QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#626487#5403. 树数术Flamire100 ✓893ms259644kbC++172.2kb2024-10-10 09:35:562024-10-10 09:35:56

Judging History

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

  • [2024-10-10 09:35:56]
  • 评测
  • 测评结果:100
  • 用时:893ms
  • 内存:259644kb
  • [2024-10-10 09:35:56]
  • 提交

answer

#include <bits/stdc++.h>
#define N 700011
#define pii pair<int,int>
#define s1 first
#define s2 second
#define ll long long
using namespace std;
int n,m,q,a[N];
vector<int> G[N];int dfn[N],siz[N],dep[N],st[21][N],rk[N],clk,lg[N];
void dfs(int u,int F)
{
	dfn[u]=++clk;dep[u]=dep[F]+1;rk[clk]=st[0][clk]=u;siz[u]=1;
	for(int v:G[u])if(v^F)
	{
		dfs(v,u);
		st[0][clk]=u;siz[u]+=siz[v];
	}
}
int lca(int x,int y)
{
	if(x==y)return x;
	if(dfn[x]>dfn[y])swap(x,y);
	int logl=lg[dfn[y]-dfn[x]];
	int u1=st[logl][dfn[x]],u2=st[logl][dfn[y]-(1<<logl)];
	return dep[u1]<dep[u2]?u1:u2;
}
int rg[21][N];
int qlca(int l,int r)
{
	int logl=lg[r-l+1];
	int u1=rg[logl][l],u2=rg[logl][r-(1<<logl)+1];
	return lca(u1,u2);
}
struct kueri{int x,y,k,id;};
vector<kueri> vk[N];
vector<pii> vv;
int ql[N],qr[N];
ll ans[N];
bool insub(int u,int v){return dfn[u]<=dfn[v]&&dfn[v]<dfn[u]+siz[u];}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<n;++i){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}
	dfs(1,0);
	for(int i=1;i<=19;++i)
	{
		for(int j=1;j+(1<<i)-1<n;++j)
		{
			int u1=st[i-1][j],u2=st[i-1][j+(1<<i-1)];
			st[i][j]=dep[u1]<dep[u2]?u1:u2;
		}
	}
	lg[0]=-1;for(int i=1;i<N;++i)lg[i]=lg[i>>1]+1;
	for(int i=1;i<=m;++i)scanf("%d",a+i),rg[0][i]=a[i];
	for(int i=1;i<=19;++i)
	{
		for(int j=1;j+(1<<i)-1<=m;++j)
		{
			rg[i][j]=lca(rg[i-1][j],rg[i-1][j+(1<<i-1)]);
		}
	}
	for(int i=1;i<=q;++i)
	{
		int k;scanf("%d",&k);
		for(int j=1;j<=k;++j)scanf("%d%d",ql+j,qr+j);
		int x=-1;
		for(int j=1;j<=k;++j)
		{
			vk[ql[j]].push_back({ql[j],qr[j],x,i});
			if(~x)x=lca(x,qlca(ql[j],qr[j]));
			else x=qlca(ql[j],qr[j]);
		}
	}
	for(int i=m;i;--i)
	{
		int x=a[i];
		while(!vv.empty()&&!insub(vv.back().s1,a[i]))vv.pop_back();
		vv.push_back({x,i});
		for(kueri k:vk[i])
		{
			int L=0,R=(int)vv.size()-1,rb=-1;
			if(~k.k)
			{
				while(L<=R)
				{
					int M=L+R>>1;
					if(insub(vv[M].s1,k.k))rb=M,L=M+1;else R=M-1;
				}
			}
			else rb=(int)vv.size()-1;
			L=0,R=(int)vv.size()-1;int lb=vv.size();
			while(L<=R)
			{
				int M=L+R>>1;
				if(vv[M].s2<=k.y)lb=M,R=M-1;else L=M+1;
			}
			ans[k.id]+=max(0,rb-lb+1);
		}
	}
	for(int i=1;i<=q;++i)printf("%lld\n",ans[i]);
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 893ms
memory: 259644kb

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:

121987
139520
87432
42773
311773
194269
177810
454211
417130
299450
366103
227736
186417
163975
292497
216139
401719
16634
192685
27351
52127
54938
142169
275076
339876
117003
51132
229206
187647
350043
398455
83905
100490
338070
356664
60211
366172
142627
16903
222331
471095
184145
170758
238393
14...

result:

ok 233333 lines

Subtask #2:

score: 20
Accepted

Test #2:

score: 20
Accepted
time: 823ms
memory: 232680kb

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:

211594
160846
176729
128251
32662
70710
74884
9095
68282
91324
154262
24279
31878
173468
75265
139715
91660
87525
194302
16875
81535
172911
29145
20483
151883
5255
9548
58890
38076
94152
14358
74859
48870
23981
41390
60976
13795
125823
427
26641
130620
174231
73241
55291
2364
78864
23391
4866
36002
...

result:

ok 699992 lines

Subtask #3:

score: 30
Accepted

Test #3:

score: 30
Accepted
time: 78ms
memory: 133404kb

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: 40
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #4:

score: 40
Accepted
time: 766ms
memory: 234328kb

input:

699991 700000 233333
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 41
44 43
45 43
46 45
47 45
48 47
49 47
50 49
51 ...

output:

129494
81962
52243
146978
53574
96058
72866
34286
184144
65111
77323
90610
168465
55995
66592
60741
118767
119126
150909
50321
114540
119576
122486
84546
19256
4585
22720
133448
124662
148500
173817
100034
135869
88299
68523
62880
73171
139874
90190
100601
100854
137709
106869
126901
40873
93249
136...

result:

ok 233333 lines