IV.IV.[Ynoi2016] 镜中的昆虫
没错，这里就是CDQ分治 \(O(n)\) 的优势所在了——本题似乎卡掉了空间复杂度为 \(O(n\log^2n)\) 的树套树。
但这不妨碍我继续说：树套树yyds
首先，这里有一个结论：长度为 \(n\) 的序列，修改 \(m\) 次，\(las\) 数组变化的次数是 \(O(n+m)\) 的。
证明：
我们不妨将其看成初始有一个长度为 \(n\) 的全相同序列，之后先进行 \(n\) 次单点修改，再进行 \(m\) 次区间修改，也就是说总共进行 \(n+m\) 次修改。
考虑一次修改 \([l,r]\)。显然，此次修改相当于把 \(las_l\) 设成一个可以被求出的值，然后将 \(i\in(l,r]\) 的 \(las_i\) 设作 \(i-1\)。
同时，其会影响 \([l,r]\) 中出现过的所有颜色，再加上区间修改的目标颜色，这所有颜色的各一个位置——但是这些位置必定是以前某个 \([l,r]\) 的 \(l\) 位置，或者是被某次修改打断形成的新区间。
实际上，这里可以结合珂朵莉树的思想理解——珂朵莉树中存了连续的取值相同的区间，而此种区间除了开头的一个数的 \(las\) 值外，其余 \(las\) 都是 \(i-1\)。
一次修改，会产生 \(O(1)\) 个新区间，并推平一些旧区间。但是旧区间除了区间开头的元素，其余位置都不需要改变。因为一个区间最多产生一次并被推平一次，所以总数是 \(O(n+m)\) 级别的。
这时直接用珂朵莉树维护 \(las\) 值。要开一棵大珂朵莉树，同时对每种颜色各开一棵小珂朵莉树。
时间复杂度 \(O(n\log^2n)\)。
珂朵莉树太难写了，一坨坨 set 看得人头晕
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010],las[100010],res[100010],t[100010],buc[200100];
vector<int>v;
struct node{
int tp,a,b;
node(){}
node(int T,int A,int B){tp=T,a=A,b=B;}
friend bool operator<(const node&x,const node&y){return x.a==y.a?!x.tp>!y.tp:x.a<y.a;}
};
void ADD(int x,int y){while(x<=n)t[x]+=y,x+=x&-x;}
int SUM(int x){int ret=0;while(x)ret+=t[x],x-=x&-x;return ret;}
vector<node>u,w[100010];
int L[100100],R[100100],C[100100],tp[100100];
set<pair<int,int> >s[200010];
struct dat{
int l,r,c;
dat(int L,int R,int C){l=L,r=R,c=C;}
friend bool operator<(const dat&u,const dat&v){return u.l<v.l;}
};
set<dat>S;
void CDQ(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
for(int i=l;i<=mid;i++)if(!tp[i])for(auto j:w[i])u.push_back(j);
for(int i=mid+1;i<=r;i++)if(tp[i])for(auto j:w[i])u.push_back(j);
sort(u.begin(),u.end());
for(auto i:u){
if(!i.tp){
if(i.b>0)ADD(i.b,1);
else ADD(-i.b,-1);
}else{
if(i.tp>0)res[i.tp]+=SUM(i.b);
else res[-i.tp]-=SUM(i.b);
}
}
u.clear();
for(auto i:u)if(!i.tp){
if(i.b>0)ADD(i.b,-1);
else ADD(-i.b,1);
}
CDQ(l,mid),CDQ(mid+1,r);
}
#define CLAS(x,y) w[i].emplace_back(0,x,-las[x]),w[i].emplace_back(0,x,las[x]=y)
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&tp[i],&L[i],&R[i]),tp[i]=(tp[i]==2);
if(!tp[i])scanf("%d",&C[i]),v.push_back(C[i]);
}
sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
for(int i=1;i<=m;i++)if(!tp[i])C[i]=lower_bound(v.begin(),v.end(),C[i])-v.begin()+1;
for(int i=1;i<=n;i++)las[i]=buc[a[i]]+1,buc[a[i]]=i;
for(int i=1;i<=m;i++){
if(!tp[i])continue;
u.emplace_back(-i,L[i]-1,L[i]),u.emplace_back(i,R[i],L[i]);
w[i].emplace_back(-i,L[i]-1,L[i]),w[i].emplace_back(i,R[i],L[i]);
}
sort(u.begin(),u.end());
for(int i=0,j=1;i<u.size();i++){
while(j<=u[i].a)ADD(las[j++],1);
if(u[i].tp>0)res[u[i].tp]+=SUM(u[i].b);else res[-u[i].tp]-=SUM(u[i].b);
}
u.clear(),memset(t,0,sizeof(t));
for(int i=1,j=1;i<=n;i=j){
while(j<=n&&a[i]==a[j])j++;
S.insert(dat(i,j-1,a[i]));
s[a[i]].insert(make_pair(i,j-1));
}
for(int i=1;i<=m;i++){
if(tp[i])continue;
auto p=S.upper_bound(dat(L[i],L[i],L[i])),q=S.upper_bound(dat(R[i],R[i],R[i]));
auto r=p--;
for(;r!=q;++r)CLAS(r->l,r->l);
for(r=p;r!=q;++r)s[r->c].erase(make_pair(r->l,r->r));
if(p->l<L[i])s[p->c].insert(make_pair(p->l,L[i]-1));
r=q;--r;
if(r->r>R[i])s[r->c].insert(make_pair(R[i]+1,r->r));
s[C[i]].insert(make_pair(L[i],R[i]));
auto o=s[C[i]].lower_bound(make_pair(L[i],0));
if(o!=s[C[i]].begin())--o,CLAS(L[i],o->second+1);else CLAS(L[i],1);
for(r=p;r!=q;++r){
o=s[r->c].upper_bound(make_pair(R[i],0x3f3f3f3f));
if(o==s[r->c].end())continue;
int tmp=o->first;
if(o!=s[r->c].begin())--o,CLAS(tmp,o->second+1);else CLAS(tmp,1);
}
o=s[C[i]].upper_bound(make_pair(R[i],0x3f3f3f3f));
if(o!=s[C[i]].end())CLAS(o->first,R[i]+1);
int LL=p->l,LC=p->c;
r=q;--r;int RR=r->r,RC=r->c;
for(r=p;r!=q;r=S.erase(r));
S.insert(dat(L[i],R[i],C[i]));
if(LL!=L[i])S.insert(dat(LL,L[i]-1,LC));
if(RR!=R[i])S.insert(dat(R[i]+1,RR,RC));
// for(auto k:w[i])printf("[%d,%d]",k.a,k.b);puts("");
// for(auto k:S)printf("(%d,%d,%d)",k.l,k.r,k.c);puts("");
}
CDQ(1,m);
for(int i=1;i<=m;i++)if(tp[i])printf("%d\n",res[i]);
return 0;
}