Znzryb's Blog
0%

2025牛客WC2-E-一起走很长的路！

Posted on Edited on

思路讲解

P2880 [USACO07JAN] Balanced Lineup G

树状数组做RMQ问题

我的思路是肯定要预处理这个东西，然后重量加减应该没那么复杂，就是加在第一块上就行
然后我们其实就是要求需要加了多少嘛
我们可以把这个问题转化为RMQ，即该区间内最大的A[i]-sumA[i-1];

query的时候这样输出就行

1
cout<<max(query(l+1,r)+sumA[l-1],0LL)<<'\n';

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75111878

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10,MINval=static_cast<ll>(-1e18)-10;
ll N,Q,A[MAXN],sumA[MAXN],tr[MAXN];
inline ll lowbit(ll x) {
	return x&(-x);
}
// 将p位置改为x (我懒得建树，这题当然不需要在线修改)
inline void change(ll p, ll x) {
	while (p<=N) {
		tr[p]=x;  // 这个之所以可以直接赋值是因为我们这道题的change函数调用是从小区间到大区间
		// 可以模拟一下8，8-1=7  8-2=6 8-4=4 相当于把8下面的全部区间都遍历了一遍（lowbit（8）=8）
		for(int i=1;i<lowbit(p);i<<=1) {
			tr[p]=max({tr[p-i],tr[p],x});
		}
		p+=lowbit(p);
	}
}

inline ll query(ll l,ll r) {
	ll res=MINval;
	while (l<=r) {
		if(r-lowbit(r)<l) {
			res=max(A[r]-sumA[r-1],res);
			r-=1;
		}else {
			res=max(tr[r],res);
			r-=lowbit(r);
		}
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i=1;i<=N;++i) {	// 初始化树状数组
		tr[i]=MINval;
	}
	// 我的思路是肯定要预处理这个东西，然后重量加减应该没那么复杂，就是加在第一块上就行
	// 然后我们其实就是要求需要加了多少嘛
	// 我们可以把这个问题转化为RMQ，即该区间内最大的A[i]-sumA[i-1];
	for(int i=1;i<=N;++i) {
		cin>>A[i];
		sumA[i]=sumA[i-1]+A[i];
		change(i,A[i]-sumA[i-1]);
	}

	for(int i=1;i<=Q;++i) {
		ll l,r;
		cin>>l>>r;
		if(l==r) {cout<<0<<'\n';continue;}	// 特判特殊情况
		cout<<max(query(l+1,r)+sumA[l-1],0LL)<<'\n';
	}
	// cout<<"debug:\n";
	// for(int i=1;i<=N;++i) {
	// 	cout<<tr[i]<<' ';
	// }
	// cout<<'\n';
	return 0;
}
/*
6 4
1 1 4 5 1 4
1 2
1 3
2 5
1 6

15 6
5 23 56 71 13 63 24 61 2 76 28 37 46 12 43
1 15
7 8
8 9
4 7
4 11
9 10

28
37
0
0
0
74

*/

心路历程（WA，TLE，MLE……）

WA

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75111646

1
2
3
for(int i=1;i<lowbit(p);i<<=1) {
			tr[p]=max({tr[p-i],tr[p],x});
	}

i<lowbit(p)，你想lowbit（p）就是其表示区间的长度