求助帖（火车线路短路，只有80分）

问题讨论区 提高段
1

@俞天行 帮我

#include <bits/stdc++.h>
using namespace std;
const int N=6e4+10;

int n,m,q;
struct tree{
	int sum,add;//sum为和，add为懒标记
	int l,r;//保存区间 
}tg[N*4];//开4倍空间

#define left x,mid
#define right mid+1,y

void build(int p,int x,int y);
void do_add(int p,int x,int y,int k);
void pushdown(int pos);
int get_sum(int p,int x,int y);
//声明函数

void build(int p,int x,int y){
	tg[p].l=x,tg[p].r=y;
	tg[p].sum=tg[p].add=0;
	if(x>=y) return ;
	
	int mid=x+y>>1;
	//分左右区间建树
	build(p<<1,left),build((p<<1)|1,right);
} 

void do_add(int p,int x,int y,int k){
	if(x<=tg[p].l&&tg[p].r<=y){
		tg[p].sum+=k,tg[p].add+=k;
		return ;
	}
	
	pushdown(p);//更新懒标记
	int mid=tg[p].l+tg[p].r>>1;
	if(x<=mid) do_add(p<<1,x,y,k);
	if(y>mid) do_add((p<<1)|1,x,y,k);
	
	tg[p].sum=max(tg[p<<1].sum,tg[(p<<1)|1].sum);
}

void pushdown(int pos){
	if(tg[pos].add){
		//如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
        tg[pos<<1].sum+=tg[pos].add,tg[(pos<<1)|1].sum+=tg[pos].add;
        tg[pos<<1].add+=tg[pos].add,tg[(pos<<1)|1].add+=tg[pos].add;
		tg[pos].add=0;
	}
	return ;
}

int get_sum(int p,int x,int y){
    if(x<=tg[p].l&&tg[p].r<=y) return tg[p].sum;
    //[x,y]为查询区间,[tg[p].l,tg[p].r]为当前节点包含的区间,p为当前节点的编号   
	
    pushdown(p);
    int ans=0,mid=tg[p].l+tg[p].r>>1;
    if(x<=mid) ans=max(ans,get_sum(p<<1,x,y));
    if(y>mid) ans=max(ans,get_sum((p<<1)|1,x,y));
    
    return ans;
}

int main(){
	cin>>n>>m>>q;
	build(1,1,n);//建树 
	while(q--){
		int l,r,k;
		cin>>l>>r>>k;
		int res=get_sum(1,l,r);
		if(res+k>m)
			cout<<"N"<<endl; 
		else{
			do_add(1,l,r-1,k);
			cout<<"T"<<endl;			
		}
	}
}

image

2

@金杭东 @稻叶昙 @俞天行 救救孩子

3

这又是啥题？

4

新课的题

5

@吴梓峤 题面看不见

6

？
我不是发截图了吗？

7

洛谷上有

8

@俞天行

9

@王天皓1 快来！！！help me

10

@360病毒

11

不是你不 update 的吗

12

吐了

13

啥意思？

14 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5;
int c, s, r;
int a[N + 5], tree[(N + 5) * 4], lzytag[(N + 5) * 4];
int ls(int x) { return x << 1;}
int rs(int x) { return x << 1 | 1;}
void pushup(int x) {
	tree[x] = max(tree[ls(x)], tree[rs(x)]);
}
void addtag(int x, int xl, int xr, int val) {
	lzytag[x] += val;
	tree[x] += val;
}
void pushdown(int x, int xl, int xr) {
	if(lzytag[x] != 0) {
		int mid = (xl + xr) / 2;
		addtag(ls(x), xl, mid, lzytag[x]); addtag(rs(x), mid + 1, xr, lzytag[x]);
		lzytag[x] = 0;
	}
}
void update(int l, int r, int x, int xl, int xr, int val) {
	if (l <= xl && xr <= r) {
		addtag(x, xl, xr, val);
		return ;
	}
	pushdown(x, xl, xr);
	int mid = (xl + xr) / 2;
	if (l <= mid) update(l, r, ls(x), xl, mid, val);
	if (r > mid) update(l, r, rs(x), mid + 1, xr, val);
	pushup(x);
}
signed main() {
	cin >> c >> s >> r;
	while (r--) {
		int o, d, n;
		cin >> o >> d >> n;
		update(o, d - 1, 1, 1, c, n);
		if (tree[1] > s) {
			update(o, d - 1, 1, 1, c, -n);
			cout << "N\n";
		} else cout << "T\n";
	}
	return 0;
}

有没有巨佬愿意帮忙卡常的？

15

改为：

        do_add(1,l,r-1,k);
		int res=get_sum(1,l,r);
		if(res>m){
            do_add(1,l,r-1,-k);
			cout<<"N"<<endl; 
		}else{
			cout<<"T"<<endl;			
		}
16

测试能过，求解决方案

17

这样会TLE

18

但 xyd 水数据 AC 了啊

19

呃，但不行啊

20

你A几题了