首页 > 代码库 > 【hdu5217-括号序列】线段树
【hdu5217-括号序列】线段树
题意：给一串括号，有2个操作，1。翻转某个括号。2。查询某段区间内化简后第k个括号是在原序列中的位置。1 ≤ N,Q ≤ 200000.
题解：
可以知道，化简后的序列一定是)))((((这种形式的。
线段树每个节点就存对应区间内化简后的ls也就是)的数量，rs也就是(的数量。
然后我先把区间[l,r]找出来合并一遍，找出第k个是哪一种扩号。
问题转化为找区间[l,r]中的第kk个左扩号或者右括号。
我们可以发现，如果是)这种括号，区间从左到右合并的时候是单调不减的。
同理，(这种括号，区间从右往左合并的时候也是单调不减的。
然后我是变成从左往右的第kk个），或者从右往左的第kk个（。
[l,r]这个区间在线段树里可能由若干个区间组合而来，我们就根据左右括号的不同从左或从右合一遍，恰好遇到第kk个的时候就进去找。这个找就简单很多，因为它就是在线段树上走一遍的。
细节挺多的。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7
8 const int N=200010;
9 int n,m,tl,cl,c[N];
10 char s[N];
11 struct node{
12 int l,r,lc,rc,ls,rs;// ls ))) rs (((
13 }t[2*N];
14
15 int maxx(int x,int y){return x>y ? x:y;}
16
17 node upd(node x,node lc,node rc)
18 {
19 x.ls=lc.ls;
20 x.rs=rc.rs;
21 int sum=rc.ls-lc.rs;
22 if(sum>0) x.ls+=sum;
23 else x.rs+=-sum;
24 // x.ls=maxx(0,lc.ls+rc.ls-lc.rs);
25 // x.rs=maxx(0,rc.rs+lc.rs-rc.ls);
26 return x;
27 }
28
29 int bt(int l,int r)
30 {
31 int x=++tl;
32 t[x].l=l;t[x].r=r;
33 t[x].lc=t[x].rc=0;
34 t[x].ls=t[x].rs=0;
35 if(l<r)
36 {
37 int mid=(l+r)/2;
38 t[x].lc=bt(l,mid);
39 t[x].rc=bt(mid+1,r);
40 int lc=t[x].lc,rc=t[x].rc;
41 t[x]=upd(t[x],t[lc],t[rc]);
42 }
43 else
44 {
45 if(s[l]==‘)‘) t[x].ls=1;
46 else t[x].rs=1;
47 }
48 return x;
49 }
50
51 void change(int x,int p)
52 {
53 if(t[x].l==t[x].r) {swap(t[x].ls,t[x].rs);return ;}
54 int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)/2;
55 if(p<=mid) change(lc,p);
56 else change(rc,p);
57 t[x]=upd(t[x],t[lc],t[rc]);
58 }
59
60 void query(int x,int l,int r)
61 {
62 if(t[x].l==l && t[x].r==r) {c[++cl]=x;return;}
63 int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)/2;
64 if(r<=mid) query(lc,l,r);
65 else if(l>mid) query(rc,l,r);
66 else
67 {
68 query(lc,l,mid);
69 query(rc,mid+1,r);
70 }
71 }
72
73 int fd(int x,int k,int tmp)
74 {
75 if(t[x].l==t[x].r) return t[x].l;
76 int lc=t[x].lc,rc=t[x].rc;
77 if(tmp==0)
78 {
79 if(t[lc].ls>=k) return fd(lc,k,tmp);
80 return fd(rc,k-t[lc].ls+t[lc].rs,tmp);
81 }
82 else
83 {
84 if(t[rc].rs>=k) return fd(rc,k,tmp);
85 return fd(lc,k-t[rc].rs+t[rc].ls,tmp);
86 }
87 }
88
89 int main()
90 {
91 freopen("a.in","r",stdin);
92 freopen("a.out","w",stdout);
93 int T;
94 scanf("%d",&T);
95 while(T--)
96 {
97 scanf("%d%d",&n,&m);
98 scanf("%s",s+1);
99 tl=0;bt(1,n);
100 for(int i=1;i<=m;i++)
101 {
102 int tmp,x,l,r,k,ans;
103 scanf("%d",&tmp);
104 if(tmp==1)
105 {
106 scanf("%d",&x);
107 change(1,x);
108 }
109 else
110 {
111 scanf("%d%d%d",&l,&r,&k);
112 cl=0;query(1,l,r);
113 node now=t[c[1]];
114 for(int j=2;j<=cl;j++) now=upd(now,now,t[c[j]]);
115 if(now.ls+now.rs<k) {printf("-1\n");continue;}
116 if(now.ls>=k)
117 {
118 node p0=t[c[1]],p1;
119 if(p0.ls>=k) ans=fd(c[1],k,0);
120 else
121 {
122 for(int j=2;j<=cl;j++)
123 {
124 p1=upd(p1,p0,t[c[j]]);
125 if(p1.ls>=k)
126 {
127 ans=fd(c[j],k-p0.ls+p0.rs,0);
128 break;
129 }
130 p0=p1;
131 }
132 }
133 }
134 else
135 {
136 k=now.ls+now.rs-k+1;
137 node p0=t[c[cl]],p1;
138 if(p0.rs>=k) ans=fd(c[cl],k,1);
139 else
140 {
141 for(int j=cl-1;j>=1;j--)
142 {
143 p1=upd(p1,t[c[j]],p0);
144 if(p1.rs>=k) {ans=fd(c[j],k-p0.rs+p0.ls,1);break;}
145 p0=p1;
146 }
147 }
148 }
149 printf("%d\n",ans);
150 }
151 }
152 }
153 return 0;
154 }
【hdu5217-括号序列】线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。