QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#585076 | #9373. Query on Tree | ucup-team3586# | TL | 936ms | 243936kb | C++23 | 6.3kb | 2024-09-23 18:47:09 | 2024-09-23 18:47:10 |
Judging History
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...