QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243391#5403. 树数术hhhgjy30 97ms61448kbC++142.8kb2023-11-08 09:53:452023-11-08 09:53:45

Judging History

你现在查看的是最新测评结果

  • [2023-11-08 09:53:45]
  • 评测
  • 测评结果:30
  • 用时:97ms
  • 内存:61448kb
  • [2023-11-08 09:53:45]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,M,Q,Log[700005],A[700005],in[700005],out[700005],tot1,lef[700005],q[700005],tail;
int mn[20][700005],mx[20][700005];
int getmin(int l,int r){
	int len=Log[r-l+1];
	return min(mn[len][l],mn[len][r-(1<<len)+1]);
}
int getmax(int l,int r){
	int len=Log[r-l+1];
	return max(mx[len][l],mx[len][r-(1<<len)+1]);
}
int getpos1(int l,int r,int v){
	if(getmin(l,r)>v)return 0;
	int pl=l,pr=r,ans=0;
	while(pl<=pr){
		int mid=pl+pr>>1;
		if(getmin(l,mid)<=v)ans=mid,pr=mid-1;
		else pl=mid+1;
	} return ans;
}
int getpos2(int l,int r,int v){
	if(getmax(l,r)<v)return 0;
	int pl=l,pr=r,ans=0;
	while(pl<=pr){
		int mid=pl+pr>>1;
		if(getmax(l,mid)>=v)ans=mid,pr=mid-1;
		else pl=mid+1;
	} return ans;
}
vector<int>road[700005];
void dfs(int u,int fa){
	in[u]=out[u]=++tot1;
	for(int v:road[u]){
		if(v==fa)continue;
		dfs(v,u);out[u]=out[v];
	}
}
int rt[700005],tot,son[14000005][2],cnt[14000005];
void ins(int &p,int q,int l,int r,int pos){
	p=++tot;son[p][0]=son[q][0],son[p][1]=son[q][1],cnt[p]=cnt[q]+1;
	if(l==r)return;int mid=l+r>>1;
	if(pos<=mid)ins(son[p][0],son[q][0],l,mid,pos);
	else ins(son[p][1],son[q][1],mid+1,r,pos);
}
int query(int p,int q,int l,int r,int a,int b){
	if(a<=l&&r<=b)return cnt[p]-cnt[q];int mid=l+r>>1,res=0;
	if(a<=mid)res+=query(son[p][0],son[q][0],l,mid,a,b);
	if(b>mid)res+=query(son[p][1],son[q][1],mid+1,r,a,b);
	return res;
}
int tot2,L[7000005],R[7000005];
int main(){
	scanf("%d%d%d",&N,&M,&Q);
    for(int i=1;i<N;++i){
    	int u,v;scanf("%d%d",&u,&v);
    	road[u].push_back(v);road[v].push_back(u);
	} dfs(1,-1);
	for(int i=2;i<=M;++i)Log[i]=Log[i>>1]+1;
	for(int i=1;i<=M;++i){
		scanf("%d",&A[i]);
		while(tail&&in[A[q[tail]]]>=in[A[i]])--tail;
		lef[i]=q[tail];q[++tail]=i;
	}tail=0;
	for(int i=1;i<=M;++i){
		while(tail&&out[A[q[tail]]]<=out[A[i]])--tail;
		lef[i]=max(lef[i],q[tail]);q[++tail]=i;++lef[i];
	}
	for(int i=1;i<=M;++i)ins(rt[i],rt[i-1],1,M,lef[i]),mn[0][i]=in[A[i]],mx[0][i]=out[A[i]];
	for(int j=1;(1<<j)<=M;++j)for(int i=1;i+(1<<j)-1<=M;++i)mn[j][i]=min(mn[j-1][i],mn[j-1][i+(1<<j-1)]),mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1<<j-1)]);
	while(Q--){
		scanf("%d",&tot2);
		for(int i=1;i<=tot2;++i)scanf("%d%d",&L[i],&R[i]);
		int Mn=1e9,Mx=0;ll res=0;
		for(int i=1;i<=tot2;++i){
			if(i==1){
				res+=1ll*query(rt[R[i]],rt[L[i]-1],1,M,1,L[i]);
				Mn=getmin(L[i],R[i]);Mx=getmax(L[i],R[i]);
				continue;
			}
			int pos1=getpos1(L[i],R[i],Mn);
			int pos2=getpos2(L[i],R[i],Mx);
			if(!pos1||!pos2){
				Mn=min(Mn,getmin(L[i],R[i]));
				Mx=max(Mx,getmax(L[i],R[i]));
				continue;
			} pos1=max(pos1,pos2);
			res+=1ll*query(rt[R[i]],rt[pos1-1],1,M,1,L[i]);
			Mn=min(Mn,getmin(L[i],R[i])),Mx=max(Mx,getmax(L[i],R[i]));
		} printf("%lld\n",res);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

699990 699995 233333
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

448495
-520897
451773
-58083
-65613
-18280
506298
686256
-378308
344972
35658
-59626
-38219
1598010
785173
313664
850355
448075
407812
-458769
-52713
-9250
6480
-553904
7130
-452731
545802
179812
35432
-148412
79310
-144620
-552187
-965030
-242092
462420
-74593
665726
382058
-608642
475440
-441833
-...

result:


Subtask #2:

score: 0
Runtime Error

Test #2:

score: 0
Runtime Error

input:

699992 699994 699992
2 1
3 1
4 3
5 3
6 5
7 5
8 7
9 7
10 9
11 9
12 11
13 11
14 13
15 13
16 15
17 15
18 17
19 17
20 19
21 19
22 21
23 21
24 23
25 23
26 25
27 25
28 27
29 27
30 29
31 29
32 31
33 31
34 33
35 33
36 35
37 35
38 37
39 37
40 39
41 39
42 41
43 40
44 43
45 43
46 45
47 45
48 47
49 47
50 49
51 ...

output:

0
12051
38
7773
22599
-8507
-1
-225
3134
-7201
1678
-210881
7
-1427
-7
-12070
52535
-88650
-396
29391
-235715
15124
5342
-2966
-2972
2059
223645
-1746
12269
342364
-85
-208690
8389
-22060
-3367
13156
50081
-256495
5541
-67206
-5014
57
-69
235447
-74025
-29811
251496
23866
-1219
-222792
-843
36
-3117...

result:


Subtask #3:

score: 30
Accepted

Test #3:

score: 30
Accepted
time: 97ms
memory: 61448kb

input:

99998 99993 33333
2 1
3 1
4 3
5 3
6 5
7 5
8 7
9 7
10 9
11 9
12 11
13 11
14 13
15 13
16 15
17 15
18 17
19 17
20 19
21 19
22 21
23 21
24 23
25 23
26 25
27 25
28 27
29 27
30 29
31 24
32 31
33 31
34 33
35 33
36 35
37 35
38 37
39 37
40 39
41 39
42 41
43 41
44 43
45 43
46 45
47 45
48 47
49 47
50 49
51 49
...

output:

9733
11330
8403
5136
22207
23231
12686
27288
23739
20937
18153
16379
8991
14036
11669
14685
20272
18955
21680
7927
21383
23576
14834
5714
15707
10013
7905
13254
13883
10446
16140
16796
11009
11912
15761
20419
11157
12192
14327
18260
19095
5239
4114
16522
7412
5005
16844
8747
19377
22600
12023
9161
9...

result:

ok 33333 lines

Subtask #4:

score: 0
Skipped

Dependency #1:

0%