HHUOJ 1023 Mouse and Parenthesis(线段树)

前言：这道题让我深刻地认识到了我自己就一白痴，已经蠢到超神了以后请叫我***

问题 E: Mouse and Parenthesis

时间限制: 1 Sec 内存限制: 128 MB

提交: 44 解决: 9

</center>

题目描述

Tom has m same balanced parenthesis sequence P=p1 p2…pn of length n.

This day Jerry comes into Tom's room and swaps one pair of parenthesis in every sequence.

Tom and Jerry both like balanced parenthesis sequence, so Jerry wants to know whether each P remains balanced after p_ai and p_bi swapped.

Parenthesis sequence S is balanced if and only if:

1. S is empty;

2. or there exists balanced parenthesis sequence A,B such that S=AB;

3. or there exists balanced parenthesis sequence S' such that S=(S').

输入

The first line contains an integers T (T≤20), which indicates the number of test cases.

For each case:

The first line contains two integers n,m.

The second line contains n characters p1 p2…pn.

The i-th of the last m lines contains 2 integers ai,bi (1≤ai,bi≤n,ai≠bi).

⋅ for 50% data, 1≤n≤50,1≤q≤1000.

⋅ for 100% data, 1≤n≤100000,1≤q≤100000.

输出

For every test case, you should output "Case #x:", where x indicates the case number and counts from 1. Then in i^th line output 'Yes' if i^th parenthesis sequence is balanced, otherwise 'No'.

样例输入

4 2

(())

1 3

2 3

2 1

()

1 2

样例输出

Case #1:

Yes

Case #2:

思路：

我真的就是一白痴啊啊啊啊啊啊啊啊啊啊啊啊啊啊白白浪费了一下午T-T

这道题的题意就是给了你平衡序列，然后对平衡序列的两个位置进行交换之后看是不是还是平衡序列。

这题花了两天的时间做...（这两天事比较多）第一天的做法就是仿照暑期联训时候的一道题，把(当作1，)当作-1，用ans计数，当ans为负时则说明不行。但是这样的方法不管怎么优化，n^2、n的算法都会TLE，第一天没做出来就去补作业了。。

第二天开始用线段树做这题，一开始还是用数组来保存每个符号的正负值，还是TLE，仔细一想，只要用数组保存的是单个的正负值，那么你遍历的时候一定会再遍历一遍这又会超时的，所以...用数组来保存第i个数以及之前的累加和，就不用再遍历求和了就会快很多。然后线段树可以将算法简化为logn。这题可以仿照之前的排兵布阵那道题，但是这里的sum不是储存的和了，而是要储存其下属值里面的最小值。

再者就是对情况的判断分为三种，第一种就是要交换的两个位置是相同的，因为之前本来就是平衡的了，所以直接输出Yes；第二种就是如果第一个数是‘）’，那么这点的贡献由-1变为了1，肯定不会不行，也直接输出Yes；第三种就是左边是'('，右边是')'，这种情况___(______)____，两个括号的交换对‘(’之前的和‘）’之后的没有影响，主要影响的就是他们其中的部分。因为如果‘(’变为了‘)’，那么他后面的值都会由原来的+1变为-1，所以会减少2，所以，就要查询这之间的最小值，如果最小值小于2的话，那么交换之后它就会变为负的了，这就不行了。所以用quire函数来查询区间最小值。然后还有小萌学姐说的那句，线段树要开4倍大！

我我我我....你猜猜我WA在了什么地方....我一共交了快20次....结果在很早之前思路就已经对了的，结果WA是因为……我的输出格式Case #1:的#号没有写

好气啊可是还要保持微笑。。。真的嫌弃我自己。面壁思过之后...记住这个教训！ 输出的格式复制粘贴题目中的！数据范围复制粘贴题目中的！唉。。下次我要是再犯这种错误就活该我找不到女朋友。。。我真的是菜爆了。。。

代码：

#include <iostream>    
#include <cstring>    
#include <cstdio>    
#include <algorithm>    
#include <cmath>    
using namespace std;    
const int maxn=100000+5;    
struct node{    
    int l;    
    int r;    
    int sum;    
}tree[(maxn+5)*9];    
int a[maxn+5];  
char s[maxn+5];
bool flag=true;
      
void build(int l,int r,int index){    
    tree[index].l=l;    
    tree[index].r=r;    
    if(l==r){    
        tree[index].sum=a[l];    
        return;    
    }    
    int middle = (l+r)/2;    
    build(l, middle, 2*index);    
    build(middle+1, r, 2*index+1);    
    tree[index].sum=min(tree[2*index].sum,tree[2*index+1].sum);    
}    
    
void update(int number,int index,int ans)  
{     
    tree[index].sum += ans;    
    if(tree[index].l==tree[index].r&&tree[index].l==number){    
        return;    
    }    
    int middle = (tree[index].l+tree[index].r)/2;    
    if(middle>=number)  
    {    
        update(number, 2*index, ans);    
    }  
    else
    {    
        update(number, 2*index+1, ans);    
    }    
}    
int getSum(int l,int r,int index)
{    
    if(tree[index].l==l&&tree[index].r==r)  
    {     
        return tree[index].sum;    
    }    
    int middle = (tree[index].l+tree[index].r)/2;    
    if(middle<l)  
    {  
        return getSum(l, r, 2*index+1);    
    }  
    else if(middle>=r)  
    {    
        return getSum(l,r,2*index);    
    }  
    else
    {    
        return min(getSum(l, middle, 2*index),getSum(middle+1, r, 2*index+1));    
    }    
}    
      
      
      
      
int main()  
{    
    //freopen("in.txt","r",stdin);  
    int t,rnd=1;    
    scanf("%d",&t);    
    while(t--)  
    {    
        printf("Case #%d:\n",rnd);    
        int n,m,i;    
        memset(tree, 0, sizeof(tree));    
        scanf("%d%d",&n,&m); 
        scanf("%s",s+1); 
        a[0]=0;  
        for(i=1;i<=n;i++)
        {    
            if(s[i]=='(') a[i]=1+a[i-1];
            else a[i]=a[i-1]-1;    
        }    
        build(1, n, 1);       
        while(m--)  
        {     
            int pos1,pos2;
            scanf("%d%d",&pos1,&pos2);
            if(pos1>pos2)swap(pos1,pos2);
            if(s[pos1]==s[pos2])
            {
                printf("Yes\n"); 
                continue;
            }
            if(s[pos1]==')')
            {
                printf("Yes\n"); 
                continue;
            } 
            /*
            int lo;
            update(pos1, 1, -a[pos1]);
            update(pos2, 1, -a[pos2]);
            lo=a[pos1];
            a[pos1]=a[pos2];
            a[pos2]=lo;
            update(pos1, 1, a[pos1]);
            update(pos2, 1, a[pos2]);     
            for(int j=pos1;j<=pos2;j++)
            {
                int re=getSum(1,j,1);
               // cout<<re<<endl; 
                if(re<0) 
                {
                    printf("No\n");
                    break;
                } 
                if(j==pos2) printf("Yes\n");    
            } 
            update(pos1, 1, -a[pos1]);
            update(pos2, 1, -a[pos2]);
            lo=a[pos1];
            a[pos1]=a[pos2];
            a[pos2]=lo;
            update(pos1, 1, a[pos1]);
            update(pos2, 1, a[pos2]); 
            */
              
            int ans=getSum(pos1,pos2-1,1);
            if(ans<2)   printf("No\n");  
            else    printf("Yes\n");  
              
        }    
        rnd++;    
    }    
          
    return 0;    
}

</center>