【bzoj4939】【YNOI2016】掉进兔子洞（莫队）

题目描述

您正在打galgame，然后突然发现您今天太颓了，于是想写个数据结构题练练手：一个长为 n 的序列 a。

有 m 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完，比如三个区间是 [1,2,2,3,3,3,3] , [1,2,2,3,3,3,3] 与 [1,1,2,3,3]，就一起扔掉了 1 个 1，1 个 2，2 个 3。

输入输出格式

输入格式：

第一行两个数表示 n , m。

第二行 n个数表示 a[i]。

之后 m 行，每行 6 个数 l1 , r1 , l2, r2 , l3 , r3 表示这三个区间。

输出格式：

对于每个询问，输出一个数表示答案。

输入输出样例

输入样例#1：复制

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

输出样例#1：复制

3
0

说明

n , m <= 100000 , 1 <= a[i] <= 1000000000

题解

　　大毒瘤题名不虚传……

　　做莫队的时候因为先del再add已经快RE到死了……

　　据某加藤大佬说这题一看就是莫队+bitset维护并集，然而我啥都看不出来……

　　先把原数组给离散，然后总共只有$10^5$个数，可以对每一个询问维护一个bitset，表示每一位有几个，然后只要把三个询问的bitset并起来就行了。然而bitset怎么表示数的个数呢？我们可以给每一个数很多位置，位置数为它在原数组中的个数。比方说1,1,4,3,1，那么我们就给1这个数字3个位置，做莫队的时候，维护一个bitset，设当前已经有x个1，且1在bitset中的位置为1，那么要add的时候，就让第x+1位变为1，表示加了一个1，del的话，就让第x位变为0，表示少了一个1，同时更新x

　　然后这样有可能两个数的区间重叠，那么我们在离散化的之后可以不去重，直接用在排序后的数组的位置表示新数，这样每一个数就不会和其他区间重叠了

 1 //minamoto
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<bitset>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<cmath>
 8 using namespace std;
 9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
10 char buf[1<<21],*p1=buf,*p2=buf;
11 inline int read(){
12     #define num ch-'0'
13     char ch;bool flag=0;int res;
14     while(!isdigit(ch=getc()))
15     (ch=='-')&&(flag=true);
16     for(res=num;isdigit(ch=getc());res=res*10+num);
17     (flag)&&(res=-res);
18     #undef num
19     return res;
20 }
21 char sr[1<<21],z[20];int C=-1,Z;
22 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
23 inline void print(int x){
24     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
25     while(z[++Z]=x%10+48,x/=10);
26     while(sr[++C]=z[Z],--Z);sr[++C]='
';
27 }
28 const int N=1e5+5,NN=27000;
29 int n,m,len,rt[N],ans[N];
30 bitset<N> f[NN+5],tmp;
31 int a[N],b[N],L1[N],R1[N],L2[N],R2[N],L3[N],R3[N],cnt[N],l,r,tot;
32 bool flag[NN+5];
33 struct node{
34     int l,r,id;
35     node(){}
36     node(int l,int r,int id):l(l),r(r),id(id){}
37 }q[N];
38 inline bool operator <(node a,node b){
39     return rt[a.l]==rt[b.l]?rt[a.l]&1?a.r<b.r:a.r>b.r:rt[a.l]<rt[b.l];
40 }
41 inline void init(){
42     memset(cnt,0,sizeof(cnt));
43     memset(flag,0,sizeof(flag));
44     tmp.reset();
45     l=1,r=0,tot=0;
46 }
47 inline void add(int x){
48     tmp[x+cnt[x]]=1,++cnt[x];
49 }
50 inline void del(int x){
51     tmp[x+cnt[x]-1]=0,--cnt[x];
52 }
53 inline void solve(int lx,int rx){
54     init();
55     for(int i=lx;i<=rx;++i){
56         q[++tot]=node(L1[i],R1[i],i),ans[i]+=R1[i]-L1[i]+1;
57         q[++tot]=node(L2[i],R2[i],i),ans[i]+=R2[i]-L2[i]+1;
58         q[++tot]=node(L3[i],R3[i],i),ans[i]+=R3[i]-L3[i]+1;
59     }
60     sort(q+1,q+1+tot);
61     for(int i=1;i<=tot;++i){
62         while(l>q[i].l) add(a[--l]);
63         while(r<q[i].r) add(a[++r]);
64         while(l<q[i].l) del(a[l++]);
65         while(r>q[i].r) del(a[r--]);
66         if(!flag[q[i].id-lx+1]) flag[q[i].id-lx+1]=1,f[q[i].id-lx+1]=tmp;
67         else f[q[i].id-lx+1]&=tmp; 
68     }
69     for(int i=lx;i<=rx;++i) ans[i]-=f[i-lx+1].count()*3;
70 }
71 int main(){
72     n=read(),m=read(),len=sqrt(n);
73     for(int i=1;i<=n;++i) a[i]=b[i]=read(),rt[i]=(i-1)/len+1;
74     sort(b+1,b+1+n);
75     for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
76     for(int i=1;i<=m;++i)
77     L1[i]=read(),R1[i]=read(),L2[i]=read(),R2[i]=read(),L3[i]=read(),R3[i]=read();
78     for(int i=1;i<=m;i+=NN) solve(i,min(m,i+NN-1));
79     for(int i=1;i<=m;++i) print(ans[i]);
80     Ot();
81     return 0;
82 }