题目描述

您正在打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 21 2 2 3 31 2 2 3 3 41 5 1 5 1 5

输出样例#1： 

30

说明

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
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            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 num19 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]='\n';27 }28 const int N=1e5+5,NN=27000;29 int n,m,len,rt[N],ans[N];30 bitset
           
             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:rt[a.l]
             
              q[i].l) add(a[--l]);63 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 }