为何TLE on #21
查看原帖
为何TLE on #21
372498
bbbzzx楼主2025/1/18 16:46

未知原因被卡

#include<bits/stdc++.h>
//#define int long long
#define db double
#define inf 1e18
#define gc getchar
#define pc putchar
#define rg register
using namespace std;
inline int lowbit(int x){return x&-x;}
inline int read(){
	int x=0,f=1;
	char ch=gc();
	while(!isdigit(ch)){
		if(ch=='-') f=-f;
		ch=gc();
	}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=gc();
	return x*f;
}
inline void write(int x){
	if(x<0) pc('-'),x=-x;
	if(x>9) write(x/10);
	pc(x%10+'0');
}
const int MAXN=(3e5+5)*50;
int n,q,cnt=1,root=1;
struct SGT{
	int lson,rson;
	int lazy=-1,sum;
}tree[MAXN];
void pushup(int i){
	tree[i].sum=tree[tree[i].lson].sum+tree[tree[i].rson].sum;
}
void pushdown(int i, int l, int r){
	if(tree[i].lazy!=-1){
		if(!tree[i].lson) tree[i].lson=++cnt;
		if(!tree[i].rson) tree[i].rson=++cnt;
		int mid=l+r>>1;
		tree[tree[i].lson].lazy=tree[tree[i].rson].lazy=tree[i].lazy;
		tree[tree[i].lson].sum=(mid-l+1)*tree[i].lazy;
		tree[tree[i].rson].sum=(r-mid)*tree[i].lazy;
		tree[i].lazy=-1;
	}
}
void update(int &i, int l, int r, int ql, int qr, int k){
	if(!i) i=++cnt;
	if(l>=ql&&r<=qr){
		tree[i].sum=(r-l+1)*k;
		tree[i].lazy=k;
		return;
	}
	pushdown(i,l,r);
	int mid=l+r>>1;
	if(ql<=mid) update(tree[i].lson,l,mid,ql,qr,k);
	if(qr>mid) update(tree[i].rson,mid+1,r,ql,qr,k);
	pushup(i);
}
signed main(){
	//n=read(),q=read();
	scanf("%d%d",&n,&q);
	int l,r,k;
	while(q--){
		//l=read(),r=read(),k=read();
		scanf("%d%d%d",&l,&r,&k);
		k&=1;
		update(root,1,n,l,r,k);
		printf("%d\n",n-tree[root].sum);
	}
	return 0;
}
2025/1/18 16:46
加载中...