Rikka with Parenthesis II

题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=5831

Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Correct parentheses sequences can be defined recursively as follows:

1.The empty string "" is a correct sequence.

2.If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.

3.If "X" is a correct sequence, then "(X)" is a correct sequence.

Each correct parentheses sequence can be derived using the above rules.

Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".

Now Yuta has a parentheses sequence S, and he wants Rikka to choose two different position i,j and swap Si,Sj.

Rikka likes correct parentheses sequence. So she wants to know if she can change S to a correct parentheses sequence after this operation.

It is too difficult for Rikka. Can you help her?

Input

The first line contains a number t(1<=t<=1000), the number of the testcases. And there are no more then 10 testcases with n>100

For each testcase, the first line contains an integers n(1<=n<=100000), the length of S. And the second line contains a string of length S which only contains ‘(’ and ‘)’.

Output

For each testcase, print "Yes" or "No" in a line.

Sample Input

3

4

())(

4

()()

6

)))(((

Sample Output

Yes

Yes

No

Hint

题意

给你一个括号序列，你必须交换俩括号位置，问你可以可以使他合法。

题解：

哎呀，好气啊，感觉只有我们队是用线段树去模拟交换的……

最优情况下一定交换第一个右括号和最后一个左括号，交换后判断一下即可。 时间复杂度 O(n)O(n)

代码

#include <bits/stdc++.h>

#define rep(a,b,c) for(int (a)=(b);(a)<=(c);++(a))

#define drep(a,b,c) for(int (a)=(b);(a)>=(c);--(a))

#define pb push_back

#define mp make_pair

#define sf scanf

#define pf printf

#define two(x) (1<<(x))

#define clr(x,y) memset((x),(y),sizeof((x)))

#define dbg(x) cout << #x << "=" << x << endl;

const int mod = 1e9 + 7;

int mul(int x,int y){return 1LL*x*y%mod;}

int qpow(int x , int y){int res=1;while(y){if(y&1) res=mul(res,x) ; y>>=1 ; x=mul(x,x);} return res;}

inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

using namespace std;

const int maxn = 100000 + 150;

int len,prefix[maxn],lstid;

char str[maxn];

struct Sgtree{

    struct node{

        int l , r , lzy , mi ;

        void Update( int v ){

            lzy += v;

            mi += v;

        }

    }tree[maxn << 2];

    void Build( int l , int r , int o ){

        tree[o].l = l , tree[o].r = r , tree[o].lzy = tree[o].mi = 0;

        if( r > l ){

            int mid = l + r >> 1;

            Build( l , mid , o << 1 );

            Build( mid + 1 , r , o << 1 | 1 );

            Maintain( o );

        }else{

            if( l == len ) lstid = o;

            tree[o].mi = prefix[l];

        }

    }

    int query( int x , int o ){

        int l = tree[o].l , r = tree[o].r;

        if( l == r ) return tree[o].mi;

        else{

            int mid = l + r >> 1 , rs ;

            ReleaseLabel(o);

            if( x <= mid ) rs = query( x , o << 1 );

            else rs = query( x , o << 1 | 1 );

            Maintain(o);

            return rs;

        }

    }

    void Maintain( int o ){

        tree[o].mi = min( tree[o << 1].mi , tree[o << 1 | 1 ].mi );

    }

    void ReleaseLabel( int o ){

        if( tree[o].lzy ){

            tree[o << 1].Update( tree[o].lzy );

            tree[o << 1 | 1].Update( tree[o].lzy );

        }

        tree[o].lzy = 0;

    }

    void Modify( int ql , int qr , int y , int o ){

        int l = tree[o].l , r = tree[o].r;

        if( ql <= l && r <= qr ) tree[o].Update( y );

        else{

            int mid = l + r >> 1;

            ReleaseLabel( o );

            if( ql <= mid ) Modify( ql , qr , y , o << 1 );

            if( qr > mid ) Modify( ql , qr , y , o << 1 | 1 );

            Maintain( o );

        }

    }

    int Search_First( int x , int o ){

        int l = tree[o].l , r = tree[o].r;

        if( l == r ){

            if( tree[o].mi < 0 ) return l;

            return -1;

        }

        int mid = l + r >> 1 , rs = -1;

        ReleaseLabel( o );

        if( tree[o << 1].mi < 0 ) rs = Search_First( x , o << 1 );

        if( rs == -1 && x > mid && tree[o << 1 | 1].mi < 0 ) rs = Search_First( x , o << 1 | 1 );

        Maintain( o );

        return rs;

    }

}Sgtree;

bool solve(){

    rep(i,1,len) if(str[i]=='(' && i > 1){

        int go = Sgtree.Search_First( i - 1 , 1 );

        if( go != -1 ){

            Sgtree.Modify( go , i - 1 , 2 , 1 );

            if( Sgtree.tree[1].mi == 0 && Sgtree.query(len,1) == 0 ) return true;

            Sgtree.Modify( go , i - 1 , -2 , 1 );

        }

    }

    return false;

}

int main(int argc,char *argv[]){

    int T=read();

    while(T--){

        len=read();

        sf("%s",str+1);

        int ar = 0 , ok = 1;

        rep(i,1,len){

            prefix[i] = prefix[i - 1];

            if(str[i]=='('){

                ++ prefix[i];

                ++ ar;

            }

            else{

                if( ar == 0 ) ok = 0;

                -- ar;

                -- prefix[i];

            }

        }

        Sgtree.Build(1,len,1);

        if( ar != 0 ) ok = 0;

        if( ok ){

            if( len == 2 ) pf("No\n");

            else pf("Yes\n");

        }else{

            bool result = solve();

            if( result == true ) printf("Yes\n");

            else printf("No\n");

        }

    }

    return 0;

}