UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214985#2037. aSTASISZHY1004541ms35036kbC++111.7kb2024-11-25 19:14:082024-11-25 23:02:11

answer

// Problem: A. a
// Contest: undefined - NOIP2024训练赛 13
// URL: http://noi.ac/contest/1165/problem/2037
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define PII pair<int, int>

using namespace std;

const int N = 1e6 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m, q, ans;

struct Tree
{
	int l, r, suml, sumr;
}tr[N << 2];

string s;

inline void pushup(int x) 
{
	tr[x].suml = tr[2 * x].suml + tr[2 * x + 1].suml - min(tr[2 * x].suml, tr[2 * x + 1].sumr);
	tr[x].sumr = tr[2 * x].sumr + tr[2 * x + 1].sumr - min(tr[2 * x].suml, tr[2 * x + 1].sumr);
}

void build(int x, int l, int r)
{
	tr[x].l = l, tr[x].r = r;
	if(l == r)
	{
		tr[x].suml = (s[l] == '(');
		tr[x].sumr = (s[r] == ')');
		return;
	}
	int mid = l + r >> 1;
	build(2 * x, l, mid);
	build(2 * x + 1, mid + 1, r);
	pushup(x);
}

inline Tree merge(Tree ls, Tree rs)
{
	Tree res = {ls.l, rs.r, 0, 0};
	res.suml = ls.suml + rs.suml - min(ls.suml, rs.sumr);
	res.sumr = ls.sumr + rs.sumr - min(ls.suml, rs.sumr);
	return res;
}

Tree query(int x, int l, int r)
{
	if(tr[x].l >= l && tr[x].r <= r) return tr[x];
	int mid = tr[x].l + tr[x].r >> 1;
	if(l > mid) return query(2 * x + 1, l, r);
	else if(r <= mid) return query(2 * x, l, r);
	else return merge(query(2 * x, l, r), query(2 * x + 1, l, r));
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> s; n = s.size(), s = ' ' + s;
	build(1, 1, n);
	cin >> q;
	while(q --)
	{
		int l, r; cin >> l >> r;
		Tree now = query(1, l, r);
		cout << r - l + 1 - now.suml - now.sumr << '\n';
	}
	return 0;
}

详细

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

Test #1:

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

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: 1308kb

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: 1ms
memory: 1304kb

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: 1304kb

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: 1308kb

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: 1308kb

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: 1135ms
memory: 35036kb

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: 1137ms
memory: 35036kb

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: 1126ms
memory: 35032kb

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: 1142ms
memory: 35036kb

input:

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

output:

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

result:

ok 1000000 lines