526互联

[Ynoi2016] 镜中的昆虫

发布时间 2023-05-04 21:36:32作者: _Youngxy

[Ynoi2016] 镜中的昆虫

P4690 [Ynoi2016] 镜中的昆虫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

您正在欣赏 galgame 的 HS，然后游戏崩溃了，于是您只能做数据结构题了：

维护一个长为 \(n\) 的序列 \(a_i\)，有 \(m\) 次操作。

  1. 将区间 \([l,r]\) 的值修改为 \(x\)。

  2. 询问区间 \([l,r]\) 出现了多少种不同的数，也就是说同一个数出现多次只算一个。

输入格式

第一行两个整数 \(n,m\)。

第二行 \(n\) 个整数表示 \(a_i\)。

后面 \(m\) 行每行为 \(1\ l\ r\ x\) 或者 \(2\ l\ r\) ，分别表示修改和询问。

输出格式

对于每个询问，输出一个数表示答案。

SOLUTION

题解 P4690 【[Ynoi2016]镜中的昆虫】 - shadowice1984 的博客 - 洛谷博客 (luogu.com.cn)

（要是没有get what meaning it is建议配合代码和注释食用）

CODE

struct qes{int op,l,r,x;}q[N];
struct qry{int t,l,r,ans;}Q[N];
inline bool operator<(qry x,qry y){
	return x.l<y.l;
}
inline bool cmp(qry x,qry y){
	return x.t<y.t;
}
inline bool cp1(int x,int y){
	return pre[x]<pre[y];
}
struct poss{int t,pos,pre,val;}P[10*N];
inline bool operator<(poss x,poss y){
	return x.pre<y.pre;
} 
inline void modify(int i,int p){
	if(npre[i]==p)return ;
	P[++tp1]={++cnt,i,npre[i],-1};
	P[++tp1]={++cnt,i,npre[i]=p,1};
}

namespace Set{
	struct data{int l,r,x;};
	inline bool operator<(data a,data b){
		return a.r<b.r;
	}
	set<data>s;
	struct node{int l,r;};
	inline bool operator<(node x,node y){
		return x.r<y.r;
	}
	set<node>c[2*N];
	set<int>cg; 
	inline void splt(int mid){//将一个节点拆成两个节点
		auto p=*(s.lower_bound((data){0,mid,0}));
		if(mid==p.r)return ;
		s.erase(p);
		s.insert({p.l,mid,p.x});
		s.insert({mid+1,p.r,p.x});
		c[p.x].erase({p.l,p.r});
		c[p.x].insert({p.l,mid});
		c[p.x].insert({mid+1,p.r});
	}
	inline void ins(data p){
		s.insert(p);
		auto it=c[p.x].insert({p.l,p.r}).fir;
		it++;
		if(it!=c[p.x].end())cg.insert(it->l);
	}
	inline void del(set<data>::iterator it){
		cg.insert(it->l);
		auto it1=c[it->x].find((node{it->l,it->r}));
		auto it2=it1;
		it2++;
		if(it2!=c[it->x].end()){
			cg.insert(it2->l);
		}
		c[it->x].erase(it1);
		s.erase(it);
	}
	inline void stv(int l,int r,int x){//区间赋值 
		if(l!=1)splt(l-1);
		splt(r);//处理可能会是交集的区间 (分成变/没变两部分) 
		int p=l;
		while(p!=r+1){//删除包含的区间 
			auto it=s.lower_bound((data){0,p,0});
			p=it->r+1;
			del(it);
		}
		ins({l,r,x}); 
		//扫一遍set处理所有变化的pre值
		for(auto it=cg.begin();it!=cg.end();it++){
			auto it1=s.lower_bound({0,*it,0});
			if(*it!=it1->l) modify(*it,*it-1);//不是左端点 
			else{//左端点 
				auto it2=c[it1->x].lower_bound({0,*it});
				if(it2!=c[it1->x].begin()){
					it2--;
					modify(*it,it2->r);//it2.r是pre前缀 
				}else{//无前缀 
					modify(*it,0);
				}
			} 
		}
		cg.clear();
	}
	inline void insert(){//set插入连续一段 
		int now=a[1],ct=1;
		for(int i=2;i<=n;i++){
			if(now!=a[i]){
				s.insert({i-ct,i-1,now});//st ed val
				c[now].insert({i-ct,i-1});
				now=a[i];			
				ct=1;
			}else ct++;
		}
		s.insert((data){n-ct+1,n,a[n]});
		c[a[n]].insert({n-ct+1,n}); 
	}
}
struct TA{//tree-arrey 
	int c[N];
	inline int lowbit(int x){
		return x&(-x);
	}
	inline void C(int x,int t){
		while(x<=n){
			c[x]+=t;
			x+=lowbit(x);
		}
	}
	inline void D(int x){//delete
		while(x<=n){
			c[x]=0;
			x+=lowbit(x);
		}
	}
	inline int Q(int x){//query
		int res=0;	
		while(x){
			res+=c[x];
			x-=lowbit(x);
		}
		return res;
	}
	inline void clear(){
		for(int i=1;i<=n;i++){
			c[i]=0;
		}
	}
}ta;
inline void CDQ(int l1,int r1,int l2,int r2,int L,int R){
	if(l1==r1||l2==r2)return ;
	int mid=(L+R)>>1;
	int mid1=l1;while(mid1!=r1&&P[mid1+1].t<=mid)mid1++;
	int mid2=l2;while(mid2!=r2&&Q[mid2+1].t<=mid)mid2++;
	CDQ(l1,mid1,l2,mid2,L,mid);CDQ(mid1,r1,mid2,r2,mid,R);
	///做了(l,mid)的修改&&(mid+1,r)的询问 
	if(l1!=mid1&&mid2!=r2){
		sort(P+l1+1,P+mid1+1);//按pre排序 
		sort(Q+mid2+1,Q+r2+1);//按l排序 
		for(int i=mid2+1,j=l1+1;i<=r2;i++){
			while(j<=mid1&&P[j].pre<Q[i].l)ta.C(P[j].pos,P[j].val),j++;//pre<l的
			//由于Q按照l从小到大，所以操作之后（将pre<l的操作更新）
			Q[i].ans+=ta.Q(Q[i].r)-ta.Q(Q[i].l-1);//(l,r)内pre<l的个数 
		}
		for(int i=l1+1;i<=mid1;i++){
			ta.D(P[i].pos);//还原 (清0) 
		}
	}
}
int main(){
	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++){
		int op,l,r,x=0;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			scanf("%d",&x);
			mp[x]=1;
		}
		q[i]={op,l,r,x}; 
		
	}
	auto it=mp.begin(),itt=it;++itt;
	while(itt!=mp.end()){
		itt->sec+=it->sec;
		it++,itt++;
	}
	for(int i=1;i<=n;i++){
		a[i]=mp[a[i]];
	} 
	for(int i=1;i<=m;i++){
		if(q[i].op==1)q[i].x=mp[q[i].x]; 
	}
	for(int i=1;i<=n;i++){
		npre[i]=pre[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	Set::insert();
	for(int i=1;i<=m;i++){
		if(q[i].op==1){
			Set::stv(q[i].l,q[i].r,q[i].x);
		}else{
			Q[++tp2]={++cnt,q[i].l,q[i].r,0};
		}
	} 
	sort(Q+1,Q+1+tp2);
	for(int i=1;i<=n;i++){
		srt[i]=i; 
	}
	sort(srt+1,srt+1+n,cp1);
	//初始计算 
	for(int i=1,j=1;i<=tp2;i++){
		while(j<=n&&pre[srt[j]]<Q[i].l) ta.C(srt[j],1),j++;
		Q[i].ans+=ta.Q(Q[i].r)-ta.Q(Q[i].l-1);
	}
	ta.clear();
	sort(Q+1,Q+tp2+1,cmp);
	CDQ(0,tp1,0,tp2,0,cnt);
	sort(Q+1,Q+tp2+1,cmp);
	for(int i=1;i<=tp2;i++){
		printf("%d\n",Q[i].ans);
	}
	return 0;
}

（先占个坑?）