QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#762060 | #7767. 数据结构 | Nesraychan | 0 | 1837ms | 315848kb | C++14 | 5.8kb | 2024-11-19 13:11:11 | 2024-11-19 13:11:11 |
Judging History
answer
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 200200
#define u64 unsigned long long
#define oo (1ll<<60)
IL int read()
{
reg int x=0,f=0; reg char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
const int B=3;
int n,q;
std::vector<int>G[N];
IL void add(reg int u,reg int v){G[u].push_back(v),G[v].push_back(u);}
namespace Segment
{
#define ls (o<<1)
#define rs (o<<1|1)
#define mid (l[o]+r[o]>>1)
int l[N<<2],r[N<<2];
u64 sum[N<<2],tag[N<<2];
IL void pushup(reg int o){sum[o]=sum[ls]+sum[rs];}
IL void apply(reg int o,reg int k){sum[o]+=1ull*k*(r[o]-l[o]+1),tag[o]+=k;}
IL void pushdown(reg int o){if(tag[o])apply(ls,tag[o]),apply(rs,tag[o]),tag[o]=0;}
void build(reg int o,reg int L,reg int R)
{
l[o]=L,r[o]=R;
if(L<R)build(ls,L,mid),build(rs,mid+1,R);
}
void modify(reg int o,reg int L,reg int R,reg int k)
{
if(L<=l[o]&&r[o]<=R)return apply(o,k);
if(L>r[o]||l[o]>R)return;
pushdown(o),modify(ls,L,R,k),modify(rs,L,R,k),pushup(o);
}
u64 query_sum(reg int o,reg int L,reg int R)
{
if(L<=l[o]&&r[o]<=R)return sum[o]; if(L>r[o]||l[o]>R)return 0;
return pushdown(o),query_sum(ls,L,R)+query_sum(rs,L,R);
}
#undef ls
#undef rs
#undef mid
}
int sz[N],dep[N],fa[N],son[N],anc[N];
void dfs1(reg int u)
{
dep[u]=dep[fa[u]]+(sz[u]=1);
for(auto v:G[u])if(!sz[v])
{
fa[v]=u,dfs1(v),sz[u]+=sz[v];
if(sz[son[u]]<sz[v])son[u]=v;
}
}
void dfs2(reg int u,reg int top)
{
anc[u]=top; if(son[u])dfs2(son[u],top);
for(auto v:G[u])if(!anc[v])dfs2(v,v);
}
IL int lca(reg int x,reg int y)
{
for(;anc[x]!=anc[y];x=fa[anc[x]])
if(dep[anc[x]]<dep[anc[y]])std::swap(x,y);
return dep[x]<dep[y]?x:y;
}
template<class T>IL void clear(reg T &a){T b; std::swap(a,b);}
int dfn[N],ed[N],dfc;
void dfs3(reg int u)
{
std::vector<int>P,Q;
for(reg int x=u;x;x=son[x])
{
P.push_back(x);
if(!dfn[x])dfn[x]=++dfc;
}
for(reg int o=1;o<=B;++o)
{
clear(Q);
for(auto u:P)for(auto v:G[u])if(v!=fa[u])
{
if(!dfn[v])dfn[v]=++dfc;
Q.push_back(v);
}
std::swap(P,Q);
}
for(reg int v=u;v;v=son[v])for(auto w:G[v])
if(w!=fa[v]&&w!=son[v])dfs3(w);
}
struct Range{int l,r;};
#define Sets std::vector<Range>
Sets work(reg Sets a)
{
Sets b;
std::sort(a.begin(),a.end(),[&](const Range &x,const Range &y){return x.l<y.l;});
reg int L=0,R=-1;
for(auto &[l,r]:a)
if(l==R+1)R=r;
else ~R?b.push_back({L,R}),0:0,L=l,R=r;
if(~R)b.push_back({L,R});
return b;
}
Sets merge(const Sets &a,const Sets &b)
{
Sets c;
for(auto p:a)c.push_back(p);
for(auto p:b)c.push_back(p);
return c;
}
IL void ins(reg Sets &a,const Sets &b)
{
a=work(merge(a,b));
}
Sets del(const Sets &a,const Sets &b)
{
Sets c;
reg int l=0,r=-1,n=b.size();
for(auto &[al,ar]:a)
{
while(r<n-1&&b[r+1].r<=ar)++r;
reg int p=al,i;
for(i=l;i<=r;++i)
{
if(p<b[i].l)c.push_back({p,b[i].l-1});
p=b[i].r+1;
}
if(p<=ar)c.push_back({p,ar});
l=r+1;
}
return work(c);
}
Sets sub[N],subk[N][4],upk[N][4],linek[N][4],pointk[N][4];
void dfs4(reg int u)
{
sub[u].push_back({dfn[u],dfn[u]});
subk[u][0]=sub[u];
for(auto v:G[u])if(v!=fa[u])
{
dfs4(v),ins(sub[u],sub[v]),upk[v][0].push_back({dfn[u],dfn[u]});
for(reg int i=1;i<=B;++i)ins(subk[u][i],subk[v][i-1]);
}
Sets tmp[4];
std::vector<int>P;
for(auto v:G[u])if(v!=fa[u])P.push_back(v);
for(reg int i=0;i<=B;++i)tmp[i].clear();
for(auto v:P)for(reg int i=1;i<=B;++i)
ins(upk[v][i],tmp[i]),ins(tmp[i],subk[v][i-1]);
std::reverse(P.begin(),P.end());
for(reg int i=0;i<=B;++i)tmp[i].clear();
for(auto v:P)for(reg int i=1;i<=B;++i)
ins(upk[v][i],tmp[i]),ins(tmp[i],subk[v][i-1]);
}
void dfs5(reg int u)
{
for(reg int i=0;i<=B;++i)linek[u][i]=subk[u][i];
for(reg int i=0;i<=B;++i)ins(linek[u][i],linek[fa[u]][i]);
for(reg int i=0,j,v;i<=B;++i)
{
pointk[u][i]=subk[u][i];
for(j=1,v=u;j<=i&&v;++j,v=fa[v])
ins(pointk[u][i],upk[v][i-j]);
}
for(reg int i=1;i<=B;++i)ins(pointk[u][i],pointk[u][i-1]);
for(auto v:G[u])if(v!=fa[u])dfs5(v);
}
Sets split(reg int x,reg int y,reg int k)
{
reg int z=lca(x,y);
return work(merge(pointk[z][k],merge(del(linek[x][k],linek[z][k]),del(linek[y][k],linek[z][k]))));
}
IL void cmax(reg int &x,reg int y){x<y?x=y:0;}
main()
{
n=read(),q=read();
for(reg int i=1;i<n;++i)add(read(),read());
Segment::build(1,1,n);
dfs1(1),dfs2(1,1),dfs3(1),dfs4(1),dfs5(1);
for(reg int op,x,y,k,w;q--;)
{
op=read(),x=read();
if(op==1)
{
y=read(),k=read(),w=read();
auto P=split(x,y,k);
for(auto &[l,r]:P)
Segment::modify(1,l,r,w);
}else if(op==2)
{
w=read();
auto P=sub[x];
for(auto &[l,r]:sub[x])
Segment::modify(1,l,r,w);
}else if(op==3)
{
y=read(),k=read();
auto P=split(x,y,k);
reg u64 res=0;
for(auto &[l,r]:P)
res+=Segment::query_sum(1,l,r);
printf("%llu\n",res);
}else
{
auto P=sub[x];
reg u64 res=0;
for(auto &[l,r]:P)
res+=Segment::query_sum(1,l,r);
printf("%llu\n",res);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 47ms
memory: 99968kb
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 4609511200067 18446744071601176942 3070072273956 1674542130 18446744071644275572 3104008526682 6341679964408 6006235988917 492570862 1127140172874 18446744072249278599 1844394554862 10080496...
result:
wrong answer 9th numbers differ - expected: '5786332239171', found: '4609511200067'
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 1837ms
memory: 310952kb
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 18446744072734690831 18446744073591495375 0 450687552 1927878522 0 0 1149208227 0 1424960716 929851494 5164351707 5127988881 4378093568 0 7315230368 0 0 9587792729 0 0 0 2747489046 8130683507 0 0 6896529180 0 29007569401 0 0 10869684653 10573808086 11264705820 0 12096061596 0 1143179...
result:
wrong output format Expected int64, but "18446744072734690831" found
Subtask #3:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 616ms
memory: 274744kb
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 153597207731803 236446702840007 241320278942639 129801336365495 234078161952004 203137132572663 166436235677589 53329676365026 451665818220 251649034404466 352771307201073 398863165818562 115602278279937 13...
result:
wrong answer 8th numbers differ - expected: '156951577189979', found: '153597207731803'
Subtask #4:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 1355ms
memory: 315848kb
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:
wrong answer 35677th numbers differ - expected: '4874907829', found: '579940533'
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:
0%