请问本题现在还能用动态开点线段树过吗?
查看原帖
请问本题现在还能用动态开点线段树过吗?
754444
tamamocross楼主2023/10/31 18:32

我这么写的,TLE了

#include<iostream>
using namespace std;
const int Max=3e5+1;
int tot;
struct node{
	int l,r;
	int lson,rson;
	int sum,tag;
}T[33*Max];
void push_down(int p){
	if(T[p].l==T[p].r){
		return;
	}
	int mid=(T[p].l+T[p].r)>>1,l=T[p].l,r=T[p].r;
	//cout<<"pd"<<p<<" "<<T[p].tag<<" "<<l<<" "<<r<<endl;
	if(!T[p].lson){
		T[p].lson=++tot;T[tot].l=l;T[tot].r=mid;T[tot].sum=mid-l+1;
		T[p].rson=++tot;T[tot].l=mid+1;T[tot].r=r;T[tot].sum=r-mid;
	}
	if(T[p].tag==1){
		T[T[p].lson].sum=0;T[T[p].rson].sum=0;
	}else if(T[p].tag==2){
		T[T[p].lson].sum=mid-l+1;T[T[p].rson].sum=r-mid;
	}
	if(T[p].tag){
		T[T[p].lson].tag=T[p].tag;T[T[p].rson].tag=T[p].tag;
	}
	T[p].tag=0;
}
void push_up(int x){	
	T[x].sum=T[T[x].lson].sum+T[T[x].rson].sum;	
	//cout<<"pup"<<T[x].l<<" "<<T[x].r<<" "<<T[x].sum<<" "<<T[T[x].lson].sum<<" "<<T[T[x].rson].sum<<endl;
}
void print(int p){
	//cout<<T[p].l<<" "<<T[p].r<<" "<<T[p].tag<<" "<<T[p].sum<<endl;
	if(T[p].lson){
		print(T[p].lson);
	}
	if(T[p].rson){
		print(T[p].rson);
	}
}
void modify(int p,int l,int r,int opt){
	int s=T[p].tag;	
	push_down(p);	
	if(l<=T[p].l&&T[p].r<=r){		
	//	cout<<"modi"<<T[p].l<<" "<<T[p].r<<" "<<s<<endl;
		if(opt==2){
			T[p].sum=T[p].r-T[p].l+1;
		}else{
			T[p].sum=0;
		}
		T[p].tag=opt;
		return;				
	}
	int mid=(T[p].l+T[p].r)>>1;
	if(mid>=l){
		modify(T[p].lson,l,r,opt);
	}
	if(mid<r){
		modify(T[p].rson,l,r,opt);
	}	
	push_up(p); 
}

int main(){
    ios::sync_with_stdio(0);
	int n,m;
	cin>>n>>m;
	T[++tot].l=1;T[tot].r=n;T[tot].sum=n;
	for(int i=1;i<=m;i++){
		int l,r,opt;
		cin>>l>>r>>opt;
		modify(1,l,r,opt);
		cout<<T[1].sum<<'\n';
		//print(1);
	}	
} 
/*
4
2
1 2 1
1 1 2
*/
2023/10/31 18:32
加载中...