4939: [Ynoi2016]掉进兔子洞莫队压位

本文主要是介绍4939: [Ynoi2016]掉进兔子洞莫队压位，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面：http://www.lydsy.com/JudgeOnline/problem.php?id=4939

大意：
每个询问有三个区间。将三个区间里都出现的数字一个一个地删除，直到不能操作为止，求这时三个区间里总共还剩下多少个数字。

稍微思考一下发现就是求 $\sum_{i=1}^3(r_i-l_i+1)- 3\sum_{i=0}^{10^9}min\{cnt_{1i},cnt_{2i},cnt_{3i} \}$ ,其中 $cnt_{ij}$ 为第i个区间里数字j的出现次数。

显然要先离散化。考虑离散化之后如何处理。发现用什么数据结构都不好处理，而这又是一个关于区间的问题，所以考虑把每个询问拆成三个区间，使用莫队算法。然而发现虽然我们很容易通过莫队维护 $cnt_{ij}$ ，但是后面的求和却不好维护。这里正解是压位。

由于bitset每一位上的值只有0/1两种，不能直接维护 $cnt_{ij}$ ，考虑更特殊的情况。如果 $a_i$ 的值两两不同，那么 $cnt_{ij}$ 就只有0/1两种取值，这时候就能够用bitset维护每个数字在区间内是否出现过， $\sum_{i=0}^{10^9}min\{cnt_{1i},cnt_{2i},cnt_{3i} \}$ 就是三个区间的bitset取交后1的位置个数。

考虑处理 $a_i$ 不必两两相同的情况。拿样例来说：

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

1 2 2 3 3离散化之后是1 2 2 4 4。那么离散化之后，将bitset里第一位表示1是否出现过，第二位表示第一个2是否出现过，第三位表示第二个2是否出现过，第四位表示第一个4是否出现过，第五位表示第二个4是否出现过。这样处理之后，发现就能够以相同的方式计算 $\sum_{i=0}^{10^9}min\{cnt_{1i},cnt_{2i},cnt_{3i} \}$ 了。

注意到直接对所有询问用莫队处理会MLE，那么把询问可以分成几块分别处理，以重复利用空间。

代码：

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<cmath>
#define MAXN 100005
using namespace std;int N,M,Be[MAXN],A[MAXN],Hash[MAXN],Ans[MAXN];struct seg{int l,r,id;
}Q[MAXN*3];struct node{int l1,r1,l2,r2,l3,r3;
}data[MAXN];bool operator<(seg a,seg b){if(Be[a.l]==Be[b.l])return a.r<b.r;return Be[a.l]<Be[b.l];
}bitset<MAXN>Tmp,f[25005];
int Cnt[MAXN];
bool vis[25005];void Update(int p,int k){p=A[p];Cnt[p]+=k;if(k==1)Tmp[p+Cnt[p]-2]=1;else Tmp[p+Cnt[p]-1]=0;
}void Solve(int l,int r){int i,tot=0;for(i=l;i<=r;i++){Q[++tot]=(seg){data[i].l1,data[i].r1,i};Q[++tot]=(seg){data[i].l2,data[i].r2,i};Q[++tot]=(seg){data[i].l3,data[i].r3,i};}sort(Q+1,Q+tot+1);int L=1,R=0;Tmp.reset();memset(vis,0,sizeof(vis));memset(Cnt,0,sizeof(Cnt));for(i=1;i<=tot;i++){while(R<Q[i].r)Update(++R,1);while(R>Q[i].r)Update(R--,-1);while(L<Q[i].l)Update(L++,-1);while(L>Q[i].l)Update(--L,1);if(vis[Q[i].id-l])f[Q[i].id-l]&=Tmp;else f[Q[i].id-l]=Tmp,vis[Q[i].id-l]=1;}for(i=l;i<=r;i++)Ans[i]-=f[i-l].count()*3;
}int main(){int i,j;scanf("%d%d",&N,&M);for(i=1;i<=N;i++){scanf("%d",&A[i]);Hash[i]=A[i];}sort(Hash+1,Hash+N+1);for(i=1;i<=N;i++)A[i]=lower_bound(Hash+1,Hash+N+1,A[i])-Hash;int S=sqrt(N);for(i=j=1;i<=N;i++){Be[i]=j;if(i%S==0)j++;}for(i=1;i<=M;i++){int l1,r1,l2,r2,l3,r3;scanf("%d%d%d%d%d%d",&l1,&r1,&l2,&r2,&l3,&r3);Ans[i]+=r1-l1+r2-l2+r3-l3+3;data[i]=(node){l1,r1,l2,r2,l3,r3};}Solve(1,min(25000,M));if(M>25000)Solve(25001,min(50000,M));if(M>50000)Solve(50001,min(75000,M));if(M>75000)Solve(75001,M);//对询问分块处理for(i=1;i<=M;i++)printf("%d\n",Ans[i]);
}