这两天复习 $splay$真的太痛苦了 $qwq$
题解
首先我们考虑一下如何维护 $Query$的信息
改变几个括号让括号序列合法？注意到一个合法的括号序列我们是可以将配对括号不断消去直到消没的，如果括号序列不合法我们消括号的时候最后会剩下类似 $)))((($的情况，记 $(=1$，$)=-1$，一个合法括号序列的充要条件就是所有前缀和 $\geq 0$且所有后缀和 $\leq 0$，因此我们就要找到最后 $)$的个数记为 $l$，$($的个数记为 $r$，答案就是 $[\frac {l+1}2]+[\frac {r+1}2]$，注意到其实剩余 $($和 $)$的个数分别是这个序列的最大后缀和，最小前缀和。因此我们只需要维护这两个东西就好了。
但是因为有 $inv$操作，所以我们还要维护最小后缀和，最大前缀和
然后剩下三个操作就打标记就行啦
刚开始我以为 $same$标记 (区间取相同的数) 和 $inv$标记 (区间取反) 还存在一个优先下放的关系，但是后来想了想是没有的啦
还有一个常见的 $trick$就是如果一个区间被打上了 $same$标记，那么它的 $rev$(翻转) 标记就可以直接置 $0$。因为此时 $rev$已经没意义了。
感觉我的 $splay$总是比别人的长一大截 $qwq$，不过我个人感觉思路清晰呀，反正这东西打得快就好长不长无所谓啦 (强行解释.jpg)
#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 10086
#define lowbit(x) (x & -x)
#define N 100205
#define cl(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
#define pi std::pair<int, int>
inline void read (int &x)
{
x = 0;
Re bool flag = 0;
Re char ch = getchar();
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') flag = 1, ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
if (flag) x = -x;
}
int n, a[N], p, m, c, q;
char ch[10];
using std::max; using std::min; using std::swap;
struct splay_tree {
int s[N][2], fa[N], sz[N], root, siz, ans, sum[N];
int lmx[N], lmn[N], rmx[N], rmn[N], val[N];
bool rev[N], same[N], inv[N];
#define ls(u) s[u][0]
#define rs(u) s[u][1]
inline void update (int u)
{
sz[u] = sz[ls(u)] + sz[rs(u)] + 1;
sum[u] = sum[ls(u)] + sum[rs(u)] + val[u];
lmx[u] = max(lmx[ls(u)], sum[ls(u)] + val[u] + lmx[rs(u)]);
rmx[u] = max(rmx[rs(u)], sum[rs(u)] + val[u] + rmx[ls(u)]);
lmn[u] = min(lmn[ls(u)], sum[ls(u)] + val[u] + lmn[rs(u)]);
rmn[u] = min(rmn[rs(u)], sum[rs(u)] + val[u] + rmn[ls(u)]);
}
inline void pushinv (int u)
{
inv[u] ^= 1;
swap(lmx[u], lmn[u]); lmx[u] = -lmx[u]; lmn[u] = -lmn[u];
swap(rmx[u], rmn[u]); rmx[u] = -rmx[u]; rmn[u] = -rmn[u];
sum[u] = -sum[u];
val[u] = -val[u];
}
inline void pushsame (int u)
{
same[u] = 1;
rev[u] = 0;
sum[u] = sz[u] * val[u];
if (val[u] > 0)
{
lmx[u] = rmx[u] = sum[u];
lmn[u] = rmn[u] = 0;
}
else
{
lmx[u] = rmx[u] = 0;
lmn[u] = rmn[u] = sum[u];
}
}
inline void pushrev (int u)
{
rev[u] ^= 1;
swap(ls(u), rs(u));
swap(lmx[u], rmx[u]);
swap(lmn[u], rmn[u]);
}
inline void pushdown (int u)
{
if (inv[u])
{
inv[u] = 0;
pushinv(ls(u));
pushinv(rs(u));
}
if (same[u])
{
same[u] = 0;
val[ls(u)] = val[rs(u)] = val[u];
pushsame(ls(u));
pushsame(rs(u));
}
if (rev[u])
{
rev[u] = 0;
pushrev(ls(u));
pushrev(rs(u));
}
}
inline bool pos (int u) { return rs(fa[u]) == u; }
inline void connect (int u, int v, int p) { fa[v] = u; s[u][p] = v; }
inline void rotate (int u)
{
int f = fa[u], g = fa[f];
int gs = pos(f), fs = pos(u);
connect(f, s[u][!fs], fs);
if (g) connect(g, u, gs); else fa[u] = g;
connect(u, f, !fs);
update(f); update(u);
}
int S[N], top;
inline void splay (int u, int rt)
{
top = 0;
while (u != rt)
{
S[++top] = u;
u = fa[u];
}
fd (i, top, 1) pushdown(S[i]);
u = S[1];
for (; fa[u] != rt; rotate(u))
if (fa[fa[u]] != rt)
rotate(pos(u) ^ pos(fa[u]) ? u : fa[u]);
if (!rt) root = u;
}
inline int build (int f, int l, int r)
{
if (l > r) return 0;
int mid = l + r >> 1;
int u = ++siz;
fa[u] = f;
val[u] = a[mid];
if (l == r)
{
sum[u] = val[u]; sz[u] = 1;
if (val[u] > 0)
lmx[u] = rmx[u] = val[u];
else
lmn[u] = rmn[u] = val[u];
return u;
}
s[u][0] = build(u, l, mid - 1);
s[u][1] = build(u, mid + 1, r);
update(u);
return u;
}
inline int kth (int x)
{
int u = root;
pushdown(u);
while (1)
{
if (sz[ls(u)] >= x) u = ls(u);
else
{
x -= sz[ls(u)] + 1;
if (x <= 0) return u;
u = rs(u);
}
pushdown(u);
}
}
inline void modify (int u, int v, int c)
{
u = kth(u); v = kth(v);
splay(u, 0); splay(v, u);
u = ls(v);
val[u] = c;
pushsame(u);
update(v); update(fa[v]);
}
inline void reverse (int u, int v)
{
u = kth(u); v = kth(v);
splay(u, 0); splay(v, u);
u = ls(v);
pushrev(u);
update(v); update(fa[v]);
}
inline void invert (int u, int v)
{
u = kth(u); v = kth(v);
splay(u, 0); splay(v, u);
u = ls(v);
pushinv(u);
}
inline int getans (int u, int v)
{
u = kth(u); v = kth(v);
splay(u, 0); splay(v, u);
u = ls(v);
return (-lmn[u] + 1 >> 1) + (rmx[u] + 1 >> 1);
}
} t;
inline int getp ()
{
char ch = getchar();
while (ch != '(' && ch != ')') ch = getchar();
return ch == '(' ? 1 : -1;
}
int main ()
{
read(n); read(q);
fo (i, 1, n) a[i] = getp();
a[n + 1] = a[0] = -inf;
t.root = t.build(0, 0, n + 1);
fo (i, 1, q)
{
scanf("%s", ch + 1);
int l, r;
read(l); read(r);
if (ch[1] == 'R')
{
t.modify(l, r + 2, getp());
}
else
if (ch[1] == 'Q')
{
printf("%d\n", t.getans(l, r + 2));
}
else
if (ch[1] == 'S')
{
t.reverse(l, r + 2);
}
else
if (ch[1] == 'I')
{
t.invert(l, r + 2);
}
}
return 0;
}
有点可惜的一点是这道题本来可以 $1A$的，因为我有一些毒瘤习惯比如当终端开太多的时候懒得去找而去开一个新的 ($vim$玩家)，而我的 $miao.cpp$就会同时开好几个 (:，然后我在某一个终端里改的东西错乱了导致有个翻转标记竟然没保存= =，这个毒瘤习惯还是改一改吧不然直接退役.jpg(然而 $win$下的省选环境是打死不可能开好几个 $Dev\;\;cpp$的 $23333$)
0 条评论