16 多校8 Rikka with Parenthesis II

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 SS, and he wants Rikka to choose two different position i,ji,j and swap Si,SjSi,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?

InputThe 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 ‘)’.OutputFor each testcase, print “Yes” or “No” in a line.Sample Input

3
4
())(
4
()()
6
)))(((

Sample Output

Yes
Yes
No

Hint

For the second sample input, Rikka can choose (1,3) or (2,4) to swap. But do nothing is not allowed.水题，注意两点1一定要交换所以"()"不行；2记录 l和r 遇到第一次r>l的情况和最后面的'('交换位置，之后就不能交换位置了

 #include<iostream>
 #include<cstdio>
 #include<queue>
 #include<vector>
 #include<cstring>
 #include<string>
 #include<algorithm>
 #include<map>
 #include<cmath>
 #include<math.h>
 using namespace std; int main()
 {
     int T,n;
     int l,r,sum;
     scanf("%d",&T);
     char a[];
     bool flag1,flag2;
     while(T--)
     {
         scanf("%d",&n);
         if(n==)
         {
             printf("Yes\n");
             continue;
         }
         cin>>a;
         l=;r=;sum=;
         if(n==&&a[]=='('&&a[]==')')
             printf("No\n");
         else if(n%!=)
             printf("No\n");
         else
         {
             flag1=false;flag2=true;
             for(int i=;i<n;i++)
             {
                 if(a[i]=='(')
                     l++;
                 else if(a[i]==')')
                     r++;
                 if(r>l&&!flag1)
                 {
                     for(int j=n-;j>i;j--)
                     {
                         if(a[j]=='(')
                         {
                             a[i]='(';
                             a[j]=')';
                             l++;
                             r--;
                             flag1=true;
                             break;
                         }
                     }
                 }
                 else if(r>l&&flag1==true)
                 {
                     flag2=false;
                     break;
                 }
             }
             if(flag2&&l==r)
                 printf("Yes\n");
             else
                 printf("No\n");
         }     }
     return ;
 }