【莫队】bzoj 3781,bzoj 2038,bzoj 3289-白红宇

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

阅读量：4445 次

发布时间：2019-06-07

本文共 6410 字，大约阅读时间需要 21 分钟。

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

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

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

　　就是在区间处理问题时对于一个待求区间[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.csdn.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

[][][]

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

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左右。。

　　其他差不多。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5   6 using namespace std; 7   8 #define maxn 50001 9  10 int n,cnt=1,team[maxn],num[maxn],a[maxn];11  12 long long up[maxn],down[maxn];13  14 struct ed{15     int l,r,id;16 }edge[maxn];17  18 bool cmp(const ed A,const ed B)19 {20     if(team[A.l]==team[B.l])21     return A.r
           
            '9')ch=getchar();41 while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();42 return x;43 }44  45 int main()46 {47     int m,k;48     n=read(),m=read(),k=read();49     for(int i=1;i<=n;i++)a[i]=read();50     build();51     for(int i=1;i<=m;i++)52     {53     edge[i].l=read(),edge[i].r=read();54     edge[i].id=i;55     }56     sort(1+edge,1+edge+m,cmp);57     int ll=1,lr=0;58     long long ans=0;59     for(int i=1;i<=m;i++)60     {61     if(edge[i].l==edge[i].r)62     {63         up[edge[i].id]=1,down[edge[i].id]=1;64         continue;65     }66     if(lr
            
             edge[i].r;j--)74 ans-=(--num[a[j]])*2+1;75 }76 lr=edge[i].r;77 if(ll>edge[i].l)78 {79 for(int j=ll-1;j>=edge[i].l;j--)80 ans+=num[a[j]]*2+1,num[a[j]]++;81 }82 else83 {84 for(int j=ll;j

View Code

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

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

Time Limit: 20 Sec Memory Limit: 259 MB

Submit: 4490 Solved: 2062

[][][]

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差不多。。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5  6 using namespace std; 7  8 #define maxn 50001 9 10 int n,cnt=1,team[maxn],num[maxn],a[maxn];11 12 long long up[maxn],down[maxn];13 14 struct ed{15     int l,r,id;16 }edge[maxn];17 18 bool cmp(const ed A,const ed B)19 {20     if(team[A.l]==team[B.l])21     return A.r
           
            '9')ch=getchar();41 while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();42 return x;43 }44 45 int main()46 {47     int m;48     n=read(),m=read();49     for(int i=1;i<=n;i++)a[i]=read();50     build();51     for(int i=1;i<=m;i++)52     {53     scanf("%d%d",&edge[i].l,&edge[i].r);54     edge[i].id=i;55     }56     sort(1+edge,1+edge+m,cmp);57     int ll=1,lr=0;58     long long ans=0;59     for(int i=1;i<=m;i++)60     {61     if(edge[i].l==edge[i].r)62     {63         up[edge[i].id]=0,down[edge[i].id]=1;64         continue;65     }66     if(lr
            
             edge[i].r;j--)74 ans-=(--num[a[j]])*2+1;75 }76 lr=edge[i].r;77 if(ll>edge[i].l)78 {79 for(int j=ll-1;j>=edge[i].l;j--)80 ans+=num[a[j]]*2+1,num[a[j]]++;81 }82 else83 {84 for(int j=ll;j

View Code

　　bzoj 3289 Mato的文件管理

3289: Mato的文件管理

Time Limit: 40 Sec Memory Limit: 128 MB

Submit: 1084 Solved: 479

[][][]

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

1 4 2 3

1 2

2 4

Sample Output

HINT

Hint

n,q <= 50000

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

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

　　和前面的差不多。。

　　只不过转移要logn

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

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5  6 #define maxn 50001 7  8 using namespace std; 9 10 inline int in()11 {12     int x=0;char ch=getchar();13     while(ch>'9'||ch<'0')ch=getchar();14     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();15     return x;16 }17 18 struct ed{19     int l,r,id;20 }edge[maxn],edge1[maxn];21 22 int a[maxn],n,pos[maxn],MST[maxn];23 24 long long ans=0,an[maxn];25 26 bool cmp(const ed A,const ed B)27 {28     if(pos[A.l]==pos[B.l])29     return A.r
            
             edge[i].r;j--)add(-1,a[j]),ans-=j-ll-sum(a[j]);87     lr=edge[i].r;88     if(ll>edge[i].l)for(int j=ll-1;j>=edge[i].l;j--)ans+=sum(a[j]-1),add(1,a[j]);89     else for(int j=ll;j