BZOJ 2038 小Z的袜子(莫队模板题)

• 题目大意

  n个数，给出m组询问，每次询问给出一个区间 [L,R] ，在区间中任意选则两个数，问这两个数相同的概率是多少.

• 分析

  设一次查询 [L,R] 区间中的不同的元素有x,y,z….，每个元素的个数是a,b,c

  a+b+c=(R-L+1)

  那么概率为:

  C2a+C2b+C2c...C2a+b+c...=a(a−1)2+b(b−1)2+c(c−1)2...(R−L+1)(R−L)2=a2+b2+c2...−(R−L+1)(R−L+1)(R−L)

  那么问题就转化成了给出一个区间 [L,R] ,求这个区间中的不同元素个数的平方和 a2+b2+c2...

  题目是离线的m次查询，可以用莫队来维护这个信息。

• 莫队基本思想

  莫队处理的问题是离线的区间查询问题

  适用的类型是如果我们知道区间 [L,R] 的信息，我们可以很快地求区间 [L−1,R],[L+1,R],[L,R−1],[L,R+1] .那么我们就可以通过莫队来维护这个区间信息

  莫队的基本思想是分块，对于有n个元素的序列，我们将这个序列分成 n−−√ 块，然后按照这m个查询区间的左端点确定每个区间在哪一块，接下来对这m个区间进行排序，先按照块的序号排序，在相同块内的区间按照右端点进行排序。

  排号序后我们通过不断地变化当前查询区间(上面所说的四个变化)依次得到排好序这m个区间.

  莫队的时间复杂度是 O(nn−√)

• 代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
#define LL long long int
const int MAXN=;
int n,m;
int a[MAXN];
LL num[MAXN];
LL up[MAXN],down[MAXN];//up[i]/down[i]表示第i次查询的答案
struct Qu
{
    int l,r,id;
}qu[MAXN];
int pos[MAXN];//pos[i]表示数组中下标i所在的块的标号
int block;//保存块数
bool cmp( Qu qu1, Qu qu2)
{
    if(pos[qu1.l]!=pos[qu2.l])return pos[qu1.l] < pos[qu2.l];
    else return qu1.r < qu2.r;
}
LL gcd(LL a,LL b)
{
    return b== ? a : gcd(b,a%b);
}
void Update(LL &ans,int x,int t)//增加t个a[x]
{
    ans-=num[a[x]]*num[a[x]];
    num[a[x]]+=t;
    ans+=num[a[x]]*num[a[x]];
}
void In()
{
    scanf("%d%d",&n,&m);
    memset(num,,sizeof(num));
    block=ceil(sqrt(*n));//向上取整
    for(int i=;i<=n;i++)
    {
        scanf("%d",&a[i]);
        pos[i]=(i-)/block+;
    }
    int a,b;
    for(int i=;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        qu[i].l=a;
        qu[i].r=b;
        qu[i].id=i;
    }
}
void Work()
{
    int ql=,qr=;///注意这里ql=1qr=0
    LL ans=;//ans中保存的是区间[ql,qr]的答案
    for(int i=;i<=m;i++)
    {
        int id=qu[i].id;
        if(qu[i].l==qu[i].r){up[id]=;down[id]=;continue;}

        if(qr < qu[i].r)for(int j=qr+;j<=qu[i].r;j++)Update(ans,j,);
        else for(int j=qr;j>qu[i].r;j--)Update(ans,j,-);
        qr=qu[i].r;

        if(ql < qu[i].l)for(int j=ql;j<qu[i].l;j++)Update(ans,j,-);
        else for(int j=ql-;j>=qu[i].l;j--)Update(ans,j,);
        ql=qu[i].l;

        up[id]=ans-(LL)(qu[i].r-qu[i].l+);
        down[id]=(LL)(qu[i].r-qu[i].l+)*(LL)(qu[i].r-qu[i].l);
        LL t=gcd(up[id],down[id]);
        up[id]/=t;
        down[id]/=t;
    }
}
int main()
{
    In();
    sort(qu+,qu++m,cmp);
    Work();
    for(int i=;i<=m;i++)
    {
        printf("%lld/%lld\n",up[i],down[i]);///这道题在bzoj上交不能用cout，printf中不能用I64d,坑
    }
    return ;
}
/*
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
*/