UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215038#2037. awangyaxu1231006365ms157152kbC++111.9kb2024-11-25 20:47:302024-11-25 23:10:00

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<deque>
#include<cstring>
#include<stack>
using namespace std;
#define int long long
const int N=1e6+10;
char s[N];
int q,n,last[N],aa[N];
vector<int> v[N],vv[N];
struct mm{
	int l,r,id;
}a[N];
struct mmm{
	int l,r,mx;
}t[4*N];
struct node{
	int id;
	char s;
};
bool cmp(mm x,mm y){
	return x.r<y.r;
}
stack<node> ss;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void build(int p,int l,int r){
	t[p].l=l;
	t[p].r=r;
	t[p].mx=0;
	if(l==r)
	return;
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void pushup(int p){
	t[p].mx=t[p*2].mx+t[p*2+1].mx;
}
void change(int p,int pos,int val){
	if(t[p].l==t[p].r&&t[p].l==pos){
		t[p].mx=val;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(pos<=mid)
	change(p*2,pos,val);
	else
	change(p*2+1,pos,val);
	pushup(p);
}
int query(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r)
	return t[p].mx;
	int mid=(t[p].l+t[p].r)>>1,ans=0;
	if(l<=mid)
	ans+=query(p*2,l,r);
	if(r>mid)
	ans+=query(p*2+1,l,r);
	return ans;
}
signed main(){
	cin>>(s+1);
	n=strlen(s+1);
	node xxx;
	xxx.s='a';
	xxx.id=0;
	ss.push(xxx);
	for(int i=1;i<=n;i++){
		last[i]=0;
		bool ff=0;
		if(s[i]==')'){
			node x;
			x=ss.top();
			if(x.s=='('){
				last[i]=x.id;
				ss.pop();
				ff=1;
			}
			
		}
		node xx;
		xx.s=s[i];
		xx.id=i;
		if(ff==0)
		ss.push(xx);
	}
	q=read();
	for(int i=1;i<=q;i++){
		a[i].l=read();
		a[i].r=read();
		v[a[i].r].push_back(i);
	}
	build(1,0,n);
	for(int i=1;i<=n;i++){
		change(1,last[i],2);
		for(int j=0;j<v[i].size();j++){
			int x=v[i][j];
			aa[x]=query(1,a[x].l,i);
		}
	}
	for(int i=1;i<=q;i++){
		cout<<aa[i]<<'\n';
	}
	return 0;
}

详细

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

Test #1:

score: 10
Accepted
time: 16ms
memory: 48236kb

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

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

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

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

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

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

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

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

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

input:

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

output:

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

result:

ok 1000000 lines