题解 P4690 【[Ynoi2016]镜中的昆虫】

shadowice1984

2018-09-08 17:00:10

Solution

普通数据结构题…… 注意通过封装以及分好函数来规避分情况讨论的尴尬情况……,不然你会死的很惨 _____________________ # 本题题解 题目简单明了区间赋值区间数颜色 但是这个东西乍一看是十分不可做的,所以让我们先来想一个这个问题的弱化版本作为启发… ____________________ ### 单点修改区间数颜色 那么对于区间数颜色问题我们是有一个非常明确的套路的,就是只数这个区间里某种颜色最左边的点,这样的话每种颜色只会被数到过一次 具体实现上来讲我们可以处理一个$pre$数组,其中$pre_{i}$表示i左侧第一个和他同色点的位置,如果没有的$pre_{i}=0$ 这样的话询问$[l,r]$区间里的颜色个数等价于询问$[l,r]$区间里有多少个点的$pre$值小于$l$,因为这些$pre$值小于l的点都是自己这个颜色的左边第一个点,所以这样数颜色就可以不重不漏的数完每一个颜色 然后接下来要支持静态的询问就不是非常困难了,无论是用主席树维护一下还是把询问离线一下用线段树维护都可以,你可以认为我们是将$(i,pre_{i})$看作二维平面上的一个点,每次数颜色相当于是询问$[l,r][0,l)$这个矩形里有多少个点,从而将问题转化为了一个经典的二维数点问题 问题来了,我们现在要支持单点修改,该怎么做呢? 发现一件事情是我们更改一个点的颜色的时候这个点的pre值会改变,并且pre值是这个点的点的pre值也会发生改变(也就是这个点右侧第一个和他同色的点的pre值会改变),但是除此之外没有别的点的pre值会发生改变了,这样的话我们一次操作只需要修改$O(1)$个点的pre值就可以了 我们每种颜色开一个set,然后这样的话我们就可以查出修改的的右侧第一个和他同色的点的是谁,然后我们修改pre值的话相当于在二维平面上插入一个点并删去一个点具体来讲我们把i的pre值修改为val的时候在$(i,pre_{i})$单点-1一下然后在$(i,val)$这个位置单点+1一下就行了 然后这就是经典的带修改二维数点问题了 写二维线段树?常数大的不行而且由于一次修改需要拆成4次单点加减法操作稍微多些稍不留神就mle了 为什么不试试神奇的cdq分治呢?常数小省空间还跑到快 我们发现每一个点修改会对时间在他之后的一个矩形询问产生+1/-1/0的贡献(取决于这个点到底在不在矩形里面) 而这样的关系有$O(n^2)$种,因此我们对这些修改-询问关系进行分治 假设我们现在处理时间在$(l,r)$这段区间的修改-询问关系 那么我们可以按照修改-询问关系是否跨越$(l,r)$的中点mid进行分类,所以我们先递归的考虑$(l,mid)$的修改-询问关系。递归然后考虑$(mid,r)$的修改-询问关系 现在考虑所有跨越了mid的修改询问关系,我们发现这相当于是先做了$(l,mid)$之前的所有修改然后做了$(mid,r)$的所有询问工作,换句话说我们此时的问题是个彻头彻尾的静态问题…… 那么将所有修改按照$pre$进行排序,将所有询问按照$l$进行排序,然后开始处理每一个询问,将所有$pre$值小于这个询问的$l$的修改,都插到树状数组里面 (插入方法是如果这个修改是将$(i,pre)$这个点添加/删去,那么就在树状数组i这个位置单点+1/-1) 此时我们在树状数组上区间求一下和就可以算出$(l,mid)$所有的修改对这个询问的贡献了 由于所有修改已经按照pre值排好序,所有询问已经按照l排好序,所以我们可以使用双指针的形式来不停的向树状数组插入点,总插入量$O(n)$ 此时我们的时间复杂度是$T(n)=T(\lfloor \frac{n}{2} \rfloor)+T(\lceil \frac{n}{2} \rceil)+O(nlogn)=O(nlog^2n)$的 具体写的时候你会发现可能为了排序只能写一个5元组结构体出来(因为询问是$(time,l,r,ans)$而修改是$(time,pos,pre,val)$这个4个参数,为了区分类型可能还得加一个type属性)这会导致修改和询问只能凑合着用同一组变量名,十分的不清真。 那么这里我们可以有一个代码上的trick可以让你不用写一个5元组结构体,而是询问写一个4元组,修改写一个4元组,变量名会变得比较清真的写法 就是我们写cdq的solve函数的时候不传$(l,r)$这个参表示我们分治$(l,r)$这段操作序列而是传6个参$(l1,r1),(l2,r2),(L,R)$表示分治时间范围在$(L,R]$的操作序列,其中修改部分的序列是$(l1,r1]$而询问部分的序列是$(l2,r2]$,然后每次分治的时候先求出$(L,R]$中点的$MID$,然后分别求出修改序列和询问序列时间比$MID$小的部分$(l1,mid1]$和$(l2,mid2]$那么比$MID$大的部分就是$(mid1,r1]$和$(mid2,r2]$了,此时我们就可以递归的向两侧分治了 这样写的话并不需要将修改和询问塞到同一个数组里面而是可以将修改存一个数组,询问存一个数组,同时对两个序列进行分治因此自然可以开两个结构体,不仅变量名清真而且处理贡献的时候不用判节点的类型了。 __________________________ ### 区间赋值区间数颜色 ## 结论: ## 对一个长度为n的数组进行m次区间赋值操作,pre数组的改变次数为$O(n+m)$级别 ~~好了有了这个结论我们可以直接cdq了,每次区间赋值拆成暴力单点的pre值改变即可~~ 乍一看这个结论相当的不可接受,明明我单次修改了$O(n)$个点的颜色到头来你告诉我总改变次数是$O(n+m)$级别的? ~~当你觉得一个东西复杂度相当诡异的时候他一定是用了摊还分析,比如splay,比如lct~~ 所以我们也用摊还分析来证明这个东西的复杂度是对的 先来考虑一下pre数组的定义,左侧第一个和i同色点的位置 所以如果有一个内部的点的颜色相同的区间,此时我们将这个区间的颜色整体赋值成一个别的颜色,那么只有这个区间左端点的pre值以及右端点右侧第一个同色点的pre值会变,对于其他的点,因为左边的点换完颜色之后还是同色的,pre值保持$i-1$不变 根据这个性质,我们将颜色相同的一段看成一个点 那么我们的区间赋值相当于执行删去$(l,r)$中的所有点,然后插入$(l,r)$这个点这个操作(可能我们的l,r落在了一个区间里面而不是包含这个区间,那么我们可以将这个节点从l处或者从r断开,拆成两个节点) 根据刚才的结论,$pre_{i}$的改变次数应该是O(删去节点个数)的,问题来了,一开始节点有n个,每次区间赋值最多插入3个节点,每个节点最多被删除一次,那么我们删除的总节点个数就是$O(n+m)$级别的,从而pre的改变此时就是$O(n+m)$级别的了…… 具体来讲我们每个区间缩成一个点存到set里面,当区间赋值的时候首先split两下左端点和右端点所在的块,将他们从l和r这两个位置断成两个块,之后删除l,r之间的所有块,最后将$(l,r)$这个块插到set里面,总复杂度$O((n+m)logn)$,至于插入和删除时pre到底变成了谁可以每种颜色开一个set单独维护一下,注意保持每种颜色开的set和存储整个序列的set是同步的,否则你的pre的改变量就炸掉了 然后就是实现时候的细节了,我们需要注意的是,请不要妄想你可以一遍插入删除一遍维护好pre的变化,这样会导致你的代码又臭又长充斥分情况讨论 正确的写法的是修改的时候把所有可能pre值变动的点,也就是被删掉块的左端点和被删掉(插入)块在自己颜色的set里的后继的左端点,丢到一个set里面,在修改结束之后挨个去查这些点的pre值都变成了什么,具体来讲先在维护序列的set里面查一下这个点的颜色,如果这个点不是左端点的话pre就是i-1,否则到自己的颜色里面取查前驱,pre值就是前驱的右端点 处理好pre值的变化之后直接去套单点修改时的cdq代码就可以解决问题了 上代码~ ```C #include<cstdio> #include<algorithm> #include<set> #include<map> #define SNI set <nod> :: iterator #define SDI set <data> :: iterator using namespace std;const int N=1e5+10;int n;int m;int pre[N];int npre[N];int a[N];int tp[N];int lf[N];int rt[N];int co[N]; struct modi{int t;int pos;int pre;int va;friend bool operator <(modi a,modi b){return a.pre<b.pre;}}md[10*N];int tp1; struct qry{int t;int l;int r;int ans;friend bool operator <(qry a,qry b){return a.l<b.l;}}qr[N];int tp2;int cnt; inline bool cmp(const qry& a,const qry& b){return a.t<b.t;} inline void modify(int pos,int co)//修改函数 { if(npre[pos]==co)return;md[++tp1]=(modi){++cnt,pos,npre[pos],-1}; md[++tp1]=(modi){++cnt,pos,npre[pos]=co,1}; } namespace prew { int lst[2*N];map <int,int> mp;//提前离散化 inline void prew() { scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]),mp[a[i]]=1; for(int i=1;i<=m;i++){scanf("%d%d%d",&tp[i],&lf[i],&rt[i]);if(tp[i]==1)scanf("%d",&co[i]),mp[co[i]]=1;} map <int,int> :: iterator it,it1; for(it=mp.begin(),it1=it,++it1;it1!=mp.end();++it,++it1)it1->second+=it->second; for(int i=1;i<=n;i++)a[i]=mp[a[i]];for(int i=1;i<=m;i++)if(tp[i]==1)co[i]=mp[co[i]]; for(int i=1;i<=n;i++)pre[i]=lst[a[i]],lst[a[i]]=i;for(int i=1;i<=n;i++)npre[i]=pre[i]; } } namespace colist { struct data {int l;int r;int x;friend bool operator <(data a,data b){return a.r<b.r;}};set <data> s; struct nod {int l;int r;friend bool operator <(nod a,nod b){return a.r<b.r;}};set <nod> c[2*N];set <int> bd; inline void split(int mid)//将一个节点拆成两个节点 { SDI it=s.lower_bound((data){0,mid,0});data p=*it;if(mid==p.r)return; s.erase(p);s.insert((data){p.l,mid,p.x});s.insert((data){mid+1,p.r,p.x}); c[p.x].erase((nod){p.l,p.r});c[p.x].insert((nod){p.l,mid});c[p.x].insert((nod){mid+1,p.r}); } inline void del(set <data> :: iterator it)//删除一个迭代器 { bd.insert(it->l);SNI it1,it2;it1=it2=c[it->x].find((nod){it->l,it->r}); ++it2;if(it2!=c[it->x].end())bd.insert(it2->l);c[it->x].erase(it1);s.erase(it); } inline void ins(data p)//插入一个节点 { s.insert(p);SNI it=c[p.x].insert((nod){p.l,p.r}).first;++it; if(it!=c[p.x].end()){bd.insert(it->l);} } inline void stv(int l,int r,int x)//区间赋值 { if(l!=1)split(l-1);split(r);int p=l;//split两下之后删掉所有区间 while(p!=r+1){SDI it=s.lower_bound((data){0,p,0});p=it->r+1;del(it);} ins((data){l,r,x});//扫一遍set处理所有变化的pre值 for(set <int> :: iterator it=bd.begin();it!=bd.end();++it) { SDI it1=s.lower_bound((data){0,*it,0}); if(*it!=it1->l)modify(*it,*it-1); else { SNI it2=c[it1->x].lower_bound((nod){0,*it}); if(it2!=c[it1->x].begin())--it2,modify(*it,it2->r);else modify(*it,0); } }bd.clear(); } inline void ih() { int nc=a[1];int ccnt=1;//将连续的一段插入到set中 for(int i=2;i<=n;i++) if(nc!=a[i]){s.insert((data){i-ccnt,i-1,nc}),c[nc].insert((nod){i-ccnt,i-1});nc=a[i];ccnt=1;} else {ccnt++;} s.insert((data){n-ccnt+1,n,a[n]}),c[a[n]].insert((nod){n-ccnt+1,n}); } } namespace cdq { struct treearray//树状数组 { int ta[N]; inline void c(int x,int t){for(;x<=n;x+=x&(-x))ta[x]+=t;} inline void d(int x){for(;x<=n;x+=x&(-x))ta[x]=0;} inline int q(int x){int r=0;for(;x;x-=x&(-x))r+=ta[x];return r;} inline void clear(){for(int i=1;i<=n;i++)ta[i]=0;} }ta;int srt[N]; inline bool cmp1(const int& a,const int& b){return pre[a]<pre[b];} inline void solve(int l1,int r1,int l2,int r2,int L,int R)//cdq { if(l1==r1||l2==r2)return;int mid=(L+R)/2; int mid1=l1;while(mid1!=r1&&md[mid1+1].t<=mid)mid1++; int mid2=l2;while(mid2!=r2&&qr[mid2+1].t<=mid)mid2++; solve(l1,mid1,l2,mid2,L,mid);solve(mid1,r1,mid2,r2,mid,R); if(l1!=mid1&&mid2!=r2) { sort(md+l1+1,md+mid1+1);sort(qr+mid2+1,qr+r2+1); for(int i=mid2+1,j=l1+1;i<=r2;i++)//考虑左侧对右侧贡献 { while(j<=mid1&&md[j].pre<qr[i].l)ta.c(md[j].pos,md[j].va),j++; qr[i].ans+=ta.q(qr[i].r)-ta.q(qr[i].l-1); }for(int i=l1+1;i<=mid1;i++)ta.d(md[i].pos); } } inline void mainsolve() { colist::ih();for(int i=1;i<=m;i++) if(tp[i]==1)colist::stv(lf[i],rt[i],co[i]);else qr[++tp2]=(qry){++cnt,lf[i],rt[i],0}; sort(qr+1,qr+tp2+1);for(int i=1;i<=n;i++)srt[i]=i;sort(srt+1,srt+n+1,cmp1); for(int i=1,j=1;i<=tp2;i++)//初始化一下每个询问的值 { while(j<=n&&pre[srt[j]]<qr[i].l)ta.c(srt[j],1),j++; qr[i].ans+=ta.q(qr[i].r)-ta.q(qr[i].l-1); }ta.clear();sort(qr+1,qr+tp2+1,cmp);solve(0,tp1,0,tp2,0,cnt);sort(qr+1,qr+tp2+1,cmp); for(int i=1;i<=tp2;i++)printf("%d\n",qr[i].ans); } } int main(){prew::prew();cdq::mainsolve();return 0;}//拜拜程序~ ```