UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214982#2037. aKXG1004983ms95252kbC++111.6kb2024-11-25 19:11:542024-11-25 23:01:33

answer

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct node {
    long long l, r, ans;
    node() : l(0), r(0), ans(0) {}
    node(char s) : l(s == ')'), r(s == '('), ans(0) {}
    node(long long l, long long r, long long ans) : l(l), r(r), ans(ans) {}
};
node merge(node a, node b) {
    long long newans = min(a.r, b.l);
    return node(a.l + b.l - newans, a.r + b.r - newans, a.ans + b.ans + 2 * newans);
}
struct segmenttree {
    char s[1000010];
    node val[4000010];
    void pushup(int p) {
        val[p] = merge(val[p << 1], val[p << 1 | 1]);
    }
    void build(int p, int l, int r) {
        if (l == r) {
            val[p] = node(s[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        pushup(p);
        // printf("%d %d %d : %lld %lld %lld\n", p, l, r, val[p].l, val[p].r, val[p].ans);
    }
    node query(int p, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return val[p];
        }
        node ans;
        int mid = (l + r) >> 1;
        if (L <= mid) {
            ans = merge(ans, query(p << 1, l, mid, L, R));
        }
        if (R > mid) {
            ans = merge(ans, query(p << 1 | 1, mid + 1, r, L, R));
        }
        return ans;
    }
} sgt;
int n, q, l, r;
int main() {
    scanf("%s", sgt.s + 1);
    scanf("%d", &q);
    n = strlen(sgt.s + 1);
    sgt.build(1, 1, n);
    for (int i = 1; i <= q; i++) {
        scanf("%d%d", &l, &r);
        printf("%lld\n", sgt.query(1, 1, n, l, r).ans);
    }
    return 0;
}

详细

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

Test #1:

score: 10
Accepted
time: 15ms
memory: 94276kb

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

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: 20ms
memory: 94276kb

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: 16ms
memory: 94280kb

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: 8ms
memory: 94276kb

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: 19ms
memory: 94280kb

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: 1182ms
memory: 95252kb

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: 1215ms
memory: 95248kb

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: 1237ms
memory: 95248kb

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: 1264ms
memory: 95248kb

input:

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

output:

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

result:

ok 1000000 lines