#include <bits/stdc++.h>
using ll = long long;
int const nmax = 500000;
int a[1 + nmax];
class SegmentTree {
private:
struct Node {
int sum;
int maxsuff;
int maxpref;
int uphill;
};
std::vector<Node> aint;
public:
SegmentTree(int n) {
aint.resize(4 * n + 1);
}
Node join(Node lson, Node rson) {
Node ans;
ans.sum = lson.sum + rson.sum;
ans.maxsuff = std::max(rson.minsuff, rson.sum + lson.maxsuff);
ans.maxpref = std::max(lson.maxpref, lson.sum + rson.maxpref);
ans.uphill = std::max({lson.maxpref + rson.maxsuff, lson.sum + rson.uphill, lson.uphill + rson.sum});
return ans;
}
void build(int v, int from, int to) {
if(from == to)
aint[v] = Node{a[from], std::max(0, a[from]), std::max(0, a[from]), std::max(0, a[from])};
else {
int mid = (from + to) / 2;
build(2 * v, from, mid);
build(2 * v + 1, mid + 1, to);
aint[v] = join(aint[2 * v], aint[2 * v + 1]);
}
}
Node query(int v, int from, int to, int l, int r) {
if(l > r)
return Node{0, 0, 0, 0};
else if(l <= from && to <= r)
return aint[v];
else {
int mid = (from + to) / 2;
return join(query(2 * v, from, mid, l, std::min(mid, r)), query(2 * v + 1, mid + 1, to, std::max(l, mid + 1), r));
}
}
};
int main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
int n;
std::string s;
std::cin >> n >> s;
for(int i = 1;i <= n; i++) {
if(s[i - 1] == 'C')
a[i] = -1;
else
a[i] = 1;
}
SegmentTree aint(n);
aint.build(1, 1, n);
int q;
std::cin >> q;
for(int i = 1;i <= q; i++) {
int l, r;
std::cin >> l >> r;
std::cout << aint.query(1, 1, n, l, r).uphill << "\n";
}
return 0;
}
Compilation message
election.cpp: In member function 'SegmentTree::Node SegmentTree::join(SegmentTree::Node, SegmentTree::Node)':
election.cpp:26:35: error: 'struct SegmentTree::Node' has no member named 'minsuff'; did you mean 'maxsuff'?
26 | ans.maxsuff = std::max(rson.minsuff, rson.sum + lson.maxsuff);
| ^~~~~~~
| maxsuff
