莫队模板

BZOJ-2038-小Z的袜子
Sample Input
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

Sample Output
2/5
0/1
1/1
4/15

【样例解释】
询问1：共C(5,2)=10种可能，其中抽出两个2有1种可能，抽出两个3有3种可能，概率为(1+3)/10=4/10=2/5。
询问2：共C(3,2)=3种可能，无法抽到颜色相同的袜子，概率为0/3=0/1。
询问3：共C(3,2)=3种可能，均为抽出两个3，概率为3/3=1/1。
注:上述C(a, b)表示组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。

【数据规模】 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define en '\n'
#define m(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N=5e4+5,M=N,INF=0x3f3f3f3f;
struct Query{int id,l,r;}q[M];
struct Ans{ll u,v;}ans[N];
int cnt[N],a[N];
int dexl,dexr,block;ll res;
int cmp(Query x,Query y)
{
    if(x.l/block==y.l/block)
        return x.r<y.r;
    return x.l/block<y.l/block;
}
ll gcd(ll a,ll b)
{
    ll t;
    while(a)
        t=a,a=b%a,b=t;
    return b;
}
void add(int x)
{
    int c=a[x];
    if(cnt[c])
        res-=(ll)cnt[c]*(cnt[c]-1)/2;
    ++cnt[c];
    res+=(ll)cnt[c]*(cnt[c]-1)/2;
}
void del(int x)
{
    int c=a[x];
    res-=(ll)cnt[c]*(cnt[c]-1)/2;
    --cnt[c];
    if(cnt[c])
        res+=(ll)cnt[c]*(cnt[c]-1)/2;
}
int main()
{
    //m(cnt,0);
    int n,m;scanf("%d%d",&n,&m);block=sqrt(n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+m+1,cmp);
    dexl=1,dexr=0,res=0;
    for(int i=1;i<=m;i++)
    {
        while(dexr>q[i].r)
            del(dexr--);
        while(dexr<q[i].r)
            add(++dexr);
        while(dexl>q[i].l)
            add(--dexl);
        while(dexl<q[i].l)
            del(dexl++);
        ll a=res,b=(ll)(q[i].r-q[i].l+1)*(q[i].r-q[i].l)/2,x=gcd(a,b);
        ans[q[i].id]=(Ans){a/x,b/x};
    }
    for(int i=1;i<=m;i++)
        printf("%lld/%lld\n",ans[i].u,ans[i].v);
}

P2709 小B的询问

输入样例#1：
6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6

输出样例#1：
6
9
5
2

说明：1<=N、M、K<=50000

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define en '\n'
#define m(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N=5e4+5,M=N,INF=0x3f3f3f3f;
ll cnt[N],a[N],ans[N];
int dexl,dexr,block;ll res;
struct Query{int id,l,r;}q[M];
int k;
int cmp(Query x,Query y)
{
    if(x.l/block==y.l/block)
        return x.r<y.r;
    return x.l/block<y.l/block;
}
void add(int x)
{
    if(a[x]>=1&&a[x]<=k)
    {
        res-=cnt[a[x]]*cnt[a[x]];
        ++cnt[a[x]];
        res+=cnt[a[x]]*cnt[a[x]];
    }
}
void del(int x)
{
    if(a[x]>=1&&a[x]<=k)
    {
        res-=cnt[a[x]]*cnt[a[x]];
        --cnt[a[x]];
        res+=cnt[a[x]]*cnt[a[x]];
    }
}
int main()
{
    int n,m;scanf("%d%d%d",&n,&m,&k);block=sqrt(n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+m+1,cmp);
    dexl=1,dexr=0,res=0;
    for(int i=1;i<=m;i++)
    {
        while(dexr>q[i].r)
            del(dexr--);
        while(dexr<q[i].r)
            add(++dexr);
        while(dexl>q[i].l)
            add(--dexl);
        while(dexl<q[i].l)
            del(dexl++);
        ans[q[i].id]=res;
    }
    for(int i=1;i<=m;i++)
        printf("%lld\n",ans[i]);
}