进食后人
查看原帖
进食后人
500542
lvyongfeng楼主2025/7/22 22:16

1. 我饿了

2. 不开long long 见祖宗

3. 线段树数组得开到8倍

4. 可能因宏定义(#define)大量调用从而TLE

5. 若以上都没有那大抵是你漏了什么(比如下传?

6. 太久没打手生,所以以上我全犯了

7. 综上所述,我是个**

8. 我真的饿了,所以来进食后人

最后贴上我的代码

#include<bits/stdc++.h>
#define int long long  //你猜为什么是define
#define ls(a)	(a << 1)
#define rs(a)	(a << 1 | 1)
#define md(a, b)	((a + b) >> 1)  //侥幸没TLE
using namespace std;
const int N = 2e5 + 10, inf = INT_MAX;
int minn[N << 3], v[N << 3], tag[N << 3], a[N << 3]; //这里一开始没开到这么大

int read(){
	int sign = 1, num = 0;
	char c = getchar();
	while(c  < '0' || c > '9'){
		if(c == '-')	sign = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		num  = (num << 3) + (num << 1) + (c ^ 48);
		c = getchar();
	}
	return sign * num;
}

void pushup(int u){
	minn[u] = min(minn[ls(u)], minn[rs(u)]);
	v[u] = v[ls(u)] + v[rs(u)];
}

void addtag(int u, int pl, int pr, int o){
	tag[u] += o;
	v[u] += o * (pr - pl + 1);
	minn[u] += o;
}

void pushdown(int u, int pl, int pr){
	if(tag[u]){
		int mid = md(pl, pr);
		addtag(ls(u), pl, mid, tag[u]);
		addtag(rs(u), mid + 1, pr, tag[u]);
		tag[u] = 0;
	}
}

void build(int l, int r, int u){
	tag[u] = 0;
	if(l == r){
		minn[u] = v[u] = a[l];
		return;
	}
	int mid = md(l, r);
	build(l, mid, ls(u));
	build(mid + 1, r, rs(u));
	pushup(u);
}

void update(int l, int r, int pl, int pr, int u, int o){
	if(l >= pl && r <= pr){
		addtag(u, l, r, o);
		return;
	}
	pushdown(u, l, r);
	int mid = md(l, r);
	if(pl <= mid)	update(l, mid, pl, pr, ls(u), o);
	if(pr > mid)	update(mid + 1, r, pl, pr, rs(u), o);
	pushup(u);
}

int query_min(int l, int r, int pl, int pr, int u){
	if(r < pl || l > pr)	return inf;
	if(l >= pl && r <= pr){
		return minn[u];
	}
	pushdown(u, l, r);  // 忘记下传
	int mid = md(l, r);
	return min(query_min(l, mid, pl, pr, ls(u)), query_min(mid + 1, r, pl, pr, rs(u)));
}

int query_v(int l, int r, int pl, int pr, int u){
	if(l >= pl && r <= pr){
//		printf("%d ", u);
		return v[u];
	}
	pushdown(u, l, r);
	int ans = 0, mid = md(l, r);
	if(pl <= mid)	ans += query_v(l, mid, pl, pr, ls(u));
	if(pr > mid)	ans += query_v(mid + 1, r, pl, pr, rs(u));
	return ans;
}
signed main(){
//	freopen("4392_4.in", "r", stdin);
//	freopen("2.out", "w", stdout);  //调完freopen忘记删了, WA了一次
	int n, q;
	n = read(), q = read();
	for(int i = 1; i <= n; i++){
		a[i] = read();
	}
	build(1, n, 1);
	for(int i = 1; i <= q; i++){
		char c;
		int x, y;
		scanf("%c", &c);
		x = read(), y = read();
		if(c == 'M'){
			int ans = query_min(1, n, x, y, 1);
			printf("%lld\n", ans);
		}
		if(c == 'P'){
			int z;
			z = read();
			update(1, n, x, y, 1, z);
		}
		if(c == 'S'){
			int ans = query_v(1, n, x, y, 1);
			printf("%lld\n", ans);
		}
	}
	return 0;
}

总结,听取WA声一片

2025/7/22 22:16
加载中...