P8856火车线路

#include<bits/stdc++.h>
using namespace std;
struct node{
	int sum,lazy;
}tree[240005];
int a[60005];
void pushup(int x){
	tree[x].sum=max(tree[x<<1].sum,tree[x<<1|1].sum);
}
void pushdown(int x,int l,int r){
	if(tree[x].lazy){
	int mid=(l+r)>>1;
	tree[x<<1].lazy+=tree[x].lazy;
	tree[x<<1|1].lazy+=tree[x].lazy;
	tree[x<<1|1].sum+=tree[x].lazy;
	tree[x<<1|1].sum+=tree[x].lazy;
	tree[x].lazy=0; 	
	}
}
void build(int l,int r,int x){
	if(l==r){
		tree[x].sum=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	pushup(x);
}
void update(int x,int l,int r,int from,int to,int v){
	if(l>=from&&r<=to){
		tree[x].lazy+=v;
		tree[x].sum+=v;
		return ;
	}
	pushdown(x,l,r);
	int mid=(l+r)>>1;
	if(from<=mid){
		update(x<<1,l,mid,from,to,v);	
	}
	if(to>mid){
		update(x<<1|1,mid+1,r,from,to,v);
	}
	pushup(x);
}
int query(int x,int l,int r,int from,int to){
	if(l>=from&&r<=to){
		return tree[x].sum;
	}
	pushdown(x,l,r);
	int maxx=-0x3f3f3f3f;
	int mid=(l+r)>>1;
	if(from<=mid)  maxx=max(maxx,query(x<<1,l,mid,from,to));
	if(to>mid)  maxx=max(maxx,query(x<<1|1,mid+1,r,from,to));
	return maxx;
}
int main(){
	int c,s,r;
	scanf("%d%d%d",&c,&s,&r);
	build(1,c,1);
	for(int i=1;i<=r;i++){
		int o,d,n;
		scanf("%d%d%d",&o,&d,&n);
		update(1,1,c,o,d-1,n);
		if(query(1,1,c,o,d-1)>s){
			printf("N\n");
			update(1,1,c,o,d-1,-n);
		}
		else{
			printf("T\n");
		}
	}
	return 0;
}