laekov

BZOJ2209 [Jsoi2011]括号序列

好恶心的数据结构题。


考虑单个询问。把(视作1,把)视作-1,设minprefix为最小前缀和,设cp=(minprefix+1)/2,那么答案为(sum/2+cp*2),使劲想想想得出来。


所以就是用个splay或者smt来维护一下一段的最小前缀和以及总和。因为有两种操作所以写起来比较麻烦。要注意不要把操作看反了,还要注意标记的优先级和更新的问题。


恶心了一下午。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


struct dat {

int sm, t[2][2];

inline void operator =(const dat& a) {

sm = a. sm;

t[0][0] = a. t[0][0];

t[0][1] = a. t[0][1];

t[1][0] = a. t[1][0];

t[1][1] = a. t[1][1];

}

};


const int maxn = 100009;


int n, m, cr, a[maxn], sz[maxn], ls[maxn], rs[maxn], pt[maxn], vl[maxn];

bool flip[maxn], rev[maxn];

dat d[maxn];


dat sgd(int v) {

dat r;

r. sm = v;

r. t[0][0] = min(v, 0);

r. t[1][0] = r. t[0][0];

r. t[0][1] = min(-v, 0);

r. t[1][1] = r. t[0][1];

return r;

}


dat mgd(const dat& a, const dat& b) {

dat r;

r. sm = a. sm + b. sm;

r. t[0][0] = min(a. t[0][0], a. sm + b. t[0][0]);

r. t[1][0] = min(b. t[1][0], b. sm + a. t[1][0]);

r. t[0][1] = min(a. t[0][1], -a. sm + b. t[0][1]);

r. t[1][1] = min(b. t[1][1], -b. sm + a. t[1][1]);

return r;

}


inline void fix(int p) {

if (flip[p]) {

swap(ls[p], rs[p]);

swap(d[p]. t[0][0], d[p]. t[1][0]);

swap(d[p]. t[0][1], d[p]. t[1][1]);

if (ls[p])

flip[ls[p]] ^= 1;

if (rs[p])

flip[rs[p]] ^= 1;

flip[p] = 0;

}

}


inline void reverse(dat& r) {

swap(r. t[0][0], r. t[0][1]);

swap(r. t[1][0], r. t[1][1]);

r. sm = -r. sm;

}


inline void pushDown(int p) {

if (rev[p]) {

if (ls[p]) {

rev[ls[p]] ^= 1;

reverse(d[ls[p]]);

}

if (rs[p]) {

rev[rs[p]] ^= 1;

reverse(d[rs[p]]);

}

vl[p] = -vl[p];

rev[p] = 0;

}

}


inline void update(int p) {

sz[p] = sz[ls[p]] + sz[rs[p]] + 1;

d[p] = sgd(rev[p] ? -vl[p] : vl[p]);

if (ls[p]) {

fix(ls[p]);

d[p] = mgd(d[ls[p]], d[p]);

}

if (rs[p]) {

fix(rs[p]);

d[p] = mgd(d[p], d[rs[p]]);

}

if (rev[p])

reverse(d[p]);

}


inline void lRot(int q) {

int p = pt[q], a = pt[p];

if (rs[q])

pt[rs[q]] = p;

ls[p] = rs[q];

rs[q] = p;

pt[q] = a;

pt[p] = q;

if (a) {

if (p == ls[a])

ls[a] = q;

else

rs[a] = q;

}

update(p);

update(q);

}


inline void rRot(int q) {

int p = pt[q], a = pt[p];

if (ls[q])

pt[ls[q]] = p;

rs[p] = ls[q];

ls[q] = p;

pt[q] = a;

pt[p] = q;

if (a) {

if (p == ls[a])

ls[a] = q;

else

rs[a] = q;

}

update(p);

update(q);

}


void splay(int q) {

static int stc[maxn];

int tst = 1;

stc[tst] = q;

while (pt[stc[tst]]) {

stc[tst + 1] = pt[stc[tst]];

++ tst;

}

while (tst) {

fix(stc[tst]);

pushDown(stc[tst]);

-- tst;

}

while (pt[q]) {

int p = pt[q], a = pt[p];

if (!a || !pt[a]) {

if (q == ls[p])

lRot(q);

else

rRot(q);

}

else {

if (p == ls[a]) {

if (q == ls[p])

lRot(p), lRot(q);

else

rRot(q), lRot(q);

}

else {

if (q == ls[p])

lRot(q), rRot(q);

else

rRot(p), rRot(q);

}

}

}

cr = q;

}


int buildTree(int l, int r) {

if (l > r)

return 0;

int p = (l + r) >> 1;

ls[p] = buildTree(l, p - 1);

if (ls[p])

pt[ls[p]] = p;

rs[p] = buildTree(p + 1, r);

if (rs[p])

pt[rs[p]] = p;

sz[p] = sz[ls[p]] + sz[rs[p]] + 1;

rev[p] = 0;

flip[p] = 0;

vl[p] = a[p];

update(p);

return p;

}


int kth(int p, int k) {

while (p) {

fix(p);

if (sz[ls[p]] + 1 == k)

break;

else if (sz[ls[p]] + 1 > k)

p = ls[p];

else

k -= sz[ls[p]] + 1, p = rs[p];

}

return p;

}


int getRange(int l, int r) {

if (l == 1 && r == n)

return cr;

else if (l == 1) {

int p = kth(cr, r + 1);

splay(p);

return ls[p];

}

else if (r == n) {

int p = kth(cr, l - 1);

splay(p);

return rs[p];

}

else {

int p = kth(cr, l - 1), q = kth(cr, r + 1);

splay(p);

splay(q);

return rs[p];

}

}


int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif


memset(flip, 0, sizeof(flip));

memset(rev, 0, sizeof(rev));

scanf("%d%d", &n, &m);

for (int i = 1; i <= n; ++ i) {

int g;

do

g = getchar();

while (g != '(' && g != ')');

a[i] = (g == '(') ? 1 : -1;

}

cr = buildTree(1, n);

while (m --) {

int opt, l, r;

scanf("%d%d%d", &opt, &l, &r);

if (opt == 0) {

int x = getRange(l, r);

fix(x);

pushDown(x);

update(x);

printf("%d\n", (d[x]. sm >> 1) + ((-d[x]. t[0][0] + 1) & ~1));

}

else if (opt == 2) {

int x = getRange(l, r);

flip[x] ^= 1;

splay(x);

}

else if (opt == 1) {

int x = getRange(l, r);

rev[x] ^= 1;

reverse(d[x]);

splay(x);

}

}

}


评论

© laekov | Powered by LOFTER