【莫队】bzoj 3781,bzoj 2038,bzoj 3289

　　好像又有一个星期没更博客了。。

　　最近疯狂考试。。。唯一有点收获的就是学会了莫队这种神奇的算法。。

　　听起来很难。。其实是一个很简单的东西。。

　　就是在区间处理问题时对于一个待求区间[L',R']通过之前求出的[L,R]更新[L,R+1],[L+1,R],[L,R-1],[L,R-1]的方式弄出答案[L,R]。

　　比如求【3,5】 我们知道了【1,7】，那么我们这样转化 : 【1,7】--> 【2,7】--> 【3,7】 --> 【3,6】 --> 【3,5】而求得。

　　那怎么确定从哪个区间转移呢？

　　在这里我们可以把区间左端点和右端点排个序，然后全局变量L,R代表当前答案区间,ans代表当前答案。。每次对于一个新询问慢慢转移即可。

　　但是这样貌似还是太暴力了。。

　　有两个优化:1) 二维曼哈顿生成树，太难写。。不推荐。

　　2)分块。把区间左端点分块处理。每次处理一个块。

　　关于分块复杂度的证明http://blog.****.net/bossup/article/details/39236275

　　其中每次转移可能是O(1)或者O(logn)。

　　下面列出一些题目。。

---

　　BZOJ 3781 小B的袜子

　　

3781: 小B的询问

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 309  Solved: 205
[Submit][Status][Discuss]

Description

小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。

Input

第一行，三个整数N、M、K。

第二行，N个整数，表示小B的序列。

接下来的M行，每行两个整数L、R。

Output

M行，每行一个整数，其中第i行的整数表示第i个询问的答案。

Sample Input

6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6

Sample Output

6
9
5
2

HINT

对于全部的数据，1<=N、M、K<=50000

---

　　基础的莫队算法。

　　在这里主要说说转移

　　一般大家的转移应该都是ans-=num[a[i]]*num[a[i]],num[a[i]]++,ans+=num[a[i]]*num[a[i]].这样大约是2400ms左右

　　这里说种更好的转移：ans+=num[a[i]++]*2+1.这样大约可以跑到1200ms左右。。

　　其他差不多。

 #include<cstdio>
 #include<cstring>
 #include<cmath>
 #include<algorithm>

 using namespace std;

 #define maxn 50001

 int n,cnt=,team[maxn],num[maxn],a[maxn];

 long long up[maxn],down[maxn];

 struct ed{
     int l,r,id;
 }edge[maxn];

 bool cmp(const ed A,const ed B)
 {
     if(team[A.l]==team[B.l])
     return A.r<B.r;
     return team[A.l]<team[B.l];
 }

 void build()
 {
     int T=sqrt(n);
     for(int i=;i<=n;i++)
     {
     if(i%T==)cnt++;
     team[i]=cnt;
     }
 }

 long long gcd(long long nn,long long mm){return nn%mm==?mm:gcd(mm,nn%mm);}

 inline int read()
 {
 int x=;char ch=getchar();
 while(ch<''||ch>'')ch=getchar();
 while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
 return x;
 }

 int main()
 {
     int m,k;
     n=read(),m=read(),k=read();
     for(int i=;i<=n;i++)a[i]=read();
     build();
     for(int i=;i<=m;i++)
     {
     edge[i].l=read(),edge[i].r=read();
     edge[i].id=i;
     }
     sort(+edge,+edge+m,cmp);
     int ll=,lr=;
     long long ans=;
     for(int i=;i<=m;i++)
     {
     if(edge[i].l==edge[i].r)
     {
         up[edge[i].id]=,down[edge[i].id]=;
         continue;
     }
     if(lr<edge[i].r)
         {
         for(int j=lr+;j<=edge[i].r;j++)
         ans+=num[a[j]]*+,num[a[j]]++;
     }
     else
     {
         for(int j=lr;j>edge[i].r;j--)
         ans-=(--num[a[j]])*+;
     }
     lr=edge[i].r;
     if(ll>edge[i].l)
     {
         for(int j=ll-;j>=edge[i].l;j--)
         ans+=num[a[j]]*+,num[a[j]]++;
     }
     else
     {
         for(int j=ll;j<edge[i].l;j++)
         ans-=(--num[a[j]])*+;
     }
     ll=edge[i].l;
     up[edge[i].id]=ans;
     }
     for(int i=;i<=m;i++)
     printf("%lld\n",up[i]);
     return ;
 }

---

　　bzoj 2038 [2009国家集训队]小Z的袜子(hose)

2038: [2009国家集训队]小Z的袜子(hose)

Time Limit: 20 Sec  Memory Limit: 259 MB
Submit: 4490  Solved: 2062
[Submit][Status][Discuss]

Description

作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。

Input

输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。

Output

包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）

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个的选取方案数。
【数据规模和约定】
30%的数据中 N,M ≤ 5000；
60%的数据中 N,M ≤ 25000；
100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。

---

　　我们先转化一下问题。

　　对于这题我们要求[L,R]中取到相同袜子的概率。

　　设区间长度是x。

　　则取两只的操作可能数:C(X,2)=x*(x-1)/2.

　　对于每种颜色i，设它在[L,R]中有Ci只袜子。

　　取到这种颜色的一双袜子可能操作数:Ci*(Ci-1)/2.

　　最后答案:C1*(C1-1)+C2*(C2-1)+...+Ck*(Ck-1)/X*(X-1).

　　转化一下就是C1^2+C2^2+C3^2+..+Ck^2-(C1-C2-C3-..-Ck)/X*(X-1).

　　=C1^2+C2^2+C3^2+..+Ck^2-X/X*(X-1).

　　其他和3781差不多。。

 #include<cstdio>
 #include<cstring>
 #include<cmath>
 #include<algorithm>

 using namespace std;

 #define maxn 50001

 int n,cnt=,team[maxn],num[maxn],a[maxn];

 long long up[maxn],down[maxn];

 struct ed{
     int l,r,id;
 }edge[maxn];

 bool cmp(const ed A,const ed B)
 {
     if(team[A.l]==team[B.l])
     return A.r<B.r;
     return team[A.l]<team[B.l];
 }

 void build()
 {
     int T=sqrt(n);
     for(int i=;i<=n;i++)
     {
     if(i%T==)cnt++;
     team[i]=cnt;
     }
 }

 long long gcd(long long nn,long long mm){return nn%mm==?mm:gcd(mm,nn%mm);}

 inline int read()
 {
 int x=;char ch=getchar();
 while(ch<''||ch>'')ch=getchar();
 while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
 return x;
 }

 int main()
 {
     int m;
     n=read(),m=read();
     for(int i=;i<=n;i++)a[i]=read();
     build();
     for(int i=;i<=m;i++)
     {
     scanf("%d%d",&edge[i].l,&edge[i].r);
     edge[i].id=i;
     }
     sort(+edge,+edge+m,cmp);
     int ll=,lr=;
     long long ans=;
     for(int i=;i<=m;i++)
     {
     if(edge[i].l==edge[i].r)
     {
         up[edge[i].id]=,down[edge[i].id]=;
         continue;
     }
     if(lr<edge[i].r)
         {
         for(int j=lr+;j<=edge[i].r;j++)
         ans+=num[a[j]]*+,num[a[j]]++;
     }
     else
     {
         for(int j=lr;j>edge[i].r;j--)
         ans-=(--num[a[j]])*+;
     }
     lr=edge[i].r;
     if(ll>edge[i].l)
     {
         for(int j=ll-;j>=edge[i].l;j--)
         ans+=num[a[j]]*+,num[a[j]]++;
     }
     else
     {
         for(int j=ll;j<edge[i].l;j++)
         ans-=(--num[a[j]])*+;
     }
     ll=edge[i].l;
     long long aa=ans-(lr-ll+);
     long long bb=(long long)(lr-ll)*(lr-ll+);
     long long cc=gcd(aa,bb);
     up[edge[i].id]=aa/cc,down[edge[i].id]=bb/cc;
     }
     for(int i=;i<=m;i++)
     printf("%lld/%lld\n",up[i],down[i]);
     return ;
 }

---

　　bzoj 3289 Mato的文件管理

　　

3289: Mato的文件管理

Time Limit: 40 Sec  Memory Limit: 128 MB
Submit: 1084  Solved: 479
[Submit][Status][Discuss]

Description

Mato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内交换2个相邻的文件（因为加密需要，不能随机访问）。Mato想要使文件交换次数最小，你能告诉他每天需要交换多少次吗？

Input

第一行一个正整数n，表示Mato的资料份数。
第二行由空格隔开的n个正整数，第i个表示编号为i的资料的大小。
第三行一个正整数q，表示Mato会看几天资料。
之后q行每行两个正整数l、r，表示Mato这天看[l,r]区间的文件。

Output

q行，每行一个正整数，表示Mato这天需要交换的次数。

Sample Input

4
1 4 2 3
2
1 2
2 4

Sample Output

0
2

HINT

Hint

n,q <= 50000

样例解释：第一天，Mato不需要交换

第二天，Mato可以把2号交换2次移到最后。

---

　　和前面的差不多。。

　　只不过转移要logn

　　加个什么树状数组维护一下就可以了。。

　　

 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<cmath>

 #define maxn 50001

 using namespace std;

 inline int in()
 {
     int x=;char ch=getchar();
     while(ch>''||ch<'')ch=getchar();
     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
     return x;
 }

 struct ed{
     int l,r,id;
 }edge[maxn],edge1[maxn];

 int a[maxn],n,pos[maxn],MST[maxn];

 long long ans=,an[maxn];

 bool cmp(const ed A,const ed B)
 {
     if(pos[A.l]==pos[B.l])
     return A.r<B.r;
     return pos[A.l]<pos[B.l];
 }

 void build()
 {
     int T=sqrt(n),res=;
     for(int i=;i<=n;i++)
     {
     if(i%T==)res++;
     pos[i]=res;
     }
 }

 void add(int d,int pos)
 {
     while(pos<=n)
     {
     MST[pos]+=d;
     pos+=pos&-pos;
     }
 }

 int b[maxn];

 int sum(int pos)
 {
     int sum=;
     while(pos)
     {
     sum+=MST[pos];
     pos-=pos&-pos;
     }
     return sum;
 }

 void pre()
 {
     for(int i=;i<=n;i++)edge1[i].id=i,edge1[i].r=a[i];
     sort(+edge1,+edge1+n,cmp);
     for(int i=;i<=n;i++)a[edge1[i].id]=i;
 }

 int main()
 {
     int q;
     n=in();
     for(int i=;i<=n;i++)a[i]=in();
     pre();
     q=in();
     build();
     for(int i=;i<=q;i++)edge[i].l=in(),edge[i].r=in(),edge[i].id=i;
     sort(+edge,+edge+q,cmp);
     int ll=,lr=;
     for(int i=;i<=q;i++)
     {
     if(lr<edge[i].r)for(int j=lr+;j<=edge[i].r;j++)ans+=j-ll-sum(a[j]),add(,a[j]);
     else for(int j=lr;j>edge[i].r;j--)add(-,a[j]),ans-=j-ll-sum(a[j]);
     lr=edge[i].r;
     if(ll>edge[i].l)for(int j=ll-;j>=edge[i].l;j--)ans+=sum(a[j]-),add(,a[j]);
     else for(int j=ll;j<edge[i].l;j++)add(-,a[j]),ans-=sum(a[j]-);
     ll=edge[i].l;
     an[edge[i].id]=ans;
     }
     for(int i=;i<=q;i++)printf("%lld\n",an[i]);
     return ;
 }