UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215028#2037. aInvisible_H1005663ms136712kbC++1.5kb2024-11-25 20:18:342024-11-25 23:08:52

answer

#include<bits/stdc++.h>
using namespace std;
const int MX=1000010,INF=0x3f3f3f3f;
struct node{
	int lc,rc,sum;
}tree[MX<<5];
int head[MX],root[MX],cnt=0;
inline void update(int now){
	tree[now].sum=tree[tree[now].lc].sum+tree[tree[now].rc].sum;
}
inline int new_node(int now){
	tree[++cnt]=tree[now];
	return cnt;
}
inline void add_node(int now,int val){tree[now].sum=val;}
void build(int &now,int lt,int rt){
	if(lt==rt)  return ;
	int mid=(lt+rt-1)>>1;
	build(tree[now].lc,lt,mid),build(tree[now].rc,mid+1,rt);
}
void add(int &now,int lt,int rt,int pos,int val){
	if(lt>pos||pos>rt)  return ;
	now=new_node(now);
	if(lt==rt)  return add_node(now,val);
	int mid=(lt+rt-1)>>1;
	add(tree[now].lc,lt,mid,pos,val),add(tree[now].rc,mid+1,rt,pos,val);
	return update(now);
}
int cy(int now,int lt,int rt,int l,int r){
	if(lt>r||rt<l)  return 0;
	if(l<=lt&&rt<=r)  return tree[now].sum;
	int mid=(lt+rt-1)>>1;
	return cy(tree[now].lc,lt,mid,l,r)+cy(tree[now].rc,mid+1,rt,l,r);
}

int input[MX],n,w[MX];
stack<int>st;
signed main(){
	string s;cin>>s;n=s.size();
	for(int i=1;i<=n;i++)  input[i]=(s[i-1]=='(');
	for(int i=1;i<=n;i++){
		if(input[i])  st.push(i);
		else  if(!st.empty())  w[i]=st.top(),st.pop();
		// printf("%d ",w[i]);
	}
	build(root[0],1,n);
	for(int i=1;i<=n;i++){
		root[i]=root[i-1];
		add(root[i],1,n,w[i],1);
	}
	int q;scanf("%d",&q);
	while(q--){
		int l,r;scanf("%d%d",&l,&r);
		printf("%d\n",(cy(root[r],1,n,l,n)<<1));
	}
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1348kb

input:

(()))())))(())()())()()))((((()()))((((()((())()))(()((((()(())(())(()))())()())()())(())(()()((((((...

output:

854
136
108
12
836
206
550
252
536
266
220
344
830
502
170
290
522
526
464
98
160
10
840
298
332
272...

result:

ok 1000 lines

Test #2:

score: 10
Accepted
time: 0ms
memory: 1344kb

input:

)))((()())((())((()()())())(((())())((()((())(())()((((((())))((()(()())))(()()(())())()))(()()))(((...

output:

30
22
96
382
252
154
386
56
434
102
590
456
114
56
346
252
324
12
138
184
320
52
380
470
64
476
40
4...

result:

ok 1000 lines

Test #3:

score: 10
Accepted
time: 0ms
memory: 1348kb

input:

(()((())))))))((())(()()))()))()()())(()))(())))))))(((())((((((((((()((()())()(()(())(()())(()))(((...

output:

674
192
100
168
206
244
378
746
184
196
196
602
414
302
224
358
232
482
154
448
168
704
232
232
810
...

result:

ok 1000 lines

Test #4:

score: 10
Accepted
time: 0ms
memory: 1352kb

input:

))))))))()))())()(()()())()())(((()())(((()(((()()))(()()()))())(()()(()()())()(())()())))))()((((()...

output:

168
378
240
380
548
324
54
492
724
276
184
398
66
452
404
192
192
594
192
128
918
424
516
46
108
430...

result:

ok 1000 lines

Test #5:

score: 10
Accepted
time: 0ms
memory: 1340kb

input:

((())))(()((()()))()))))((((()()()()()()()))()()(()(())(()((()))()((())))))()(((()())()))()())))(())...

output:

634
386
334
6
246
372
226
424
274
168
254
448
312
112
532
126
594
780
112
150
68
470
260
150
22
322
...

result:

ok 1000 lines

Test #6:

score: 10
Accepted
time: 0ms
memory: 1344kb

input:

))((()))()(())())(()()))))()()((((()()())()((())(())))))(())))()())()()(())()(())())(()())))(()()))(...

output:

728
224
580
200
784
152
280
194
0
664
278
260
630
328
816
470
388
736
82
132
406
440
140
12
276
776
...

result:

ok 1000 lines

Test #7:

score: 10
Accepted
time: 1414ms
memory: 136448kb

input:

((((()))()()())(()))((()())(((())))(()((()))))))()()))()))((((()(()(()()()(()(())(()())))(((()())))(...

output:

142860
235344
446706
759772
134088
748980
83870
685562
31730
572204
366368
67746
18554
603330
946486...

result:

ok 1000000 lines

Test #8:

score: 10
Accepted
time: 1399ms
memory: 136444kb

input:

())))()))))(()))()())(()(()))((()))))(()))((())()((()(()()((())(())()))(()))))())(((()(())()(())()()...

output:

583148
425884
255036
448502
200322
256890
167684
114904
55236
440164
138094
879918
580038
452166
984...

result:

ok 1000000 lines

Test #9:

score: 10
Accepted
time: 1382ms
memory: 136444kb

input:

)()((()())(())())(()())))(((()())()()(((((()(()()(()(())(()())((()(((()()))()))))()(((())(((((()()()...

output:

47942
241400
323510
553980
111490
20570
51892
169422
82080
124416
107806
804528
123414
274334
135650...

result:

ok 1000000 lines

Test #10:

score: 10
Accepted
time: 1468ms
memory: 136712kb

input:

())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...

output:

487878
425694
419984
176404
493462
782462
63276
27548
109942
308166
354282
302574
697816
3128
144748...

result:

ok 1000000 lines