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
*/