Description

見EOJ439

Solution

先考慮不強(qiáng)制在線怎么做。

按詢問區(qū)間右端點(diǎn)排序，從左往右掃，維護(hù)所有后綴的答案。

如果掃到 \(a[i]\)，那么讓統(tǒng)計(jì)個(gè)數(shù)的 \(cnt[a[i]]++\).

如果\(cnt[a[i]]<a[i]\)，那么在當(dāng)前的右端點(diǎn)固定的情況下這個(gè)\(a[i]\)不會(huì)有任何的貢獻(xiàn)。

如果\(cnt[a[i]]=a[i]\)，那么可以讓\([1,pre[i]]\)區(qū)間加\(1\)，其中\(pre[i]\)代表從\(i\)向前第\(a[i]\)個(gè)\(a[i]\)出現(xiàn)的位置。

如果\(cnt[a[i]]>a[i]\)，那么需要讓\((pos[pos[pre[i]]],pos[pre[i]]]\)區(qū)間減\(1\)，其中\(pos[i]\)代表從\(i\)向前第\(1\)個(gè)\(a[i]\)出現(xiàn)的位置，同時(shí)還需要讓\((pos[pre[i]],pre[i]]\)區(qū)間加\(1\)。

這個(gè)放上線段樹區(qū)間修改單點(diǎn)查詢就好了。

但是要求強(qiáng)制在線。

推上主席樹。

還要區(qū)間修改。

pushdown空間巨大？

標(biāo)記永久化。

Code

#include<set> #include<map> #include<cmath> #include<queue> #include<cctype> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using std::min; using std::max; using std::swap; using std::vector; const int N=1e5+5; typedef double db; const int maxn=1e5; typedef long long ll; #define pb(A) push_back(A) #define pii std::pair<int,int> #define all(A) A.begin(),A.end() #define mp(A,B) std::make_pair(A,B)vector<int> v[N]; int n,q,a[N],sum[N*30],cov[N*30]; int root[N],ch[N*30][2],cnts[N],tot;int getint(){int X=0,w=0;char ch=0;while(!isdigit(ch))w|=ch=='-',ch=getchar();while( isdigit(ch))X=X*10+ch-48,ch=getchar();if(w) return -X;return X; }int modify(int pre,int l,int r,int ql,int qr,int c){int cur=++tot;ch[cur][0]=ch[pre][0];ch[cur][1]=ch[pre][1];sum[cur]=sum[pre]+c*(qr-ql+1);cov[cur]=cov[pre];if(ql<=l and r<=qr){cov[cur]+=c;return cur;} int mid=l+r>>1;if(qr<=mid) ch[cur][0]=modify(ch[pre][0],l,mid,ql,qr,c);else if(ql>mid) ch[cur][1]=modify(ch[pre][1],mid+1,r,ql,qr,c);else{ch[cur][0]=modify(ch[pre][0],l,mid,ql,mid,c);ch[cur][1]=modify(ch[pre][1],mid+1,r,mid+1,qr,c);} return cur; }int query(int cur,int l,int r,int ql,int qr,int add){if(ql<=l and r<=qr) return sum[cur]+add*(r-l+1);int mid=l+r>>1;if(qr<=mid) return query(ch[cur][0],l,mid,ql,qr,add+cov[cur]);else if(ql>mid) return query(ch[cur][1],mid+1,r,ql,qr,add+cov[cur]);else return query(ch[cur][0],l,mid,ql,mid,add+cov[cur])+query(ch[cur][1],mid+1,r,mid+1,qr,add+cov[cur]); }signed main(){n=getint(),q=getint();for(int i=1;i<=n;i++) v[i].pb(0);for(int i=1;i<=n;i++){a[i]=getint();root[i]=root[i-1];if(a[i]>n)continue;cnts[a[i]]++;v[a[i]].pb(i);if(cnts[a[i]]==a[i])root[i]=modify(root[i],1,n,1,v[a[i]][1],1);else if(cnts[a[i]]>a[i]){int sze=v[a[i]].size();root[i]=modify(root[i],1,n,v[a[i]][sze-a[i]-2]+1,v[a[i]][sze-a[i]-1],-1);root[i]=modify(root[i],1,n,v[a[i]][sze-a[i]-1]+1,v[a[i]][sze-a[i]],1);}} int lasans=0;while(q--){int x=getint()^lasans,y=getint()^lasans;printf("%d\n",lasans=query(root[y],1,n,x,x,0));} return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YoungNeal/p/9857615.html

總結(jié)

以上是生活随笔為你收集整理的[EOJ439] 强制在线的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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