区间数不同的数的个数是个常见的套路，不说了。
考虑这个区间修改怎么办——意味着需要修改一堆数的 $pre$。
假设对于修改前，有一段区间 $[l’,r’],l\leq l’\leq r’\leq r$ ，满足这一段区间中的数都是相同的。那么进行了修改过后，容易发现改变 $pre$ 只有 $pre_{l’},pre_{r”}$ ，这里 $pre_{r”}$ 满足修改前，$pre_{r”}=r’$ 。
接着考虑，如果最开始整个序列有 $n$ 个区间，显而易见的，如果一次修改覆盖到了 $a$ 个完整的区间并且碰到了 $b\leq 2$ 个不完整的区间，那么暴力进行修改的话是 $a+b$ 次修改的，然后区间数就会减去 $a-1$ 。
由于区间数最多减到 $1$，又因为 $b\leq 2$ ，所以其实暴力修改的次数是 $O(n+m)$ 级别的。事实上，最坏情况大概是 $n+2m$ 次修改。
所以拿一个 set 维护一下区间，然后维护 $pre$ 的话用二维线段树即可。
时间复杂度是 $O((n+m)\log n$ ？只有 $10^5$ 所以应该不会被卡常吧？
关于实现：
- 二维线段树：最坏点得跑 $2.7s$ 。（空间 $\log^2$）
- 树状数组 + 动态开点线段树：最坏点 $1.7s$，足以通过 loj 数据。（空间 $\log ^2$）。
-
CDQ + 平衡树：卡住了懒得调。（空间 $\log$）。
- CDQ + 树状数组：最坏点 $0.9s$，足以通过 luogu 数据。（空间 $\log$）。
容易发现 luogu 的空间有毒，甚至不足以开下两个 Node 数组搞 CDQ，所以可以开两个 int 数组维护编号（具体见代码实现）
而且为了加速，这里采用归并排序。
关于代码。
树状数组 + 动态开点线段树：详见提交记录
CDQ + 树状数组：
const int N=1e5+5;
const int M=1e6+5;
int n,m,_,cnt,a[N],id[M],ti[M],ans[N],h[N<<1];
struct Query {int tim,l,r,val,typ,op;} q[M];
namespace ChthollyTree { // {{{ ChthollyTree
#define ins insert
int pre[N],las[N<<1];
struct Node {
int l,r,val;
bool operator < (const Node &kls) const {return r<kls.l;}
};
std::set <Node> seq;
std::set <pii> sta[N<<1];
inline void update(int x,int now) {
q[++cnt]=(Query){cnt,x,-1,pre[x],0,-1},
q[++cnt]=(Query){cnt,x,-1,pre[x]=now,0,1};
}
inline void init() {
lep(i,1,n) {
a[i]=std::lower_bound(h+1,h+1+_,a[i])-h;
q[++cnt]=(Query){cnt,i,-1,pre[i]=las[a[i]],0,1},las[a[i]]=i;
seq.ins((Node){i,i,a[i]}),sta[a[i]].ins(mkp(i,i));
}
lep(i,1,_) sta[i].ins(mkp(0,0));
}
inline void insert(int l,int r,int val) {
std::set <pii>::iterator it2=sta[val].upper_bound(mkp(l,r)),it1=it2; --it2;
if(it1!=sta[val].end()) update(it1->fi,r); update(l,it2->se);
sta[val].ins(mkp(l,r)),seq.ins((Node){l,r,val});
}
inline void erase(int l,int r,int val,int _flag) {
std::set <pii>::iterator it2=sta[val].upper_bound(mkp(l,r)),it1=it2; --it2,--it2;
if(it1!=sta[val].end()) update(it1->fi,it2->se);
if(l!=_flag) update(l,l-1);
sta[val].erase(mkp(l,r)),seq.erase((Node){l,r,val});
}
inline void cut(int l,int r,int val,int pos) {
seq.erase((Node){l,r,val}),sta[val].erase(mkp(l,r));
seq.ins((Node){l,pos,val}),sta[val].ins(mkp(l,pos));
seq.ins((Node){pos+1,r,val}),sta[val].ins(mkp(pos+1,r));
}
inline void split(int L,int R,int val) {
std::set <Node>::iterator it=seq.lower_bound((Node){L,L-1,0});
if(it->l<=L&&R<=it->r) {
int l=it->l,r=it->r,_val=it->val;
if(l<L) cut(l,r,_val,L-1);
if(R<r) cut(L,r,_val,R);
erase(L,R,_val,L);
} else while(it!=seq.end()&&it->l<=R) {
int l=it->l,r=it->r,_val=it->val; ++it;
if(L<=l&&r<=R) erase(l,r,_val,L);
else {
if(l<L&&L<=r&&r<=R) cut(l,r,_val,L-1),erase(L,r,_val,L);
if(L<=l&&l<=R&&R<r) cut(l,r,_val,R),erase(l,R,_val,L);
}
}
insert(L,R,val);
}
} using namespace ChthollyTree; // }}}
// {{{ cdq divide
// {{{ BIT
int res,c[N];
inline int lowbit(int x) {return x&(-x);}
inline void modify(int x,int y) {for(;x<=n;x+=lowbit(x)) c[x]+=y;}
inline int query(int l,int r) {
--l,res=0;
while(r>l) res+=c[r],r-=lowbit(r);
while(l>r) res-=c[l],l-=lowbit(l);
return res;
}
// }}}
void cdq(int l,int r) {
if(l==r) return ;
int mid=(l+r)>>1;
cdq(l,mid),cdq(mid+1,r);
int L=mid+1; lep(i,l,mid) {
while(L<=r&&q[id[L]].val<q[id[i]].val) {
if(q[id[L]].typ) ans[q[id[L]].typ]+=q[id[L]].op*query(q[id[L]].l,q[id[L]].r);
++L;
}
if(!q[id[i]].typ) modify(q[id[i]].l,q[id[i]].op);
}
while(L<=r) {
if(q[id[L]].typ) ans[q[id[L]].typ]+=q[id[L]].op*query(q[id[L]].l,q[id[L]].r);
++L;
}
lep(i,l,mid) if(!q[id[i]].typ) modify(q[id[i]].l,-q[id[i]].op);
int i=l,j=mid+1,t=l;
while(i<=mid&&j<=r) ti[t++]=(q[id[i]].val<q[id[j]].val)?id[i++]:id[j++];
while(i<=mid) ti[t++]=id[i++];
while(j<=r) ti[t++]=id[j++];
lep(i,l,r) id[i]=ti[i];
}
// }}}
int query_cnt,_op[N],_l[N],_r[N],_x[N];
int main() {
IN(n,m);
lep(i,1,n) IN(a[i]),h[++_]=a[i];
lep(i,1,m) {
IN(_op[i],_l[i],_r[i]);
if(_op[i]==1) h[++_]=_x[i]=int(IN);
}
std::sort(h+1,h+1+_); int tmp=_; _=1;
lep(i,2,tmp) if(h[i]!=h[_]) h[++_]=h[i];
init();
lep(i,1,m) {
if(_op[i]==1) split(_l[i],_r[i],std::lower_bound(h+1,h+1+_,_x[i])-h);
if(_op[i]==2) q[++cnt]=(Query){cnt,_l[i],_r[i],_l[i]-1,++query_cnt,1};
}
lep(i,1,cnt) id[i]=i;
cdq(1,cnt);
lep(i,1,query_cnt) printf("%d\n",ans[i]);
return 0;
}
0 条评论