大佬求助!这道题我样例过了为什么0分
查看原帖
大佬求助!这道题我样例过了为什么0分
1409511
EverNight37楼主2025/8/30 22:14

有人点进来吗,那就帮我调可以吗qwq,另外悬4关求调

#include<bits/stdc++.h>
#define int long long 
#define sum(u) w[u].sum
#define max1(u) w[u].max1
#define max2(u) w[u].max2
#define maxh(u) w[u].maxh
#define cnt(u) w[u].maxnum
#define l(u) w[u].l
#define r(u) w[u].r
#define tag1(u) w[u].tag1
#define tag2(u) w[u].tag2
#define tag3(u) w[u].tag3
#define tag4(u) w[u].tag4
#define int long long
#define inf 1e9
using namespace std;
struct node {
	int sum, max1, max2, maxh, maxnum;
	int l, r, tag1, tag2, tag3, tag4;
	void clear() {
		tag1 = tag2 = tag3 = tag4 = 0;
	}
}w[2000005];
int a[5000005], n, m;
bool InRange(int l, int r, int L, int R) {
	return (l >= L) && (r <= R);
}
bool OutofRange(int l, int r, int L, int R) {
	return (r < L) || (l > R);
}
void pushup(int u) {
	int ls = u * 2, rs = u * 2 + 1;
	sum(u) = sum(ls) + sum(rs);
	max1(u) = max(max1(ls), max1(rs));
	maxh(u) = max(maxh(ls), maxh(rs)); 
	if(max1(ls) == max1(rs)) {
		max2(u) = max(max2(ls), max2(rs));
		cnt(u) = cnt(ls) + cnt(rs);
	} 
	if(max1(ls) > max1(rs)) {
		max2(u) = max(max1(rs), max2(ls));
		cnt(u) = cnt(ls);
	}
	if(max1(ls) < max1(rs)) {
		max2(u) = max(max1(ls), max2(rs));
		cnt(u) = cnt(rs);
	}
}
void build(int u, int l, int r) {
	l(u) = l, r(u) = r;
	if(l == r) {
		sum(u) = max1(u) = maxh(u) = a[l];
		max2(u) = -inf;
		cnt(u) = 1;
		return ;
	}
	int mid = l + r >> 1;
	build(u * 2, l, mid);
	build(u * 2 + 1, mid + 1, r);
	pushup(u);
}
void update(int u, int l, int r, int L, int R) {
	sum(u) += (l * cnt(u) + r * (r(u) - l(u) + 1 - cnt(u)));
	maxh(u) = max(maxh(u), max1(u) + r);
	max1(u) += l;
	if(max2(u) != -inf) max2(u) += L;
	tag2(u) = max(tag2(u), tag1(u) + r);
	tag4(u) = max(tag4(u), tag3(u) + R);
	tag1(u) += l;
	tag3(u) += L;
}
void pushdown(int u) {
	int ls = u * 2, rs = u * 2 + 1;
	if(max1(ls) >= max1(rs)) {
		update(ls, tag1(u), tag2(u), tag3(u), tag4(u));
	} 
	else update(ls, tag3(u), tag4(u), tag3(u), tag4(u));
	if(max1(rs) >= max1(ls)) {
		update(rs, tag1(u), tag2(u), tag3(u), tag4(u));
	}
	else update(rs, tag3(u), tag4(u), tag3(u), tag4(u));
	w[u].clear();
}
void updatesum(int u, int L, int R, int x) {
	if(InRange(l(u), r(u), L, R)) {
		update(u, x, x, x, x);
		return ;
	}
	if(OutofRange(l(u), r(u), L, R)) {
		return ;
	}
	pushdown(u);
	updatesum(u * 2, L, R, x);
	updatesum(u * 2 + 1, L, R, x);
	pushup(u);
}
void updatemax(int u, int L, int R, int x) {
	if(InRange(l(u), r(u), L, R) && max2(u) < x) {
		update(u, x - max1(u), x - max1(u), 0, 0);
		return ;
	}
	if(OutofRange(l(u), r(u), L, R)) return ;
	pushdown(u);
	updatemax(u * 2, L, R, x);
	updatemax(u * 2 + 1, L, R, x);
	pushup(u);
}
int querysum(int u, int L, int R) {
	if(InRange(l(u), r(u), L, R)) {
		return sum(u);
	}
	if(OutofRange(l(u), r(u), L, R)) {
		return 0;
	}
	pushdown(u);
	return querysum(u * 2, L, R) + querysum(u * 2 + 1, L, R);
}
int querymaxa(int u, int L, int R) {
	if(InRange(l(u), r(u), L, R)) {
		return w[u].max1;
	}
	if(OutofRange(l(u), r(u), L, R)) {
		return -2e9;
	}
	pushdown(u);
	return max(querymaxa(u * 2, L, R), querymaxa(u * 2 + 1, L, R));
}
int querymaxb(int u, int L, int R) {
	if(InRange(l(u), r(u), L, R)) {
		return w[u].maxh;
	}
	if(OutofRange(l(u), r(u), L, R)) return -2e9;
	pushdown(u);
	return max(querymaxb(u * 2, L, R), querymaxb(u * 2 + 1, L, R));
}
signed main() {
	cin >> n >> m;
	for(int i = 1;i <= n;i ++) cin >> a[i];
	build(1, 1, n);
	while(m --) {
		int op, l, r, x;
		cin >> op >> l >> r;
		if(op == 1) {
			cin >> x;
			updatesum(1, l, r, x);
		}
		if(op == 2) {
			cin >> x;
			updatemax(1, l, r, x);
		}
		if(op == 3) {
			cout << querysum(1, l, r) << endl;
		}
		if(op == 4) {
			cout << querymaxa(1, l, r) << endl;
		}
		if(op == 5) {
			cout << querymaxb(1, l, r) << endl;
		}
	}
}
2025/8/30 22:14
加载中...