「HDU 5217」Brackets

发表于

给出一个长度为 nn 的括号序列和 22 种操作：1.1. 翻转某一个括号；2.2. 查询区间内完成括号匹配后第 kk 个括号的原位置。

Constraints

1≤n,q≤2000001\leq n,q \leq 200000

Solution

易得，最后的序列一定形如 ‘)))(((’ ，即左段皆为 ‘)’，右段皆为 ‘(’ 。我们可以建出一棵线段树，线段树上的每个节点对应区间内匹配后左段 ‘(’ 的数量和右段 ‘)’ 的数量。

区间合并与修改显然，主要问题在查询。至此我们可以通过查询区间 [L,R][L,R] 的信息快速得到第 kk 个括号的类型。因为 ‘(’ 在从右往左合并区间时单调不减， ‘)’ 在从左往右合并区间时单调不减，所以可以在线段树上边跑边查询。详见代码。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define lc x<<1
#define rc x<<1|1
#define LL long long
using namespace std;
const int N=5e5+5;
int T,n,m,op,L,R,x;
int a[N],id[N],tl[N*4],tr[N*4];
char ch[N];
struct node{int t1,t0;}ans,now,tmp,t[N*4];
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
node merge(node a,node b)
{
    node c=(node){a.t1,b.t0};
    if(a.t0>b.t1)c.t0+=a.t0-b.t1;
    else c.t1+=b.t1-a.t0;
    return c;
}
void build(int x,int l,int r)
{
    tl[x]=l;tr[x]=r;
    if(l==r)
    {
        if(a[l])t[x]=(node){1,0};
        else t[x]=(node){0,1};
        id[l]=x;return;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    t[x]=merge(t[lc],t[rc]);
}
void modify(int x,int l,int r,int p)
{
    if(l==r)
    {
        swap(t[x].t0,t[x].t1);
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)modify(lc,l,mid,p);
    else modify(rc,mid+1,r,p);
    t[x]=merge(t[lc],t[rc]);
}
void query(int x,int l,int r)
{
    if(L<=l&&r<=R)
    {
        ans=merge(ans,t[x]);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)query(lc,l,mid);
    if(R>mid)query(rc,mid+1,r);
}
int work0(int x,int l,int r,int goal)
{
    if(l==r)return l;
    int mid=(l+r)>>1;
    tmp=now;now=merge(t[rc],now);
    if(now.t0>=goal)
    {
        now=tmp;
        return work0(rc,mid+1,r,goal);
    }
    return work0(lc,l,mid,goal);
}
int find0(int p,int goal)
{
    int x=id[p];
    bool flag=false;
    now=merge(t[x],now);
    if(now.t0==goal)return p;
    if(x&1)flag=true;
    while(1)
    {
        x>>=1;
        if(flag)
        {
            tmp=now;now=merge(t[lc],now);
            if(now.t0>=goal){now=tmp;x=lc;break;}
        }
        if(x&1)flag=true;
        else flag=false;
    }
    return work0(x,tl[x],tr[x],goal);
}
int work1(int x,int l,int r,int goal)
{
    if(l==r)return l;
    int mid=(l+r)>>1;
    tmp=now;now=merge(now,t[lc]);
    if(now.t1>=goal)
    {
        now=tmp;
        return work1(lc,l,mid,goal);
    }
    return work1(rc,mid+1,r,goal);
}
int find1(int p,int goal)
{
    int x=id[p];
    bool flag=true;
    now=merge(now,t[x]);
    if(now.t1==goal)return p;
    if(x&1)flag=false;
    while(1)
    {
        x>>=1;
        if(flag)
        {
            tmp=now;now=merge(now,t[rc]);
            if(now.t1>=goal){now=tmp;x=rc;break;}
        }
        if(x&1)flag=false;
        else flag=true;
    }
    return work1(x,tl[x],tr[x],goal);
}
void work()
{
    n=read();m=read();
    scanf("%s",ch+1);
    for(int i=1;i<=n;i++)
        if(ch[i]=='(')a[i]=0;
        else a[i]=1; 
    build(1,1,n);
    while(m--)
    {
        op=read();
        if(op==1)
        {
            x=read();
            modify(1,1,n,x);
            continue;
        }
        L=read();R=read();x=read();
        ans.t0=ans.t1=0;
        query(1,1,n);
        if(ans.t0+ans.t1<x)
        {
            printf("-1\n");
            continue;
        }
        now.t0=now.t1=0;
        if(x<=ans.t1)printf("%d\n",find1(L,x));
        else printf("%d\n",find0(R,ans.t0+ans.t1-x+1));
    }
}
int main()
{
    T=read();
    while(T--)work();
    return 0;
}