UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214981#2037. aThySecret1004602ms43160kbC++112.4kb2024-11-25 19:04:242024-11-25 23:01:16

answer

#include <bits/stdc++.h>

using namespace std;

// #define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1000010;
const int INF = 0x3f3f3f3f;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int n, q;
char str[N];

struct SegsTree
{
    #define lc u << 1
    #define rc u << 1 | 1
    struct Node { int l, r, sum, lft, rht; } tr[N << 2];

    friend Node operator + (const Node &a, const Node &b)
    {
        Node res = Node{a.l, b.r, 0, 0, 0};
        res.sum = a.sum + b.sum, res.lft = a.lft, res.rht = b.rht;
        int rest = min(a.rht, b.lft);
        res.sum += 2 * rest, res.lft += b.lft - rest, res.rht += a.rht - rest;
        return res;
    }

    inline void pushup(int u) { tr[u] = tr[lc] + tr[rc]; }

    void build(int u, int l, int r)
    {
        tr[u].l = l, tr[u].r = r;
        if (l == r)
        {
            if (str[l] == '(') tr[u].rht = 1;
            else tr[u].lft = 1;
            return;
        }
        int mid = l + r >> 1;
        build(lc, l, mid), build(rc, mid + 1, r);
        pushup(u);
    }

    Node query(int u, int l, int r)
    {
        if (l <= tr[u].l && tr[u].r <= r)
            return tr[u];
        int mid = tr[u].l + tr[u].r >> 1;
        if (l > mid) return query(rc, l, r);
        else if (r <= mid) return query(lc, l, r);
        else return query(lc, l, r) + query(rc, l, r);
    }
} SGT;

signed main()
{
    scanf("%s%d", str + 1, &q), n = strlen(str + 1);
    SGT.build(1, 1, n);

    // cout << SGT.query(1, 1, n).sum << '\n';

    while (q --)
    {
        int l, r; read(l, r);
        cout << SGT.query(1, l, r).sum << '\n';
    }

    return 0;
}

详细

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

Test #1:

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

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

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

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

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

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

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

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

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

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

input:

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

output:

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

result:

ok 1000000 lines