UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215025#2037. anaroto20221004810ms67668kbC++1.5kb2024-11-25 20:08:552024-11-25 23:08:23

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int MN=1e6+5;
ll n,q;
struct tree{
    ll lsum,rsum,l,r;
    void clear(){lsum=rsum=0;}
}t[MN<<2];
char ch[MN];
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
void update(ll p){
    ll num=min(t[ls].lsum,t[rs].rsum);
    t[p].lsum=t[ls].lsum+t[rs].lsum-num;
    t[p].rsum=t[ls].rsum+t[rs].rsum-num;
}
void build(ll p, ll l, ll r){
    t[p].l=l;t[p].r=r;
    if(l==r){
        if(ch[l]=='(') t[p].lsum=1;
        else t[p].rsum=1;
        return;
    }
    ll mid=l+r>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    update(p);
}
tree query(ll p, ll l, ll r){
    if(l<=t[p].l&&t[p].r<=r) return t[p];
    ll mid=(t[p].l+t[p].r)>>1;tree res;res.clear();
    if(r<=mid) return query(ls,l,r);
    if(l>mid) return query(rs,l,r);
    tree lc=query(ls,l,r),rc=query(rs,l,r);
    ll num=min(lc.lsum,rc.rsum);
    res.lsum=lc.lsum+rc.lsum-num;
    res.rsum=lc.rsum+rc.rsum-num;
    return res;
}
int main(){
    scanf("%s",ch+1);n=strlen(ch+1);
    build(1,1,n);
    q=read();while(q--){
        ll l=read(),r=read();
        tree ans=query(1,l,r);
        write((r-l+1)-ans.lsum-ans.rsum);putchar('\n');
    }
    return 0;
}

详细

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

Test #1:

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

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

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

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

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

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

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: 1138ms
memory: 67668kb

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: 1242ms
memory: 67668kb

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: 1236ms
memory: 67668kb

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: 1194ms
memory: 67668kb

input:

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

output:

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

result:

ok 1000000 lines