QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#585076#9373. Query on Treeucup-team3586#TL 936ms243936kbC++236.3kb2024-09-23 18:47:092024-09-23 18:47:10

Judging History

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

  • [2024-09-23 18:47:10]
  • 评测
  • 测评结果:TL
  • 用时:936ms
  • 内存:243936kb
  • [2024-09-23 18:47:09]
  • 提交

answer

#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int B=12;
int inp[1<<18],a[1<<18],fa[1<<18];
int rt[1<<18];
vector<int> e[1<<18],g[1<<18];
int to[1<<18],from[1<<18];
int in[1<<18],out[1<<18];
int le[1<<18][15],ri[1<<18][15];
const int N=1<<18;
struct BIT{int tr[1<<18];
pair<int,int> opers[1<<23];
int opsz;
void add(int x,int k,bool lo=1)
{
	if(lo) opers[++opsz]={x,k};
	while(x<N)tr[x]+=k,x+=x&(-x);
}
int find(int x)
{
	int r=0;
	while(x)r+=tr[x],x-=x&(-x);
	return r;
}
void clr()
{
	while(opsz)
	{
		auto [x,y]=opers[opsz--];
		add(x,-y,0);
	}
}
}T;
int n,m;
int arr[1<<18];
struct SGT
{
	int tag[1<<19];
	int f[1<<19];
	void build(int nl,int nr,int x)
	{
		tag[x]=0;
		if(nl==nr){f[x]=arr[nl];return;}
		int mid=(nl+nr)>>1;
		build(nl,mid,x<<1),
		build(mid+1,nr,(x<<1)+1);
		f[x]=max(f[x<<1],f[(x<<1)+1]);
		return ;
	}
	void pd(int x,int ls,int rs)
	{
		tag[ls]+=tag[x],tag[rs]+=tag[x],
		f[ls]+=tag[x],f[rs]+=tag[x];
		tag[x]=0;
	}
	void update(int nl,int nr,int l,int r,int x,int v)
	{
		if(nr<l||r<nl) return ;
		if(l<=nl&&nr<=r){f[x]+=v;tag[x]+=v;return;}
		int mid=(nl+nr)>>1;
		if(tag[x]) pd(x,x<<1,(x<<1)+1);
		update(nl,mid,l,r,x<<1,v);
		update(mid+1,nr,l,r,(x<<1)+1,v);
		f[x]=max(f[x<<1],f[(x<<1)+1]);
		return ;
	}
	void update(int nl,int nr,int t,int x,int v)
	{
		if(nl==nr){f[x]=v;tag[x]=0;return;}
		int mid=(nl+nr)>>1;
		if(tag[x]) pd(x,x<<1,(x<<1)+1);
		if(t<=mid) update(nl,mid,t,x<<1,v);
		else update(mid+1,nr,t,(x<<1)+1,v);
		f[x]=max(f[x<<1],f[(x<<1)+1]);
		return ;
	}
	int query(int nl,int nr,int l,int r,int x)
	{
		if(nr<l||r<nl) return -1e18;
		if(l<=nl&&nr<=r) return f[x];
		int mid=(nl+nr)>>1;
		if(tag[x]) pd(x,x<<1,(x<<1)+1);
		return max(query(nl,mid,l,r,x<<1),
			query(mid+1,nr,l,r,(x<<1)+1));
		// assert(f[x]==max(f[x<<1],f[(x<<1)+1]));
	}
}Q1,Q2;
int Kevin(int l,int r,int x)
{
	// printf("kevin %lld %lld %lld\n",l,r,x);
	if(l>r) return -1e18;
	int root=rt[l],val=T.find(root);
	// printf("%lld %lld %lld\n",l,r,x);
	Q1.update(1,n,l,r,1,x);
	int ans=Q1.query(1,n,l,r,1);
	if(root==0) return ans;
	// if(le[root][B]>l||r>ri[root][B])
	// {
		// for(int i=l,j=0; i!=root; i=fa[i],++j)
		// {
			// printf("%lld %lld %lld\n",i,j,le[i][j]);
		// }
		// printf("%lld\n",root);
		// printf("%lld %lld %lld %lld\n",le[root][B],l,r,ri[root][B]);
		// exit(2333);
	// }
	int global=Q1.query(1,n,le[root][B],ri[root][B],1);
	Q2.update(1,n,in[root],1,global+val);
	// for(int i=l; i<=r; ++i) a[i]+=x,ans=max(ans,a[i]+backup[root]);
	return ans+val;
}
int Haitang(int x,int v)
{
	// printf("haitang %lld %lld\n",x,v);
	T.add(in[x],v);
	T.add(out[x]+1,-v);
	Q2.update(1,n,in[x],out[x],1,v);
	return Q2.query(1,n,in[x],out[x],1);
}
int counter=0;
void dfs(int x)
{
	in[x]=++counter;
	for(int y:e[x]) dfs(y);
	out[x]=counter;
}
void solve()
{
	T.clr();
	n=read(),m=read();
	for(int i=1; i<=n; ++i) inp[i]=read(),
		e[i].clear(),g[i].clear();
	for(int i=1; i<n; ++i)
	{
		int u=read(),v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	queue<pair<int,int>> q;
	q.push({1,0});fa[1]=0;
	int qwq=0;
	while(!q.empty())
	{
		auto [x,awa]=q.front();q.pop();
		from[++qwq]=x,to[x]=qwq,a[qwq]=inp[x];
		for(int y:g[x]) if(y!=awa) q.push({y,x});
	}
	assert(qwq==n);
	int edges=0;
	for(int i=1; i<=n; ++i)
		for(int j:g[i]) if(to[i]<to[j])
			e[to[i]].push_back(to[j]),fa[to[j]]=to[i],++edges;
	assert(edges==n-1);
	// printf("%lld\n",edges);
	// for(int i=1; i<=n; ++i) sort(e[i].begin(),e[i].end());
	// for(int i=2; i<=n; ++i) assert(find
	// (e[fa[i]].begin(),e[fa[i]].end(),i)!=e[fa[i]].end());
	for(int i=n; i>=1; --i)
	{
		rt[i]=i;
		for(int j=1; j<=B; ++j) rt[i]=fa[rt[i]];
		sort(e[i].begin(),e[i].end());
		le[i][0]=ri[i][0]=i;
		for(int k=1; k<=B; ++k)
			le[i][k]=n+1,ri[i][k]=0;
		for(int j:e[i])
		{
			for(int k=0; k<B; ++k)
				le[i][k+1]=min(le[i][k+1],le[j][k]),
				ri[i][k+1]=max(ri[i][k+1],ri[j][k]);
		}
	}
	counter=0;
	dfs(1);
	for(int i=1; i<=n; ++i) arr[i]=a[i];
	Q1.build(1,n,1);
	for(int i=1; i<=n; ++i) arr[i]=-1e18;
	// for(int i=1; i<=n; ++i) if(le[i][B]<=ri[i][B])
		// arr[in[i]]=Q1.query(1,n,le[i][B],ri[i][B],1);
	for(int i=1; i<=n; ++i) arr[in[rt[i]]]=max(arr[in[rt[i]]],a[i]);
	Q2.build(1,n,1);
	while(m--)
	{
		int op=read(),x=to[read()],ans=-1e18;
		if(op==2)
		{
			int d=read(),v=read();
			for(int i=0,layer=d; x&&i<=d; ++i,x=fa[x])
			{
				// printf("%d %d\n",x,layer);
				int l=le[x][layer],r=ri[x][layer];
				// printf("go %lld %lld\n",l,r);
				ans=max(ans,Kevin(l,r,v));
				
				if(layer==0)break;
				--layer;
				l=le[x][layer],r=ri[x][layer];
				ans=max(ans,Kevin(l,r,v));
				
				if(x==1)
				{
					while(layer>0)
					{
						--layer;
						l=le[x][layer],r=ri[x][layer];
						ans=max(ans,Kevin(l,r,v));
					}
				}
				// printf("go %lld %lld\n",l,r);
			}
		}
		else if(op==1)
		{
			int d=read(),v=read();
			for(int i=0,y=0,layer=d; x&&i<=d; ++i,y=x,x=fa[x])
			{
				if(y&&layer)
				{
					int l=le[x][layer],r=ri[x][layer];
					int l1=le[y][layer-1],r1=ri[y][layer-1];
					if(r1==0)
					{
						ans=max(ans,Kevin(l,r,v));
					}
					else
					{
						ans=max(ans,Kevin(l,l1-1,v));
						ans=max(ans,Kevin(r1+1,r,v));
					}
				}
				else
				{
					int l=le[x][layer],r=ri[x][layer];
					// printf("go %lld %lld\n",l,r);
					ans=max(ans,Kevin(l,r,v));
				}
				--layer;
			}
		}
		else
		{
			int v=read();
			function<void(int)> dfs=[&](int x)
			{
				ans=max(ans,Kevin(x,x,v));
				for(int y:e[x]) dfs(y);
				return ;
			};
			dfs(x);
			// for(int i=0; i<B; ++i)
			// {
				// // printf("%d %d\n",x,layer);
				// int l=le[x][i],r=ri[x][i];
				// // printf("go %lld %lld\n",l,r);
				// ans=max(ans,Kevin(l,r,v));
			// }
			// // Haitang(l,r,v);
			// ans=max(ans,Haitang(x,v));
			
		}
		if(ans<-1e17) puts("GG");
		else printf("%lld\n",ans);
	}
	return ;
}
signed main()
{
	for(int T=read();T--;)
	{
		solve();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 165808kb

input:

1
5 5
1 2 1 3 2
1 2
2 3
2 4
4 5
2 2 1 0
1 2 1 3
3 4 -5
2 5 2 3
3 2 -1

output:

3
6
1
5
4

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 35ms
memory: 165884kb

input:

10000
3 9
42973045452542 34994498886390 -91733395797555
1 3
1 2
1 1 5 -71952967
3 1 -816873082
1 1 5 -842437577
2 3 7 254550528
3 3 -854082700
2 3 2 699808309
3 3 554885567
1 2 7 595565507
1 3 0 -318374053
3 2
-63158159333100 77264362049163 -99188430131116
1 2
3 2
2 2 4 -305866230
3 1 -549738403
3 5...

output:

GG
42972228579460
GG
42972483129988
-91734812202809
42973182938297
-91733557508933
GG
-91733875882986
77264056182933
77263506444530
7065382376488
7065749360235
7066534912965
-85115611272570
-85114714781312
96492412785032
-20428913156111
-20428197540063
96491742171666
-14945310996805
96491180203461
-...

result:

ok 200000 lines

Test #3:

score: 0
Accepted
time: 42ms
memory: 165552kb

input:

10000
4 32
-1057044448491 -93293078803919 -24212938548357 74427756948193
1 3
1 2
3 4
3 1 -82365883
1 2 9 -730670945
2 4 2 -618745828
2 1 2 774032949
3 3 6733210
3 3 -843683844
3 1 327410390
3 1 -865685600
1 4 6 -951367966
3 2 107763506
1 3 2 721870187
2 3 3 -530847597
2 2 1 451029291
3 2 231297873
3...

output:

74427674582310
GG
74427055836482
74427829869431
74427836602641
74426992918797
74427320329187
74426454643587
GG
-93292817648557
-93292095778370
74425923795990
-1057589620769
-93291944298803
74425228504438
74425430401539
-93291936231808
74425906008467
GG
-1058067327518
74424997886529
74424370598990
74...

result:

ok 200000 lines

Test #4:

score: 0
Accepted
time: 52ms
memory: 165524kb

input:

10000
5 21
-17119694111919 -49543801764535 15340078463236 -13731655847398 -41385234314814
3 2
1 5
1 4
1 2
3 5 865538081
3 4 551893736
2 3 9 797578233
1 3 0 -657534941
3 4 -507570975
1 1 2 352656478
3 5 951666995
2 5 3 524459610
3 4 819153725
2 4 0 955588629
3 5 -451248313
1 3 0 -251438755
1 4 0 -707...

output:

-41384368776733
-13731103953662
15340876041469
15340218506528
-13730813946404
15340571163006
-41382619531505
15341095622616
-13729470333069
-13728514744440
-41382546320208
15340844183861
-13729221899958
15340255675017
-13729490336654
-13729529150761
-13729624738248
15341124008689
15341173814500
GG
-...

result:

ok 200000 lines

Test #5:

score: 0
Accepted
time: 63ms
memory: 165480kb

input:

10000
7 53
-49257878340663 65913602617244 -77586447275975 37912663831730 -29965751459870 -24028915786606 -20711244730875
2 1
3 1
4 6
1 5
7 1
2 4
1 6 4 -614276625
3 7 -430532617
3 3 -970301980
1 1 4 767992650
2 1 4 88036223
2 3 5 -930151770
3 3 -816226996
1 2 1 -696978838
2 1 1 -877781309
2 5 2 58619...

output:

-20711859007500
-20712289540117
-77588031854580
GG
65913690653467
65912760501697
-77589690197123
37911124737345
65911882720388
65912468916628
65911745912774
-29967336843362
65911988615088
GG
37910494006281
65912545393218
-49259038263999
GG
65913255260627
GG
GG
65912963550828
-24029074909413
65912862...

result:

ok 200000 lines

Test #6:

score: 0
Accepted
time: 68ms
memory: 165584kb

input:

10000
10 4
71797802165245 -54234031880796 29183815458453 29504172959957 49372193603523 -16185389362615 39453295094243 663036651923 96744787191200 -50620611104201
5 8
5 1
1 2
4 7
7 10
2 4
5 6
3 9
3 2
3 7 -830615007
1 2 6 637860195
2 7 7 -843886558
3 8 273999944
10 8
-33479821641433 91082116968197 -34...

output:

39452464479236
GG
96743943304642
662466765309
91246631814706
-29877405744477
GG
GG
91081604757708
GG
91246614330784
-29877381879548
-4361386733251
89595437158302
-4360828297147
19337184792075
89595109336295
89594748412265
19336971357477
89594978989869
86993545918633
-84286253125550
GG
GG
52174855696...

result:

ok 200000 lines

Test #7:

score: 0
Accepted
time: 33ms
memory: 165556kb

input:

10000
3 9
42973045452542 34994498886390 -91733395797555
2 3
2 1
3 1 -988613092
1 2 0 308890489
1 1 0 472776476
2 2 2 -122992202
2 3 1 831940219
3 3 -612896282
3 3 -536438981
1 1 0 161104440
2 1 1 354965461
3 2
77441670935132 -63158159333100 77264362049163
3 1
2 1
1 3 4 -20585631
1 1 6 747193249
3 5
...

output:

42972056839450
34993819163787
42972529615926
42972406623724
34994528111804
-91734288358912
-91734824797893
42972567728164
42972922693625
GG
GG
GG
7064655135811
-61568732738930
7065157020537
-61568593058530
80122234728388
80122047274326
80122140239806
80121956639200
80121963373184
80121401404979
9259...

result:

ok 200000 lines

Test #8:

score: 0
Accepted
time: 52ms
memory: 165528kb

input:

10000
4 32
-1057044448491 -93293078803919 -24212938548357 74427756948193
3 2
4 1
1 2
1 2 8 639477246
1 4 0 510694922
2 1 0 421373363
2 3 4 -843809269
3 1 -620938865
3 3 -933234989
1 3 3 458028025
1 4 6 -951367966
3 2 107763506
1 3 2 721870187
2 3 3 -530847597
2 2 1 451029291
3 2 231297873
3 1 -69529...

output:

GG
74428267643115
-1056623075128
74427423833846
74426802894981
-24215336531480
74427260923006
GG
-24215228767974
-1057365953075
74426730075409
-1057445771381
-24215077288407
74426034783857
74426236680958
-24215069221412
74426712287886
74427585548383
74427327526258
-24215759758547
-24216387046086
744...

result:

ok 200000 lines

Test #9:

score: 0
Accepted
time: 43ms
memory: 165524kb

input:

10000
5 21
-17119694111919 -49543801764535 15340078463236 -13731655847398 -41385234314814
1 2
4 1
5 1
1 3
3 4 -183603675
1 1 6 750831651
2 4 2 -112044052
2 5 0 487266103
2 4 7 623494631
2 3 6 -758745863
2 5 3 524459610
3 4 819153725
2 4 0 955588629
3 5 -451248313
1 3 0 -251438755
1 4 0 -707155518
3 ...

output:

-13731839451073
GG
15339966419184
-41384859092763
15340589913815
15339831167952
15340355627562
-13730743133022
-13729787544393
-41384921132698
15340104188807
-13730494699911
-49544113109053
-13730763136607
15340065374700
-13730897538201
-17118548613921
15340115180511
GG
-41384542096059
1534095454059...

result:

ok 200000 lines

Test #10:

score: 0
Accepted
time: 58ms
memory: 165608kb

input:

10000
7 53
-49257878340663 65913602617244 -77586447275975 37912663831730 -29965751459870 -24028915786606 -20711244730875
6 5
6 7
3 6
5 4
5 2
1 7
1 2 1 -902483856
2 2 0 -166019888
1 2 6 773740058
1 7 4 332162805
3 4 483966804
2 1 8 -161176455
2 6 2 999609920
2 2 1 575504367
1 2 2 -125436309
1 7 6 -85...

output:

-29966653943726
65913436597356
GG
GG
37913147798534
65913275420901
65914275030821
65914850535188
37913860795690
GG
65915321019354
65915455681128
65915560380329
65915183127659
65914812218108
65915548812492
65916224155305
65915243014798
-20710396693949
GG
65915329685860
65915917517754
65915625807955
6...

result:

ok 200000 lines

Test #11:

score: 0
Accepted
time: 79ms
memory: 165520kb

input:

10000
10 4
71797802165245 -54234031880796 29183815458453 29504172959957 49372193603523 -16185389362615 39453295094243 663036651923 96744787191200 -50620611104201
3 4
3 8
5 10
8 1
6 2
7 6
10 3
8 9
5 7
3 10 272721546
2 10 4 618153907
3 8 763987349
1 9 7 870230974
10 8
-13468051963531 -33479821641433 9...

output:

49372466325069
96745405345107
96746169332456
-54231506787020
91247244061845
91246513437933
-33254303623674
-34062728633884
38205426400070
91082413811192
-13468602472782
GG
86995519872619
10278075155744
86995188030179
86995444966527
19338147521978
86995117144520
86994756220490
19337573163350
-9437093...

result:

ok 200000 lines

Test #12:

score: 0
Accepted
time: 789ms
memory: 214056kb

input:

5
100000 10278
-33062210930377 -27859969846302 -17580975150961 82421468622525 73124685670220 24605270582441 -85306160207816 -94488582195355 85451638721967 61110610044303 20119327748559 28059853591446 40777043818126 -26083158668773 -86932609818311 -80046664707280 36276301345898 72062141434820 -521113...

output:

99730096363045
-53142619895885
62633703474374
91065884890424
95913832039203
71963014593268
-73718672703414
88512243346245
95865153100847
20076236503631
-34284711719410
39055157031710
89757297384484
10950553757520
74269720205379
-9148723701106
-8854522652340
30148659190315
43163551215290
403669992467...

result:

ok 200000 lines

Test #13:

score: 0
Accepted
time: 936ms
memory: 243936kb

input:

2
200000 23147
-97882461219103 4406360045230 -36834806355299 -23973944052222 67113212265469 11669200972710 -6141709659817 -49560474741369 -18057145741204 -44040958119516 3611153759432 -22756796992893 65910580696453 -78071204736196 25214500077730 -40055869810099 52016133250624 24245766969509 -8573710...

output:

-84299253303082
91895293630648
98660521022574
99046915140773
96940400761168
-80640388829817
62170787931699
80755385476426
87313515284587
58038098598906
58552202132101
69717429372059
50840268036882
49052127297522
30321746138445
57233008189011
-26057525271228
98121546101640
88622027455733
621912032228...

result:

ok 200000 lines

Test #14:

score: 0
Accepted
time: 722ms
memory: 194712kb

input:

10
50000 1687
36077001037650 -28672159307004 -49567820178173 -66598809699217 51717647349268 40388708770673 -41615842513164 20640893046085 55244284371739 -12659258787859 -57804698295568 -1343921361566 -31490537070370 87398926700957 6369486949134 29314854271472 87863569527089 713709747605 -57348496935...

output:

99530565733478
52005604713243
95506513999163
99658832110191
99907096903163
97154724606255
81337070881934
58949958650580
99715077145772
85133043445758
74581069634085
50184582656147
69809426118622
70927902639147
-91729966293446
17060316600613
-10509867546560
-87583239449605
65152989953561
700189739274...

result:

ok 200000 lines

Test #15:

score: 0
Accepted
time: 334ms
memory: 165836kb

input:

500
1000 92
-34961255282319 -28048065121777 48403085782275 59825930674807 -81890804792913 -3718001248779 -16547933440271 86250915241917 86924443194023 -9735258000336 -91234968422024 -28592966984694 52777768205476 -93185139144600 5318140881411 -56116796281200 9179306895895 -22296214888774 -9108202485...

output:

4668320585308
88059957249898
71176226537037
93851532152750
-32706642031920
99121476057172
79602129082988
84325004453053
86250139584500
98672885845344
45802895326473
68661280872768
97371517369487
93616500614156
27589386746356
88059626048731
99121271376424
68093790136715
99361085683130
98488054170870
...

result:

ok 200000 lines

Test #16:

score: -100
Time Limit Exceeded

input:

5
100000 10278
-33062210930377 -27859969846302 -17580975150961 82421468622525 73124685670220 24605270582441 -85306160207816 -94488582195355 85451638721967 61110610044303 20119327748559 28059853591446 40777043818126 -26083158668773 -86932609818311 -80046664707280 36276301345898 72062141434820 -521113...

output:

-12749974258479
84017004006248
-89539813077621
-80338381552172
82312582262422
98103687339070
94560175951271
93134724507461
58620904163291
81867438963191
-400987364342
63575768373779
90005411398068
-98825155078969
67966851202993
98296098861174
-24807695936092
96949416015307
-34263626970319
8507072303...

result: