QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#767736 | #7767. 数据结构 | zhouhuanyi | 0 | 0ms | 0kb | C++17 | 7.2kb | 2024-11-20 21:57:27 | 2024-11-20 21:57:32 |
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#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];
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>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);
if (sp.size()>=40) sp.clear(),sp.shrink_to_fit();
return sp;
}
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,depth[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]),DP2[x]=DP2[x]+DP2[ES[x][i]];
}
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<E[x].size();++k)
if (E[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<=n;++i) sort(E[i].begin(),E[i].end(),cmp);
for (int i=1;i<=3;++i)
for (int j=1;j<=n;++j)
{
dp[j][i]=dp[j][i-1];
for (int t=0;t<E[j].size();++t) dp[j][i]=dp[j][i]+dp[E[j][t]][i-1];
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
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:
result:
Subtask #2:
score: 0
Runtime Error
Test #3:
score: 0
Runtime Error
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:
result:
Subtask #3:
score: 0
Runtime Error
Test #5:
score: 0
Runtime Error
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:
result:
Subtask #4:
score: 0
Runtime Error
Test #7:
score: 0
Runtime Error
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:
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:
0%