[Ynoi2016] 镜中的昆虫
正式而卤蛋
·
·
题解
祭念成功搞了我一天的题。
题意
维护长度为 n 一个序列的序列，m 次操作，区间赋值 或 查询区间不同权值数 。
## 题解
其实在黑题中思维难度较低，~~但这跟我不会又有什么关系呢~~。
首先这个问题看上去不太可做，我们 **由简到难** 考虑，就先考虑如果是单点修改怎么做。首先统计答案是常见套路了，维护一个 $pre$ ，查询 $pre_i<l,l\le i\le r$ 的 $i$ 的个数，就是一个经典的二维偏序问题，也就是转换成一个 **二维数点** 。
静态的随便乱搞都行。
动态的话可以用一个线段树套 $set$ 维护就行（仿佛被卡空间了。。。~~忘记二维线段树这种愚蠢的东西吧~~）。
但我们考虑 $\mathrm{cdq}$ 分治能不能做，难点在于处理修改，我们考虑一个点的影响的变化，一开始是在这个点的位置 $+1$ ，后来把它修改了可以理解为之前点的位置 $-1$ ，新的点 $+1$ ，也可以理解为加入两个权值为 $-1,1$ 的点，于是修改就变成了两个点，单点修改问题就做完了。
考虑原问题，当时做的时候手玩一下区间赋值发现这个区间的点成了一条斜率为 $1$ 的线，~~我真是个人才~~。然后你发现区间修改到最后变的点只有左右两端点，即一段覆盖两次后中间的就不变了，于是其实就是规模为 $n+m$ 的单点修改，问题 $\mathrm{GG}$ 。
于是你就可以把这道题切掉了。。。
---
## Code
**~~后面讲的是实现，可以不用看了。~~**
其实说实话如果做过 $\mathrm{cdq}$ 的模板，这道题这样口胡一下最多 $5$ 分钟就能明白，但是对我这样的蒟蒻最大的难点就是这道题的实现，折磨了我一整天。我写这篇题解也主要是总结一下这方面的思考。
首先要分出主要步骤：1.把所有加点和询问预处理下来。2. $\mathrm{cdq}$ 分治算答案。 显然后者是个板子，我们着重考虑前者。
接着考虑我们的目的，我们想把修改和询问按顺序找出来保证时间的维度，所以这个过程要动态的做。所以考虑每到一个区间赋值怎么把这些要更新的点找出来，即是看哪些点受到影响，但实际做的时候为了方便我们把 **可能更新** 的点找出来做。
我们把赋值的区间看成一个一个不同权值的块加入 $\mathrm{set}$ 里维护（这样才能保证复杂度和可操作），那么对于当前赋值区间内的所有块，它们都会被删除，并且左端点的 $pre$ 都有可能被修改，如果越过这个区间不妨把区间分成两部分。其次这个加入的区间的左端点会修改，其次还有就是在它后面的与它权值相同的块的左端点会被修改，发现这个还需要另一个 $\mathrm{set}$ 维护这个权值的所有区间的位置，同时这个也就能维护对于最后找到的可能要更新的点的更新查询，问题就基本做完了。
初始化就假设初始序列是已有状态，加入两个 $\mathrm{set}$ 里就行了。
**还有 $\mathrm{cdq}$ 的实现可以每个类型各维护一个范围，变量名就不会混了，算是一个很不错的技巧。但是注意边界的时候仍然要排序（具体看代码）。**
注意数组大小 ~~（你可能 $75$ 分 WA 了是因为数组开小了。。。）~~
```
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10,M=1e5+10;
int n,m,a[N],opt[M],l[M],r[M],x[M],b[N+M],uni,ans[M];
int pre[N],lst[N+M],cnt;
struct Node{
int t,x,y,v; // x -> pre , y -> i
friend bool operator < (const Node &X,const Node &Y){
return X.x<Y.x;
}
}o[N*10],oo[N*10]; int cntn; // 不知道开多少就多开吧
struct Que{
int t,l,r,id;
friend bool operator < (const Que &X,const Que &Y){
return X.l<Y.l;
}
}q[M],qq[M]; int cntq;
int bit[N];
inline int lowbit(const int x){
return x&-x;
}
inline void add(int x,const int v){
if(!x) return;
while(x<=n) bit[x]+=v,x+=lowbit(x);
}
inline int sum(int x){
if(!x) return 0;
int res=0; while(x) res+=bit[x],x-=lowbit(x); return res;
}
#define mid ((l+r)>>1)
inline void cdq(const int l,const int r,const int ln,const int rn,const int lq,const int rq){ // 不用混在一起的写法
if(rn<ln||rq<lq){
if(ln<=rn) sort(o+ln,o+rn+1);
if(lq<=rq) sort(q+lq,q+rq+1);
return;
}
int mn=ln; while(mn<=rn&&o[mn].t<=mid) ++mn;
int mq=lq; while(mq<=rq&&q[mq].t<=mid) ++mq;
cdq(l,mid,ln,mn-1,lq,mq-1),cdq(mid+1,r,mn,rn,mq,rq);
int i=ln,j=mq; for(;j<=rq;j++){
while(i<=mn-1&&o[i].x<q[j].l) add(o[i].y,o[i].v),++i;
ans[q[j].id]+=sum(q[j].r)-sum(q[j].l-1);
} while(j<=rq) ans[q[j].id]+=sum(q[j].r)-sum(q[j].l-1),++j;
for(j=ln;j<i;j++) add(o[j].y,-o[j].v);
merge(o+ln,o+mn,o+mn,o+rn+1,oo+ln),merge(q+lq,q+mq,q+mq,q+rq+1,qq+lq);
for(int i=ln;i<=rn;i++) o[i]=oo[i]; for(int i=lq;i<=rq;i++) q[i]=qq[i];
}
#undef mid
inline void modify(const int i,const int pre){ // 修改 i 位置的 pre
if(::pre[i]==pre) return;
o[++cntn]=Node{++cnt,::pre[i],i,-1},o[++cntn]=Node{++cnt,::pre[i]=pre,i,1};
}
set<int> upd; // 可能需要更新的点
struct Kuai{
int l,r,x;
friend inline bool operator < (const Kuai &X,const Kuai &Y){
return X.l<Y.l;
}
}; // 操作分出的块
set<Kuai> s;
typedef set<Kuai>::iterator Its; Its its;
struct Col{
int l,r;
friend inline bool operator < (const Col &X,const Col &Y){
return X.l<Y.l;
}
}; // 权值的位置区间
set<Col> c[N+M]; // 用来查询相同权值区间的位置关系
typedef set<Col>::iterator Itc; Itc itc;
inline void split(const int pos){ // 在 pos 处拆块（ pos 拆到后面）
its=s.lower_bound(Kuai{pos,0,0}); Kuai now=*its; if(now.l==pos) return;
now=*(--its); // 注意是前面那块
s.erase(its),s.insert(Kuai{now.l,pos-1,now.x}),s.insert(Kuai{pos,now.r,now.x}); // 发现这几个地方都不用特判
c[now.x].erase(Col{now.l,now.r}),c[now.x].insert(Col{now.l,pos-1}),c[now.x].insert(Col{pos,now.r});
}
inline void delet(const Its &it){ // 删除一块
Kuai now=*it; upd.insert(now.l);
itc=c[now.x].find(Col{now.l,now.r});
++itc; if(itc!=c[now.x].end()) upd.insert((*itc).l); // 注意 end()-1 是最后一位
s.erase(it),c[now.x].erase(--itc);
}
inline void insert(const Kuai now){ // 插入一段
s.insert(now); upd.insert(now.l);
itc=c[now.x].insert(Col{now.l,now.r}).first;
++itc; if(itc!=c[now.x].end()) upd.insert((*itc).l);
}
inline void waxxx(const int l,const int r,const int x){ // 不知道函数名什么意思
split(l); if(r+1<=n) split(r+1);
int pos=l; while(pos<=r) its=s.lower_bound(Kuai{pos,0,0}),pos=(*its).r+1,delet(its);
insert(Kuai{l,r,x});
for(int now:upd){ its=s.lower_bound(Kuai{now,0,0});
if(now!=(*its).l) modify(now,now-1); // 在块中就不用找了
else{ itc=c[(*its).x].lower_bound(Col{now,0});
if(itc==c[(*its).x].begin()) modify(now,0);
else modify(now,(*--itc).r);
}
} upd.clear();
}
inline bool cmp(const int X,const int Y){
return pre[X]<pre[Y];
}
inline void pre_work(){
int pre_i=1,pre_a=a[1]; pre[1]=lst[a[1]],lst[a[1]]=1; // pr 预处理临时
for(int i=2;i<=n;i++){
if(pre_a!=a[i]){
s.insert(Kuai{pre_i,i-1,pre_a}),c[pre_a].insert(Col{pre_i,i-1});
pre_i=i,pre_a=a[i];
} pre[i]=lst[a[i]],lst[a[i]]=i;
} s.insert(Kuai{pre_i,n,pre_a}),c[pre_a].insert(Col{pre_i,n});
// 加入一开始的信息
for(int i=1;i<=n;i++) o[++cntn]=Node{++cnt,pre[i],i,1};
for(int i=1;i<=m;i++){
if(opt[i]==1) waxxx(l[i],r[i],x[i]);
else q[++cntq]=Que{++cnt,l[i],r[i],i};
}
// 最关键的处理修改的操作
}
#define gc getchar()
#define in read()
inline int read(){
int f=1,k=0; char cp=gc; while(cp!='-'&&(cp<'0'||cp>'9')) cp=gc; if(cp=='-') f=-1,cp=gc;
while(cp>='0'&&cp<='9') k=(k<<3)+(k<<1)+cp-48,cp=gc; return f*k;
}
int main(){
n=in,m=in; for(int i=1;i<=n;i++) b[++uni]=a[i]=in;
for(int i=1;i<=m;i++){ opt[i]=in,l[i]=in,r[i]=in;
if(opt[i]==1) b[++uni]=x[i]=in;
} sort(b+1,b+uni+1),uni=unique(b+1,b+uni+1)-b-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+uni+1,a[i])-b;
for(int i=1;i<=m;i++) x[i]=lower_bound(b+1,b+uni+1,x[i])-b;
// 离散化
pre_work();
// 预处理（最重要的部分）
cdq(1,cnt,1,cntn,1,cntq); //算修改类似于差分的贡献
for(int i=1;i<=m;i++) if(opt[i]==2) cout<<ans[i]<<'\n';
return 0;
}
```