QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#768480 | #7767. 数据结构 | zhouhuanyi | 25 | 1584ms | 435032kb | C++14 | 6.8kb | 2024-11-21 11:11:24 | 2024-11-21 11:11:25 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cassert>
#define N 200000
using namespace std;
int read()
{
char c=0;
int sum=0,f=1;
while (c!='-'&&(c<'0'||c>'9')) c=getchar();
if (c=='-') c=getchar(),f=-1;
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum*f;
}
struct reads
{
int l,r;
};
reads operator + (reads a,reads b)
{
return (reads){min(a.l,b.l),max(a.r,b.r)};
}
struct lines
{
int x,y,data;
bool operator < (const lines &t)const
{
return data>t.data;
}
};
lines dque[N+1];
int n,m,tops,dfn[N+1],leng,depth[N+1],rev[N+1],rev2[N+1],sz[N+1],top[N+1],fa[N+1],hs[N+1],num[N+1],length;
__int128 ans;
bool used[N+1];
vector<int>E[N+1];
vector<int>ES[N+1];
vector<int>p[N+1][4];
vector<reads>dp[N+1][4];
vector<reads>DP[N+1][4];
vector<reads>DP2[N+1];
vector<reads>DWP[N+1];
bool cmp(int x,int y)
{
return num[x]<num[y];
}
vector<reads>operator + (vector<reads>a,vector<reads>b)
{
if (a.empty()) return b;
if (b.empty()) return a;
int ps=0,ps2=0;
reads d=(reads){0,-1};
vector<reads>sp;
while (ps<a.size()||ps2<b.size())
{
if (ps<a.size()&&(ps2==b.size()||a[ps].l<b[ps2].l))
{
if (d.r+1>=a[ps].l) d=d+a[ps];
else
{
if (d.l<=d.r) sp.push_back(d);
d=a[ps];
}
ps++;
}
else
{
if (d.r+1>=b[ps2].l) d=d+b[ps2];
else
{
if (d.l<=d.r) sp.push_back(d);
d=b[ps2];
}
ps2++;
}
}
sp.push_back(d);
return sp;
}
vector<reads>solve(int l,int r)
{
if (l==r) return DWP[l];
int mid=(l+r)>>1;
return solve(l,mid)+solve(mid+1,r);
}
void add(int x,int y)
{
E[x].push_back(y),E[y].push_back(x);
return;
}
void dfs(int x)
{
used[x]=sz[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i]])
{
fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,ES[x].push_back(E[x][i]),dfs(E[x][i]),sz[x]+=sz[E[x][i]];
if (sz[E[x][i]]>sz[hs[x]]) hs[x]=E[x][i];
}
return;
}
void dfs2(int x)
{
dfn[x]=++leng,rev[dfn[x]]=x;
if (ES[x].empty()) dque[++tops]=(lines){top[x],x,dfn[top[x]]};
if (hs[x]) top[hs[x]]=top[x],dfs2(hs[x]);
for (int i=0;i<ES[x].size();++i)
if (ES[x][i]!=hs[x])
top[ES[x][i]]=ES[x][i],dfs2(ES[x][i]);
return;
}
void dfs3(int x)
{
for (int i=0;i<ES[x].size();++i)
{
if (ES[x][i]==hs[x])
{
for (int j=0;j<=3;++j) DP[ES[x][i]][j]=DP[ES[x][i]][j]+DP[x][j];
}
dfs3(ES[x][i]);
}
if (!ES[x].empty())
{
for (int i=0;i<ES[x].size();++i) DWP[i+1]=DP2[ES[x][i]];
DP2[x]=DP2[x]+solve(1,ES[x].size());
}
return;
}
struct seg
{
struct node
{
int l,r;
vector<reads>data;
};
node tree[(N<<2)+1];
void push_up(int k)
{
tree[k].data=tree[k<<1].data+tree[k<<1|1].data;
return;
}
void build(int k,int l,int r,int d)
{
tree[k].l=l,tree[k].r=r;
if (l==r)
{
tree[k].data=dp[rev[l]][d];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid,d),build(k<<1|1,mid+1,r,d),push_up(k);
return;
}
vector<reads>query(int k,int l,int r)
{
if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) return query(k<<1,l,r);
else if (l>=mid+1) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}
};
seg T[4];
struct seg2
{
struct node
{
int l,r;
long long lazy;
__int128 data;
};
node tree[(N<<2)+1];
void push_up(int k)
{
tree[k].data=tree[k<<1].data+tree[k<<1|1].data;
return;
}
void push_tag(int k,long long d)
{
tree[k].lazy+=d,tree[k].data+=(__int128)(d)*(tree[k].r-tree[k].l+1);
return;
}
void spread(int k)
{
if (tree[k].lazy!=0) push_tag(k<<1,tree[k].lazy),push_tag(k<<1|1,tree[k].lazy),tree[k].lazy=0;
return;
}
void build(int k,int l,int r)
{
tree[k].l=l,tree[k].r=r;
if (l==r) return;
int mid=(l+r)>>1;
build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
return;
}
void add(int k,int l,int r,int d)
{
if (tree[k].l==l&&tree[k].r==r)
{
push_tag(k,d);
return;
}
spread(k);
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) add(k<<1,l,r,d);
else if (l>=mid+1) add(k<<1|1,l,r,d);
else add(k<<1,l,mid,d),add(k<<1|1,mid+1,r,d);
push_up(k);
return;
}
__int128 query(int k,int l,int r)
{
if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
spread(k);
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) return query(k<<1,l,r);
else if (l>=mid+1) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}
};
seg2 T2;
vector<reads>get_path(int x,int y,int k)
{
vector<reads>sp;
while (top[x]!=top[y])
{
if (depth[top[x]]<depth[top[y]]) swap(x,y);
sp=sp+DP[x][k],x=fa[top[x]];
}
if (depth[x]>depth[y]) swap(x,y);
sp=sp+T[k].query(1,dfn[x],dfn[y]);
return sp;
}
void write(__int128 d)
{
if (!d) return;
write(d/10),printf("%d",(int)(d%10));
return;
}
void output(__int128 d)
{
if (d>0) write(d),puts("");
else if (d==0) puts("0");
else printf("-"),write(-d),puts("");
return;
}
int main()
{
int opt,x,y,d,k;
vector<reads>sp;
n=read(),m=read();
for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
depth[1]=1,dfs(1);
for (int i=1;i<=n;++i)
{
x=i;
for (int j=0;j<=3;++j)
{
if (x) p[x][j].push_back(i);
x=fa[x];
}
}
top[1]=1,dfs2(1),sort(dque+1,dque+tops+1);
for (int i=1;i<=tops;++i)
{
x=dque[i].x;
while (x)
{
if (!num[x]) num[x]=++length;
x=hs[x];
}
for (int j=0;j<=2;++j)
{
x=dque[i].x;
while (x)
{
for (int k=0;k<ES[x].size();++k)
if (ES[x][k]!=hs[x])
{
for (int t=0;t<p[ES[x][k]][j].size();++t)
if (!num[p[ES[x][k]][j][t]])
num[p[ES[x][k]][j][t]]=++length;
}
x=hs[x];
}
}
}
for (int i=1;i<=n;++i) dp[i][0]={(reads){num[i],num[i]}},rev2[num[i]]=i;
for (int i=1;i<=3;++i)
for (int j=1;j<=n;++j)
{
for (int t=0;t<E[j].size();++t) DWP[t+1]=dp[E[j][t]][i-1];
if (E[j].empty()) dp[j][i]=dp[j][i-1];
else dp[j][i]=dp[j][i-1]+solve(1,E[j].size());
}
for (int i=1;i<=n;++i)
{
for (int j=0;j<=3;++j) DP[i][j]=dp[i][j];
DP2[i]=dp[i][0];
}
dfs3(1);
for (int i=0;i<=3;++i) T[i].build(1,1,n,i);
T2.build(1,1,n);
for (int qt=1;qt<=m;++qt)
{
opt=read();
if (opt==1)
{
x=read(),y=read(),k=read(),d=read(),sp=get_path(x,y,k);
for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
}
else if (opt==2)
{
x=read(),d=read(),sp=DP2[x];
for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
}
else if (opt==3)
{
x=read(),y=read(),k=read(),sp=get_path(x,y,k),ans=0;
for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
printf("%llu\n",(unsigned long long)(ans));
}
else
{
x=read(),sp=DP2[x],ans=0;
for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
printf("%llu\n",(unsigned long long)(ans));
}
}
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 76ms
memory: 208064kb
input:
5000 5000 1 2 2 3 3 4 4 5 5 6 5 7 6 8 7 9 9 10 8 11 11 12 12 13 12 14 14 15 15 16 16 17 16 18 18 19 18 20 20 21 20 22 22 23 23 24 23 25 23 26 26 27 27 28 28 29 27 30 30 31 29 32 32 33 33 34 32 35 35 36 36 37 35 38 36 39 38 40 38 41 41 42 42 43 43 44 42 45 44 46 45 47 47 48 48 49 48 50 49 51 51 52 52...
output:
37227703492 2136305359188 2794367845468 1309925069860 1698169768858 2678958746332 6690595071246 2087826052960 5786332239171 2186592622 4014965079076 1674542130 6524658548 7094033144666 10065416610040 11589693473717 492570862 3356228199498 2834694279 4198036633070 4395772262 4221137767 9630829210 992...
result:
ok 2559 numbers
Test #2:
score: 10
Accepted
time: 59ms
memory: 193752kb
input:
5000 5000 54 2 1945 3 4131 4 1207 5 3558 6 3582 7 1648 8 3498 9 1761 10 360 11 3617 12 4359 13 158 14 2314 15 529 16 4619 17 1070 18 1504 19 2675 20 2981 21 2142 22 1349 23 1640 24 1374 25 4059 26 2511 27 2708 28 2939 29 3017 30 3320 31 4602 32 4779 33 2697 34 3906 35 1121 36 197 37 1551 38 1119 39 ...
output:
0 198262395 0 0 1595057854 0 0 39277179818 13451201574 21469030838 0 0 23554220364 19140694248 212211615641 0 0 0 0 0 86500798 60136122614 47351162248 0 0 306346383502 230306838988 0 170207438 471673864986 387605196674 0 0 0 688392707 115968801311 199501119668 168720065378 634329317954 0 0 155717506...
result:
ok 2456 numbers
Subtask #2:
score: 10
Accepted
Test #3:
score: 10
Accepted
time: 1584ms
memory: 435032kb
input:
200000 200000 1 2 1 3 1 4 3 5 1 6 1 7 7 8 8 9 2 10 1 11 5 12 1 13 7 14 10 15 2 16 7 17 11 18 5 19 5 20 1 21 16 22 1 23 3 24 20 25 14 26 2 27 6 28 15 29 10 30 15 31 5 32 13 33 12 34 31 35 31 36 36 37 36 38 1 39 28 40 5 41 12 42 41 43 20 44 30 45 22 46 11 47 47 48 45 49 14 50 41 51 3 52 30 53 29 54 6 ...
output:
0 0 0 0 0 0 0 0 7615073807 4176911055 0 4745654848 6222845818 0 0 9739142819 0 1424960716 5224818790 9459319003 13717923473 8673060864 0 11610197664 0 0 9587792729 0 0 0 2747489046 12425650803 0 0 11191496476 0 37597503993 0 0 15164651949 14868775382 15559673116 0 16391028892 0 15726757336 0 2421390...
result:
ok 100169 numbers
Test #4:
score: 10
Accepted
time: 1534ms
memory: 411136kb
input:
200000 200000 121679 2 13340 3 45206 4 112138 5 47397 6 88216 7 173469 8 109861 9 58662 10 130056 11 61155 12 4313 13 196310 14 46189 15 32349 16 143798 17 103215 18 159921 19 27365 20 14332 21 49504 22 64451 23 106931 24 59878 25 177587 26 100555 27 86848 28 793 29 79845 30 150813 31 42854 32 11551...
output:
77900221111 0 0 476439705914 0 216029652830 0 0 631267909751 508097390689 0 29277716182 695169620128 0 809294022024 0 0 829507748883 260130797154 0 1005527232590 109198360548 821333235719 0 0 1265757368752 738460021055 296232170804 845184728833 0 434366813420 0 1922343637889 0 0 0 229703081048 0 441...
result:
ok 100073 numbers
Subtask #3:
score: 5
Accepted
Test #5:
score: 5
Accepted
time: 613ms
memory: 388944kb
input:
200000 200000 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 51 51 ...
output:
0 134315201201061 38210069287857 75889674481730 25202765567748 179527420359031 75824479907233 156951577189979 246509811214535 251383387317167 181645886595511 285463150681348 213797241401335 244909583142805 53376921005282 451665818220 379334117147250 720759810155057 768646965102274 224741692238593 18...
result:
ok 100065 numbers
Test #6:
score: 5
Accepted
time: 615ms
memory: 389712kb
input:
200000 200000 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 51 51 ...
output:
0 1950387013442 2906443199266 2144858813468 3137341049831 1081425884175 20924388962208 73530126133368 136609133052209 125022026678010 22502893517249 99022896674514 84010333777754 13909990392191 43442491331837 190816082733002 92810414504491 244006706308139 42843404030538 126151201042579 7249812065288...
result:
ok 99740 numbers
Subtask #4:
score: 0
Memory Limit Exceeded
Test #7:
score: 10
Accepted
time: 1262ms
memory: 434764kb
input:
200000 200000 1 2 2 3 3 4 1 5 3 6 5 7 5 8 7 9 2 10 7 11 11 12 10 13 6 14 3 15 14 16 4 17 11 18 3 19 14 20 4 21 4 22 12 23 18 24 5 25 5 26 14 27 13 28 24 29 11 30 26 31 29 32 28 33 31 34 23 35 33 36 6 37 11 38 22 39 13 40 35 41 37 42 21 43 12 44 4 45 16 46 12 47 21 48 1 49 26 50 45 51 41 52 46 53 7 5...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 99786 numbers
Test #8:
score: 0
Memory Limit Exceeded
input:
200000 200000 1 2 2 3 1 4 1 5 2 6 3 7 6 8 8 9 8 10 9 11 8 12 12 13 13 14 11 15 13 16 13 17 16 18 17 19 18 20 19 21 19 22 21 23 21 24 21 25 24 26 23 27 26 28 27 29 26 30 30 31 28 32 29 33 32 34 32 35 33 36 36 37 35 38 38 39 38 40 40 41 39 42 42 43 43 44 41 45 45 46 43 47 45 48 46 49 49 50 50 51 51 52...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #2:
100%
Accepted
Dependency #4:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
0%