P1494 [国家集训队]小Z的袜子

普通莫队模板题。

考虑对于任意一个区间，只需要维护平方和即可（推导题解里面就有）

中间这一段核心操作解释以下：

for(register int i=1,l=1,r=0;i<=m;++i){
        for(;r<e[i].r;++r)
            update(r+1,1);
        for(;r>e[i].r;--r)
            update(r,-1);
        for(;l<e[i].l;++l)
            update(l,-1);
        for(;l>e[i].l;--l)
            update(l-1,1);
        if(e[i].l==e[i].r){
            e[i].a=0,e[i].b=1;
            continue;
        }
        e[i].a=ans-(e[i].r-e[i].l+1);
        e[i].b=(e[i].r-e[i].l+1)*1LL*(e[i].r-e[i].l);
        ll g=gcd(e[i].a,e[i].b);
        e[i].a/=g;
        e[i].b/=g;
    }

将这一段代码分开来看。

for(;r<e[i].r;++r)
	update(r+1,1);

• 将区间右端点少了的东西补上。

for(;r>e[i].r;--r)
	update(r,-1);

• 将区间右端点多余的东西删去

for(;l<e[i].l;++l)
	update(l,-1);

• 将左端点多余的东西先删去

for(;l>e[i].l;--l)
	update(l-1,1);

• 再补上左端点少了的东西

这样反复推敲肯定不会有问题啦！

这里，我将这四段代码的顺序调为如下格式，一样能AC：

for(;r>e[i].r;--r)
	update(r,-1);
for(;r<e[i].r;++r)
	update(r+1,1);        
for(;l>e[i].l;--l)
	update(l-1,1);
for(;l<e[i].l;++l)
   update(l,-1);

说明顺序并没有任何影响。

---

update

1）具体\(update\)里面怎么写还是看题目为标准

2）这道题目主要是在维护区间的平方

inline void update(ll x,ll val){
    ans-=s[c[x]]*s[c[x]];
    s[c[x]]+=val;
    ans+=s[c[x]]*s[c[x]];
}

3）后面就直接跟着式子打就好了。

---

注意事项

1）这题目的排序有毒！尝试过以下情况：

inline int cmp(Node a,Node b){
    return a.pos!=b.pos?a.l<b.l:((a.pos&1)?a.r<b.r:a.r>b.r);
}

或

inline int cmp(Node at,Node az){    if(pos[at.pos]==pos[az.pos])        return at.r<az.r;    return at.l<az.l;}

(当然后面这个显然不对了)

至今原因不明。

#include <bits/stdc++.h>
#define ll long long
#define maxn 50005
using namespace std;
ll n,m,c[maxn],s[maxn];
ll lg,ans,pos[maxn];
struct Node{
    ll l,r,pos;
    ll a,b;
}e[maxn<<2];

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline int cmp(Node at,Node az){
    if(pos[at.l]==pos[az.l])
        return at.r<az.r;
    return at.l<az.l;
}

inline int cmp_two(Node at,Node az){
    return at.pos<az.pos;
}

inline ll gcd(ll a,ll b){
    return (b==0)?a:gcd(b,a%b);
}

inline void update(ll x,ll val){
    ans-=s[c[x]]*s[c[x]];
    s[c[x]]+=val;
    ans+=s[c[x]]*s[c[x]];
}

inline void solve(){
    for(register int i=1,l=1,r=0;i<=m;++i){
        for(;r>e[i].r;--r)
            update(r,-1);
        for(;r<e[i].r;++r)
            update(r+1,1);
        
        
        for(;l>e[i].l;--l)
            update(l-1,1);
        for(;l<e[i].l;++l)
            update(l,-1);    
        if(e[i].l==e[i].r){
            e[i].a=0,e[i].b=1;
            continue;
        }
        e[i].a=ans-(e[i].r-e[i].l+1);
        e[i].b=(e[i].r-e[i].l+1)*1LL*(e[i].r-e[i].l);
        ll g=gcd(e[i].a,e[i].b);
        e[i].a/=g;
        e[i].b/=g;
    }
}

int main(){
    n=read();m=read();
    for(register int i=1;i<=n;++i)
        c[i]=read();
    lg=sqrt(n);
    for(register int i=1;i<=n;++i)
        pos[i]=(i-1)/lg+1;
    for(register int i=1;i<=m;++i)
        e[i].l=read(),e[i].r=read(),e[i].pos=i;
    sort(e+1,e+m+1,cmp);
    solve();
    sort(e+1,e+m+1,cmp_two);
    for(register int i=1;i<=m;++i)
        printf("%lld/%lld\n",e[i].a,e[i].b);
    return 0;
}