把左括号看做$1$,右括号看做$-1$,于是查询操作等于查询一个区间左边右边最大(最小)子段和
支持区间翻转,反转,覆盖操作。。。注意如果有覆盖操作,之前的操作全部作废了。。。于是在下传标记的时候要最后做。。。
/**************************************************************
Problem: 2329
User: rausen
Language: C++
Result: Accepted
Time:4252 ms
Memory:7352 kb
****************************************************************/ #include <cstdio>
#include <algorithm> #define _max(x, y) (x > y ? x : y)
#define _min(x, y) (x < y ? x : y)
using namespace std;
const int N = 1e5 + ; int read();
int get_c();
int get_op(); namespace treap {
struct node;
node *root, *null; struct node {
node *ls, *rs;
int val, rev, inv, fill, maxl, maxr, minl, minr, sum, sz; #define Len (1 << 16)
inline void* operator new(size_t, int _v = ) {
static node *mempool, *c;
if (mempool == c)
mempool = (c = new node[Len]) + Len;
c -> ls = c -> rs = null;
c -> val = c -> sum = _v, c -> rev = c -> inv = c -> fill = ;
c -> maxl = c -> maxr = c -> minl = c -> minr = ;
c -> sz = ;
return c++;
}
#undef Len inline void reverse() {
rev ^= ;
swap(ls, rs);
swap(minl, minr), swap(maxl, maxr);
}
inline void inverse() {
inv ^= ;
fill = -fill, val = -val, sum = -sum;
swap(maxl, minl), maxl = -maxl, minl = -minl;
swap(maxr, minr), maxr = -maxr, minr = -minr;
}
inline void replace(int t) {
fill = val = t, sum = sz * t;
maxl = maxr = sz * (t == );
minl = minr = -sz * (t == -);
} inline node* update() {
sz = ls -> sz + rs -> sz + ;
sum = ls -> sum + rs -> sum + val;
maxl = _max(ls -> maxl, ls -> sum + val + _max(, rs -> maxl));
minl = _min(ls -> minl, ls -> sum + val + _min(, rs -> minl));
maxr = _max(rs -> maxr, rs -> sum + val + _max(, ls -> maxr));
minr = _min(rs -> minr, rs -> sum + val + _min(, ls -> minr));
return this;
}
inline node* push() {
if (rev) {
ls -> reverse(), rs -> reverse();
rev = ;
}
if (inv) {
ls -> inverse(), rs -> inverse();
inv = ;
}
if (fill) {
ls -> replace(fill), rs -> replace(fill);
fill = ;
}
return this;
}
}; inline void init() {
null = new()node;
null -> ls = null -> rs = null;
null -> sz = null -> val = ;
} inline unsigned int Rand() {
static unsigned int res = ;
return res += res << | ;
}
inline int random(int x, int y) {
return Rand() % (x + y) < x;
} void build(node *&p, int l, int r, int *a) {
if (l > r) {
p = null;
return;
}
p = new(a[l + r >> ])node;
if (l == r) {
p -> update();
return;
}
build(p -> ls, l, (l + r >> ) - , a);
build(p -> rs, (l + r >> ) + , r, a);
p -> update();
} void merge(node *&p, node *x, node *y) {
if (x == null || y == null)
p = x == null ? y -> push() : x -> push();
else if (random(x -> sz, y -> sz)) {
p = x -> push();
merge(p -> rs, x -> rs, y);
} else {
p = y -> push();
merge(p -> ls, x, y -> ls);
}
p -> update();
} void split(node *p, node *&x, node *&y, int k) {
if (!k) {
x = null, y = p -> push();
return;
}
if (k == p -> sz) {
x = p -> push(), y = null;
return;
}
if (p -> ls -> sz >= k) {
y = p -> push();
split(p -> ls, x, y -> ls, k);
y -> update();
} else {
x = p -> push();
split(p -> rs, x -> rs, y, k - p -> ls -> sz - );
x -> update();
}
}
}
using namespace treap; int n;
int a[N]; int main() {
int Q, i, oper, l, r;
node *x, *y, *z;
init();
n = read(), Q = read();
for (i = ; i <= n; ++i) a[i] = get_c();
build(root, , n, a);
while (Q--) {
oper = get_op(), l = read(), r = read();
split(root, x, y, l - ), split(y, y, z, r - l + );
if (oper == ) y -> replace(get_c());
else if (oper == ) printf("%d\n", (y -> maxr + ) / - (y -> minl - ) / );
else if (oper == ) y -> reverse();
else if (oper == ) y -> inverse();
merge(root, x, y -> push()), merge(root, root, z);
}
return ;
} inline int read() {
register int x = ;
register char ch = getchar();
while (ch < '' || '' < ch) ch = getchar();
while ('' <= ch && ch <= '')
x = x * + ch - '', ch = getchar();
return x;
} inline int get_c() {
register char ch = getchar();
while (ch != '(' && ch != ')') ch = getchar();
return ch == '(' ? : -;
} inline int get_op() {
register char ch = getchar();
while (ch != 'R' && ch != 'Q' && ch != 'S' && ch != 'I') ch = getchar();
if (ch == 'R') return ;
if (ch == 'Q') return ;
if (ch == 'S') return ;
if (ch == 'I') return ;
}