2025寒假专场朱老师题解

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m;
long long a[N];//原序列 
bool vis[N*4];//线段树维护撤销操作 支持区间赋值与单点查询 true表示整个区间要撤销 不用懒标记 true不会变为false  
bool ok[N];//标记每个时刻是否被撤销 
 
long long b[N];//lsh
int tot_f,tot_che,b_tot;
struct Info{
	int id,op,l,r;
	long long t,k;
}f[N];
struct Node{
	long long t,l,r;
}che[N];

void lsh(){
	sort(b+1,b+1+b_tot);
	int len=unique(b+1,b+1+b_tot)-b-1;
	for(int i=1;i<=tot_f;i++)
		f[i].t=lower_bound(b+1,b+1+len,f[i].t)-b;
	for(int i=1;i<=tot_che;i++)
		che[i].t=lower_bound(b+1,b+1+len,che[i].t)-b,
		che[i].l=lower_bound(b+1,b+1+len,che[i].l)-b,
		che[i].r=lower_bound(b+1,b+1+len,che[i].r)-b;//l r也是时间点  
	b_tot=len;//时间线段树的长度 
	 
//	for(int i=1;i<=tot_f;i++){
//		if(f[i].op==2) 
//			printf("%d %d %lld %d %d\n",f[i].id,f[i].op,f[i].t,f[i].l,f[i].r); 
//		else
//			printf("%d %d %lld %d %d %lld\n",f[i].id,f[i].op,f[i].t,f[i].l,f[i].r,f[i].k); 
//	}
}

bool cmp_che(Node x,Node y){
	return x.t>y.t;
}
void update(int p,int l,int r,int pl,int pr){
	if(vis[p]) return;//小优化 已经集体撤销了 不用再撤销一遍  
	if(l<=pl&&pr<=r){
		vis[p]=true;
		return;
	}
	int mid=(pl+pr)>>1;
	if(l<=mid) update(p<<1,l,r,pl,mid);
	if(r>mid) update(p<<1|1,l,r,mid+1,r);
	vis[p]=vis[p<<1]&&vis[p<<1|1];
}
bool query(int p,int k,int pl,int pr){
	if(vis[p]) return true;
	if(pl==pr) return false;
	int mid=(pl+pr)>>1;
	if(k<=mid) return query(p<<1,k,pl,mid);
	else return query(p<<1|1,k,mid+1,pr);
}
void dfs(int p,int pl,int pr){
	if(vis[p]){
		for(int i=pl;i<=pr;i++)
			ok[i]=true;
		return;
	}
	if(pl==pr) return;
	int mid=(pl+pr)>>1;
	dfs(p<<1,pl,mid);
	dfs(p<<1|1,mid+1,pr);
}
void chexiao(){
	sort(che+1,che+1+tot_che,cmp_che);
	for(int i=1;i<=tot_che;i++){
		if(query(1,int(che[i].t),1,b_tot)==true)//该撤销操作被之前的撤销操作撤销了 
			 continue;
		update(1,int(che[i].l),int(che[i].r),1,b_tot);//区间撤销  
	} 
	//遍历整棵树得到每个时间点是否被撤销 记为ok  
	dfs(1,1,b_tot); 
}

bool cmp_f(Info x,Info y){
	return x.t==y.t?x.id<y.id:x.t<y.t;
}
void count_cha(){
	sort(f+1,f+1+tot_f,cmp_f);
	int cnt=0;
	for(int i=1;i<=tot_f;i++)
		if(f[i].op==2&&!ok[int(f[i].t)]) cnt++;
	printf("%d\n",cnt);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++){
		int op;scanf("%d",&op);
		if(op==3){
			++tot_che;
			scanf("%lld%d%d",&che[tot_che].t,&che[tot_che].l,&che[tot_che].r); 
			b[++b_tot]=che[tot_che].t;
		} 
		else{
			++tot_f;
			f[tot_f].id=i,f[tot_f].op=op;
			scanf("%lld%d%d",&f[tot_f].t,&f[tot_f].l,&f[tot_f].r); 
			if(op==1) scanf("%lld",&f[tot_f].k); 
			b[++b_tot]=f[tot_f].t; 
		}
	}
	//离散化 
	lsh(); 
	//处理撤销操作 
	chexiao(); 
	//统计未被撤销的查询次数 
	count_cha();
	return 0;
}