題目描述

您正在打galgame，然后突然發(fā)現(xiàn)您今天太頹了，于是想寫個數(shù)據(jù)結構題練練手： 一個長為?n?的序列?a。

有?m?個詢問，每次詢問三個區(qū)間，把三個區(qū)間中同時出現(xiàn)的數(shù)一個一個刪掉，問最后三個區(qū)間剩下的數(shù)的個數(shù)和，詢問獨立。 注意這里刪掉指的是一個一個刪，不是把等于這個值的數(shù)直接刪完，比如三個區(qū)間是?[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。

輸入輸出格式

輸入格式：

?

第一行兩個數(shù)表示?n?,?m。

第二行?n個數(shù)表示?a[i]?。

之后?m?行，每行?6?個數(shù)?l1???,?r1???,?l2,?r2???,?l3???,?r3???表示這三個區(qū)間。

?

輸出格式：

?

對于每個詢問，輸出一個數(shù)表示答案。

?

輸入輸出樣例

輸入樣例#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已經(jīng)快RE到死了……

　　據(jù)某加藤大佬說這題一看就是莫隊+bitset維護并集，然而我啥都看不出來……

　　先把原數(shù)組給離散，然后總共只有$10^5$個數(shù)，可以對每一個詢問維護一個bitset，表示每一位有幾個，然后只要把三個詢問的bitset并起來就行了。然而bitset怎么表示數(shù)的個數(shù)呢？我們可以給每一個數(shù)很多位置，位置數(shù)為它在原數(shù)組中的個數(shù)。比方說1,1,4,3,1，那么我們就給1這個數(shù)字3個位置，做莫隊的時候，維護一個bitset，設當前已經(jīng)有x個1，且1在bitset中的位置為1，那么要add的時候，就讓第x+1位變?yōu)?，表示加了一個1，del的話，就讓第x位變?yōu)?，表示少了一個1，同時更新x

　　然后這樣有可能兩個數(shù)的區(qū)間重疊，那么我們在離散化的之后可以不去重，直接用在排序后的數(shù)組的位置表示新數(shù)，這樣每一個數(shù)就不會和其他區(qū)間重疊了

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]='\n'; 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 }

?

轉載于:https://www.cnblogs.com/bztMinamoto/p/9531585.html

總結

以上是生活随笔為你收集整理的【bzoj4939】【YNOI2016】掉进兔子洞（莫队）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。