【csu oj 1542】线段树

题目大意：给定一个合法的括号序列（只包含'(',')'），有q次操作，对每次操作改变一个位置的括号，求最左端的位置，使得改变这个位置上的括号以后，新序列合法（完全配对）。

思路：对于合法的括号序列，如果把括号序列一次进行栈操作，把'('进栈，')'则把最近的'('出栈，令a[i]表示到i位置后栈里面的左括号个数，也就是i位置的左括号数目和右括号数目的差。则原序列对应新的数组a。原序列合法等价于对于1<=i<=n,a[i]>=0 恒成立。那么对于把位置pos上的括号改变一下，如果是'(' - ')',那么a[pos~n]会都减去2，如果是')'->'(',那么a[pos~n]会都加上2。分类讨论后，答案不难得出。对于'('->')'答案就是从左至右找第一个右括号；对于')'->'(',答案就是找一个最左端的位置pos0,使得a[pos0~pos-1]都大于等于2。对于找第一个右括号，可以转化为用新的数组b[i] = a[i] - i,找第一个小于0的位置，进而转化为找最大的前缀区间使得这个区间上的b的最小值等于0。对于找最左端的位置，也可以转化为区间最值来做，详见代码:

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <map>

 #include <queue>

 #include <cmath>

 #include <vector>

 #include <ctime>

 #define mem0(a) memset(a, 0, sizeof(a))

 #define lson l, m, rt << 1

 #define rson m + 1, r, rt << 1 | 1

 #define define_m int m = (l + r) >> 1

 #define LL long long

 #define Rep(a, b) for(int a = 0; a < b; a++)

 #define lowbit(x) ((x) & (-(x)))

 const int dx[] = {, , -, };

 const int dy[] = {, -, , };

 const int INF = 1e9 + ;

 const int maxn = ;

 const double eps = 1e-;

 typedef double db;

 using namespace std;

 struct SegTree {

     struct Node {

         int minv, add;

     } tree[maxn << ];

     void PushUp(int rt) {

         tree[rt].minv = min(tree[rt << ].minv, tree[rt <<  | ].minv);

     }

     void PushDown(int rt) {

         int add = tree[rt].add;

         if (add) {

             tree[rt << ].minv += add;

             tree[rt << ].add += add;

             tree[rt <<  | ].minv += add;

             tree[rt <<  | ].add += add;

             tree[rt].add = ;

         }

     }

     void Build(int a[], int l, int r, int rt) {

         tree[rt].add = ;

         if (l == r) {

             tree[rt].minv = a[l];

             return ;

         }

         define_m;

         Build(a, lson);

         Build(a, rson);

         PushUp(rt);

     }

     void Update(int L, int R, int x, int l, int r, int rt) {

         if (L <= l && r <= R) {

             tree[rt].minv += x;

             tree[rt].add += x;

             return;

         }

         define_m;

         PushDown(rt);

         if (L <= m) Update(L, R, x, lson);

         if (R > m) Update(L, R, x, rson);

         PushUp(rt);

     }

     int Query1(int l, int r, int rt) {

         if (l == r) return tree[rt].minv == ;

         define_m;

         PushDown(rt);

         if (tree[rt << ].minv < )  return Query1(lson);

         int len = r - l + ;

         return len - (len >> ) + Query1(rson);

     }

     int Query2(int l, int r, int rt) {

         if (l == r) return tree[rt].minv == ;

         define_m;

         PushDown(rt);

         if (tree[rt <<  | ].minv < ) return Query2(rson);

         int len = r - l + ;

         return (len >> ) + Query2(lson);

     }

 };

 int n, q;

 char s[];

 int a[], b[], c[];

 SegTree G, H;

 void Init() {

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

         c[i + ] = c[i];

         if (s[i] == '(') c[i + ]++;

         else c[i + ]--;

     }

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

         a[i] = c[i] - i;

         b[i] = c[i];

     }

 }

 int main() {

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

     cin >> n >> q;

     scanf("%s", s);

     Init();

     G.Build(a, , n, );

     H.Build(b, , n, );

     for (int i = ; i < q; i++) {

         int pos, tmp;

         scanf("%d", &pos);

         if (s[pos - ] == '(') {

             s[pos - ] = ')';

             G.Update(pos, n, -, , n, );

             H.Update(pos, n, -, , n, );

             printf("%d\n", tmp = G.Query1(, n, ) + );

             G.Update(tmp, n, , , n, );

             H.Update(tmp, n, , , n, );

             s[tmp - ] = '(';

         }

         else {

             s[pos - ] = '(';

             H.Update(pos, n, , , n, );

             G.Update(pos, n, , , n, );

             printf("%d\n", tmp = n - H.Query2(, n, ) + );

             H.Update(tmp, n, -, , n, );

             G.Update(tmp, n, -, , n, );

             s[tmp - ] = ')';

         }

     }

     return ;

 }

巴特西

【csu oj 1542】线段树

最新文章

热门文章