P4690 Ynoi2016 镜中的昆虫
原题不会见祖宗。
前置
珂朵莉树、cdq 分治、树状数组
思路
单点修改区间查询
定义 \(pre_i\) 表示 \(col_i\) 的前一个一样颜色的位置，那么对于一段区间查询 \([l,r]\)，我们只需要查询有区间内有多少个 \(pre_i< l\)。
每次修改时就相当于修改四个同颜色的点的 \(pre\) 值，用 \(set\) 维护每个颜色的编号，树套树维护区间的 \(pre\) 值，一次修改就可以变为若干次树套树上的修改。
但实际上也可以使用 cdq 分治，先按照时间排序，对于时间区间 \([l,r]\) 取其终点 \(mid=\frac{l+r}{2}\)，使 \([l,mid]\) 时刻中的修改对 \((mid,r]\) 的询问做贡献。
然后按照修改的 \(pre\) 值小于查询的 \(l\)，依次插入树状数组。
但这样我们的 cdq 分治的排序会比较复杂，需要维护查询 \((time,l,r,ans,type)\)，修改 \((time,pos,pre,val,type)\)，这两个五元组。
我们可以考虑把查询和修改拆开拆成两个数组，\(mid\) 为时刻 \([L,R]\) 的中点，每次找到修改时刻小于 \(mid\) 的部分 \([l_1,mid_1]\) 和查询时刻小于 \(mid\) 的部分 \([l_2,mid_2]\)，使用 \([l_1,mid_1]\) 对 \((mid_2,r_2]\) 贡献，下传 \((l_1,mid_1,l_2,mid_2,L,mid)\) 和 \((mid_1+1,r_1,mid_2+1,r_2,mid,R)\)，就可以让你的代码优美一点。
inline void solve(int l1,int r1,int l2,int r2,int L,int R)
{
if(l1==r1||l2==r2||L==R) return ;
int mid=(L+R)>>1;
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) T.updata(md[j].pos,md[j].val),j++;
qr[i].ans+=T.getsum(qr[i].r)-T.getsum(qr[i].l-1);
}
for(int i=l1+1;i<=mid1;i++) T.del(md[i].pos);
}
}
//md 是修改,qr 是查询
区间修改区间查询
结论：对一个长度为 n 的数组进行 m 次区间赋值操作，pre 数组的改变次数为 \((n+m)\) 级别
我们只需要每次对于一个区间推平 \([l,r]\)，如果其内部有一个区间的颜色是相同的，现在需要将其赋值为其他的颜色，那么只有 \(l\) 的 \(pre\) 值，和右端点右侧第一个同色点的 \(pre\) 值会改变。
根据这个性质，我们可以把颜色相同的区间看做一个点，所以 \(pre\) 的改变是删去节点个数，一开始有 \(n\) 个节点，\(m\) 次修改，总复杂度在 \(O(n+m)\) 级别。
具体的修改可以参考珂朵莉树的区间推平，一个 set 维护所有的区间和颜色。\([l,r]\) 端点的落下区间 split 拆开，然后把 \([l,r]\) 中的所有区间删除。删除时的 \(pre\) 变成了什么可以每个颜色开一个 set 维护，注意每个颜色的 set 和整体的 set 是同步的。
具体看代码吧。
CODE
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m;
int a[maxn];
int pre[maxn],npre[maxn];
int tp[maxn],lf[maxn],rt[maxn],co[maxn];
#define SNI set <nod> :: iterator
#define SDI set <data> :: iterator
struct modi{int t,pos,pre,val;friend bool operator<(modi a,modi b){return a.pre<b.pre;}}md[10*maxn];int tp1;
struct qry{int t,l,r,ans;friend bool operator<(qry a,qry b){return a.l<b.l;}}qr[maxn];int tp2,cnt;
inline bool cmp(qry a,qry b){return a.t<b.t;}
inline void modify(int pos,int co)//将 pos 点的 pre 值改成 co（原来的 pre 值是 npre[pos]）
{
if(npre[pos]==co) return ;
md[++tp1]=(modi){++cnt,pos,npre[pos],-1};
md[++tp1]=(modi){++cnt,pos,npre[pos]=co,1};
}
namespace preview
{
int lst[2*maxn];
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();it1++,it++) it1->second+=it->second;
for(int i=1;i<=n;i++) a[i]=mp[a[i]];for(int i=1;i<=m;i++) 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,r,x;friend bool operator<(data a,data b){return a.r<b.r;}};set <data> s;
struct nod {int l,r;friend bool operator<(nod a,nod b){return a.r<b.r;}};set <nod> c[2*maxn];set <int> bd;
//bd 维护了等待更改的 l 点
inline void split(int mid)//把区间 [l,r] 拆成 [l,mid-1] 和 [mid,r]
{
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;//
while(p!=r+1){SDI it=s.lower_bound((data){0,p,0});p=it->r+1;del(it);}
ins((data){l,r,x});
for(auto it=bd.begin();it!=bd.end();it++)//对 l 点 pre 进行更新
{
auto it1=s.lower_bound((data){0,*it,0});
if(*it!=it1->l) modify(*it,*it-1);
else
{
auto 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;
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,nc});c[a[n]].insert((nod){n-ccnt+1,n});
}
}
namespace cdq
{
struct treearray//树状数组
{
const int K=maxn-5;
int tree[maxn];
int lowbit(int x){return x&(-x);}
void updata(int x,int y){for(;x<=K;x+=lowbit(x)) tree[x]+=y;}
void del(int x){for(;x<=K;x+=lowbit(x)) tree[x]=0;}
int getsum(int x){int sum=0;for(;x;x-=lowbit(x)) sum+=tree[x];return sum;}
void clr(){for(int x=1;x<=K;x++) tree[x]=0;}
}T;
int srt[maxn];
inline bool cmp1(int a,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||L==R) return ;
int mid=(L+R)>>1;
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) T.updata(md[j].pos,md[j].val),j++;
qr[i].ans+=T.getsum(qr[i].r)-T.getsum(qr[i].l-1);
}
for(int i=l1+1;i<=mid1;i++) T.del(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++)//对于初始的颜色不进行 cdq
{
while(j<=n&&pre[srt[j]]<qr[i].l) T.updata(srt[j],1),j++;
qr[i].ans+=T.getsum(qr[i].r)-T.getsum(qr[i].l-1);
}
T.clr();
//cdq 中的贡献一定是修改给予的
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()
{
preview::prew();cdq::mainsolve();
}