动态开点线段树求助卡常 TLE on #18
查看原帖
动态开点线段树求助卡常 TLE on #18
724648
light_searcher楼主2024/8/25 10:59

现在这题用动态开点线段树还能过吗

#include<bits/stdc++.h>
#define il inline
using namespace std;
const int N=9e6+5;
int n,q,cnt=1,sum[N],S[N],ls[N],rs[N];
il int read(){ 
	int x=0;
	char s=getchar();
	while(s<'0'||s>'9') s=getchar();
	while(s>='0'&&s<='9'){
		x=x*10+s-'0';
		s=getchar();
	}
	return x;
}
il void write(int x){
	if(x>9) write(x/10);	
	putchar(x%10+'0');
}
il void push_down(int x,int cntl,int cntr){
	if(~S[x]){
		if(!ls[x]) ls[x]=++cnt;
		if(!rs[x]) rs[x]=++cnt;
		S[ls[x]]=S[rs[x]]=S[x];
		sum[ls[x]]=cntl*S[x];
		sum[rs[x]]=cntr*S[x];
		S[x]=-1;
	}
}
il void change(int &x,int l,int r,int L,int R,int v){
	if(!x) x=++cnt;
	if(l>=L&&r<=R){
		S[x]=v;
		sum[x]=(r-l+1)*v;
		return;
	}
	int mid=(l+r)>>1;
	push_down(x,mid-l+1,r-mid);
	if(L<=mid) change(ls[x],l,mid,L,R,v);
	if(R>mid) change(rs[x],mid+1,r,L,R,v);
	sum[x]=sum[ls[x]]+sum[rs[x]];
}
il void modify(int x,int l,int r,int L,int R,int v){
	change(x,l,r,L,R,v);
}
int main(){
	n=read(),q=read();
	memset(S,-1,sizeof(S));
	modify(1,1,n,1,n,1);
	for(int l,r,k;q;--q){
		l=read(),r=read(),k=read();
		modify(1,1,n,l,r,k-1);
		write(sum[1]),putchar('\n');
	}
	return 0;
}
2024/8/25 10:59
加载中...