UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215039#2037. awhereismy25607ms5208kbC++2.0kb2024-11-25 20:48:072024-11-25 23:10:19

answer

/*****************************************
Note  :
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
#define LL long long
#define IL inline
const int N = 1e6+10;
const int INF = 0x3f3f3f3f;
using namespace std;
IL int read()
{
    char ch = getchar();
    int f = 1, num = 0;
    while(ch>'9'||ch<'0')
    {
        if(ch=='-') f = -1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        num = num*10+ch-'0', ch = getchar();
    return num*f;
}
int n,q;
int mn[N],stk[N],tp;
string s;
int rt[N],ls[N*4],rs[N*4],sum[N*4],tot;
void upd(int la,int ne,int l,int r,int x)
{
    sum[ne]=sum[la]+1;
    if(l==r)
        return;
    ls[ne]=ls[la],rs[ne]=rs[la];
    int mid=l+r>>1;
    if(x<=mid)
    {
        ls[ne]=++tot;
        upd(ls[la],ls[ne],l,mid,x);
    }
    else
    {
        rs[ne]=++tot;
        upd(rs[la],rs[ne],mid+1,r,x);
    }
}
int qsum(int la,int ne,int l,int r,int L,int R)
{
//    printf("%d %d %d %d\n",l,r,sum[ne],sum[la]);
    if(L<=l&&r<=R)
        return sum[ne]-sum[la];
    int mid=l+r>>1,res=0;
    if(L<=mid)
        res+=qsum(ls[la],ls[ne],l,mid,L,R);
    if(R>mid)
        res+=qsum(rs[la],rs[ne],mid+1,r,L,R);
    return res;
}
int main()
{
	cin>>s;
	n=s.size();
	memset(mn,0x3f,sizeof(mn));
	for(int i = 0;i<n;i++)
    {
        if(s[i]=='(')
            stk[++tp]=i+1;
        else
        {
            if(tp)
                mn[stk[tp--]]=i+1;
        }
    }
    rt[0]=++tot;
    for(int i = 1;i<=n;i++)
    {
        if(mn[i]<=n)
        {
            rt[i]=++tot;
            upd(rt[i-1],rt[i],1,n,mn[i]);
//            printf("%d %d\n",i,mn[i]);
        }
        else rt[i]=rt[i-1];
    }
	q=read();
	while(q--)
    {
        int l=read(),r=read();
//        printf("rt:%d %d\n",rt[l-1],rt[r]);
        int res=qsum(rt[l-1],rt[r],1,n,1,r)*2;
        printf("%d\n",res);
    }
}

Details

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

Test #1:

score: 10
Accepted
time: 3ms
memory: 5204kb

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

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

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

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

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

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: 0
Runtime Error

input:

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

output:


result:


Test #8:

score: 0
Runtime Error

input:

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

output:


result:


Test #9:

score: 0
Runtime Error

input:

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

output:


result:


Test #10:

score: 0
Runtime Error

input:

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

output:


result: