[DS记录]P4690 [Ynoi2016] 镜中的昆虫

**题意** ： 维护长度为 $n$ 的序列 $A$ ，支持 ： - 区间覆盖 - 区间数颜色 允许离线，$n,m\leq 10^5$ ，时限$\texttt{1.5s}$ ，空限$\texttt{64Mb}$。 ------------ 先离散化一手。 考虑区间数颜色的经典套路，维护 $pre_i$ 表示 $A_i$ 上一次出现的位置，然后区间 $[l,r]$ 的答案即为 ： $$\sum_{i=l}^r[pre_i<l]$$ 这是二维数点。 考虑如何在区间覆盖的同时维护 $pre_i$ 。 使用 ODT 维护，会产生 $O(n+m)$ 次颜色连续段的修改。 每一个颜色连续段除了第一个位置之外，其余的 $pre_i$ 均为 $i-1$。分两部分维护。 第一部分是颜色连续段的第一个位置。我们除了用一个 `set` 维护连续段，还要用 $O(n+m)$ 个 `set` 维护每种颜色，这样才能 $O(\log n)$ 求一个 $pre$。 求答案时是动态二维偏序问题，容易转为静态三维偏序，然后用 $CDQ$ 分治解决。 对于其余 $pre_i=i-1$ 的点，只有 $pre_l$ 可能有贡献，单独判一下即可。 复杂度 $O\big((n+m)\log^2n\big)$ ，空间 $O(n+m)$。 > 不要访问删除过的迭代器！！！调了 $7$ 小时！！！ ```cpp #include<algorithm> #include<cstring> #include<cstdio> #include<set> #define Pr pair<int,int> #define fir first #define sec second #define mp make_pair #define Itor set<Pr>::iterator #define itor set<int>::iterator #define MaxN 100500 using namespace std; const int INF=1000000000; int n; #define lbit(x) (x&-x) struct SumDS{ int t[MaxN<<1]; void add(int p,int c) {p++;while(p<=n+1){t[p]+=c;p+=lbit(p);}} void clr(int p) {p++;while(p<=n+1){t[p]=0;p+=lbit(p);}} int qry(int p){ int ret=0;p++; while(p){ret+=t[p];p^=lbit(p);} return ret; } }T; struct Data{bool op;int x,y,p;}s[MaxN*10],st1[MaxN*5],st2[MaxN*5]; int ans[MaxN],tn; void solve(int l,int r) { if (l==r)return ; int mid=(l+r)>>1,lenl=mid-l+1,lenr=r-mid,tn=l-1; solve(l,mid);solve(mid+1,r); memcpy(st1,s+l,sizeof(Data)*lenl); memcpy(st2,s+mid+1,sizeof(Data)*lenr); int p=0; for (int i=0;i<lenr;i++){ while(p<lenl&&st1[p].x<=st2[i].x){ if (st1[p].op==1)T.add(st1[p].y,st1[p].p); s[++tn]=st1[p++]; }if (st2[i].op==0)ans[st2[i].p]+=T.qry(st2[i].y); s[++tn]=st2[i]; }while(p<lenl)s[++tn]=st1[p++]; for (int i=0;i<lenl;i++)T.clr(st1[i].y); } set<int> tc[MaxN<<1]; set<Pr> sg; int sp[MaxN]; void adp(int x,int y,int c) {s[++tn]=(Data){1,x,y,c};T.add(max(x,y),c);} void erase(Itor it){ int c=it->sec,p=it->fir; itor pit=tc[c].lower_bound(p);pit++; if (pit!=tc[c].end()){ Itor it=sg.lower_bound(mp(*pit,INF)); it--;pit--;pit--; int p=it->fir; adp(p,sp[p],-1); adp(p,sp[p]=*pit,1);pit++; }else pit--; tc[c].erase(pit); adp(p,sp[p],-1);sp[p]=-1; sg.erase(it); } void insert(int l,int r,int c){ itor pit=tc[c].lower_bound(l); if (pit!=tc[c].end()){ Itor it=sg.lower_bound(mp(*pit,INF));it--; int p=it->fir; adp(p,sp[p],-1); adp(p,sp[p]=r,1); } adp(l,sp[l]=*(--pit),1); sg.insert(mp(l,c));tc[c].insert(r); } struct QData{int op,l,r,x;}b[MaxN]; Itor st[MaxN]; int m,tq,a[MaxN],tx,x[MaxN<<1]; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++){scanf("%d",&a[i]);x[++tx]=a[i];} for (int i=1;i<=m;i++){ scanf("%d%d%d",&b[i].op,&b[i].l,&b[i].r); if (b[i].op==1){scanf("%d",&b[i].x);x[++tx]=b[i].x;} } sort(x+1,x+tx+1);tx=unique(x+1,x+tx+1)-x-1; for (int i=1;i<=tx;i++)tc[i].insert(0); sg.insert(mp(n+1,0)); for (int i=1;i<=n;i++){ int sav=lower_bound(x+1,x+tx+1,a[i])-x; sg.insert(mp(i,sav));tc[sav].insert(i); adp(i,sp[i]=*(--tc[sav].find(i)),1); } for (int i=1;i<=m;i++){ int l=b[i].l,r=b[i].r; if (b[i].op==1){ Itor it=sg.lower_bound(mp(l,INF)); int nxt=it->fir;it--; if (r<nxt){ Pr now=*it;erase(it); if (now.fir<l)insert(now.fir,l-1,now.sec); if (r<nxt-1)insert(r+1,nxt-1,now.sec); }else { Pr sav=*it;int tn=0; while(it->fir<=r){st[++tn]=it;it++;} int las=st[tn]->sec; //不要访问删除过的迭代器 for (int k=1;k<=tn;k++)erase(st[k]); if (sav.fir<l)insert(sav.fir,l-1,sav.sec); if (r+1<it->fir)insert(r+1,it->fir-1,las); }insert(l,r,lower_bound(x+1,x+tx+1,b[i].x)-x); }else { ans[++tq]=(sp[b[i].l]==-1)-T.qry(b[i].l-1); s[++tn]=(Data){0,b[i].r,b[i].l-1,tq}; } } memset(T.t,0,sizeof(T.t)); solve(1,tn); for (int i=1;i<=tq;i++) printf("%d\n",ans[i]); return 0; } ```