QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#762352 | #7767. 数据结构 | hxhhxh | 15 | 293ms | 175964kb | C++20 | 3.2kb | 2024-11-19 14:44:00 | 2024-11-19 14:44:01 |
Judging History
answer
#include<bits/stdc++.h>
#define ll unsigned long long
#define pii pair<int,int>
#define vpi vector<pii>
#define fi first
#define se second
using namespace std;
const int N=2e5+5;
struct BIT{
ll a[N],b[N];
void _add(int x,ll v){
for(ll c=x*v;x<N;x+=x&-x) a[x]+=v,b[x]+=c;
}
void add(int l,int r,ll v){
_add(l,v),_add(r+1,-v);
}
ll _que(int x){
ll v=0;
for(ll t=x+1;x;x-=x&-x) v+=a[x]*t-b[x];
return v;
}
ll que(int l,int r){
return _que(r)-_que(l-1);
}
}T;
int n,Q,K,fa[N],dfn[N],hs[N],siz[N],dcnt,dep[N],top[N];
vector<int>e[N],g[N];
vpi tk[N][4],lk[N][4],tr[N];
void dfs1(int x,int f){
siz[x]=1;
dep[x]=dep[f]+1;
fa[x]=f;
for(int i:e[x]){
if(i==f) continue;
dfs1(i,x);
siz[x]+=siz[i];
g[x].push_back(i);
}
for(int i:g[x]) if(siz[i]>siz[hs[x]]) hs[x]=i;
}
void lb(int x){
if(!dfn[x]) dfn[x]=++dcnt;
}
void dfs2(int x,int ff){
top[x]=ff;
if(ff==x){
vector<int>u;
for(int t=x;t;t=hs[t]) u.push_back(t),lb(t);
for(int i=1;i<=3;i++){
vector<int>v;
for(int j:u) for(int l:g[j]) if(top[j]!=x) v.push_back(l),lb(l);
u=v;
}
}
if(hs[x]) dfs2(hs[x],ff);
for(int i:g[x]) if(i!=hs[x]) dfs2(i,i);
}
void zp(vpi&x){
sort(x.begin(),x.end());
vpi y;
for(pii i:x){
if(y.empty()||i.fi>y.back().se+1) y.push_back(i);
else y.back().se=max(y.back().se,i.se);
}
x=y;
}
void add(vpi&x,const vpi&y){
if(y.empty()) return;
if(x.empty()) x=y;
else{
for(pii i:y) x.push_back(i);
zp(x);
}
}
void dfs3(int x){
tr[x]=tk[x][0]={{dfn[x],dfn[x]}};
for(int i:g[x]){
dfs3(i);
for(int j=0;j<K;j++) add(tk[x][j+1],tk[i][j]);
add(tr[x],tr[i]);
}
for(int i=0;i<K;i++) add(tk[x][i+1],tk[x][i]);
}
void dfs4(int x){
for(int i=0;i<=K;i++) lk[x][i]=tk[x][i];
if(x>1){
for(int i=0;i<K;i++) add(tk[x][i+1],tk[fa[x]][i]);
for(int i=0;i<=K;i++) add(lk[x][i],lk[fa[x]][i]);
}
for(int i:g[x]) dfs4(i);
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
vpi del(vpi a,vpi b){
vpi res;
int l=0,r=-1,m=b.size();
for(pii i:a){
while(l<m&&b[l].se<i.fi) l++;
while(r<m-1&&b[r+1].fi<=i.se) r++;
if(l>r){
res.push_back(i);
continue;
}
if(i.fi<b[l].fi) res.push_back({i.fi,b[l].fi-1});
for(int j=l+1;j<=r;j++) res.push_back({b[j-1].se+1,b[j].fi-1});
if(i.se>b[r].se) res.push_back({b[r].se+1,i.se});
}
zp(res);
return res;
}
vpi ql(int x,int y,int k){
int u=lca(x,y);
vpi res=tk[u][k];
add(res,del(lk[x][k],lk[u][k]));
add(res,del(lk[y][k],lk[u][k]));
return res;
}
int main(){
// freopen("T2/zyf8.in","r",stdin);
// freopen("T2/zyf8.out","w",stdout);
cin>>n>>Q;K=3;
for(int i=1,j,k;i<n;i++){
scanf("%d %d",&j,&k);
e[j].push_back(k);
e[k].push_back(j);
}
dfs1(1,0);
dfs2(1,1);
dfs3(1);
dfs4(1);
for(int op,x,y,k,u;Q--;){
vpi cw;
scanf("%d",&op);
if(op&1) scanf("%d %d %d",&x,&y,&k),cw=ql(x,y,k);
else scanf("%d",&x),cw=tr[x];
ll res=0;
if(op<3){
scanf("%d",&u);
for(pii i:cw) T.add(i.fi,i.se,u);
}
else for(pii i:cw) res+=T.que(i.fi,i.se);
if(op>2) printf("%lld\n",res);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 11ms
memory: 10556kb
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: 19ms
memory: 15632kb
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: 0
Memory Limit Exceeded
Test #3:
score: 0
Memory Limit Exceeded
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:
Subtask #3:
score: 5
Accepted
Test #5:
score: 5
Accepted
time: 293ms
memory: 175964kb
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: 291ms
memory: 175704kb
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: 0
Memory Limit Exceeded
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:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #2:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%