QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#742796 | #7767. 数据结构 | Larunatrecy | 0 | 613ms | 154644kb | C++14 | 6.0kb | 2024-11-13 17:20:11 | 2024-11-13 17:20:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
x=(f?-x:x);
}
typedef unsigned long long ull;
const int N = 2e5+7;
typedef long long LL;
int n;
vector<int> G[N],T[N];
int fa[N],siz[N],son[N],dfn[N],dep[N],top[N],seq[N],tot=0;
void dfs(int x,int pre)
{
fa[x]=pre;siz[x]=1;dep[x]=dep[pre]+1;
for(int y:T[x])if(y!=pre)
{
dfs(y,x);
siz[x]+=siz[y];
G[x].push_back(y);
if(siz[y]>siz[son[x]])son[x]=y;
}
}
struct BIT
{
ull d[N],c[N];
void add1(int x,ull v){for(int i=x;i<=n+1;i+=i&-i)d[i]+=v;}
void add2(int x,ull v){for(int i=x;i<=n+1;i+=i&-i)c[i]+=v;}
ull ask1(int x){ull res=0;for(int i=x;i;i-=i&-i)res+=d[i];return res;}
ull ask2(int x){ull res=0;for(int i=x;i;i-=i&-i)res+=c[i];return res;}
inline ull sum(int x){return ask1(x)*(x+1)-ask2(x);}
inline void add(int l,int r,ull v){if(l>r)return;add1(l,v);add1(r+1,-v);add2(l,v*l);add2(r+1,-v*(r+1));}
inline ull ask(int l,int r){if(l>r)return 0;return sum(r)-sum(l-1);}
}DS;
void extend(int x,int t)
{
if(!dfn[x])seq[dfn[x]=++tot]=x;
if(!t)return;
for(int y:G[x])extend(y,t-1);
}
void dfs2(int x,int topth)
{
top[x]=topth;
if(x==topth)
{
for(int i=0;i<=3;i++)
for(int u=x;u;u=son[u])extend(u,i);
}
if(!son[x])return;
dfs2(son[x],topth);
for(int y:G[x])if(y!=fa[x]&&y!=son[x])dfs2(y,y);
}
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define l(x) x.first
#define r(x) x.second
#define segment vector<pii>
segment operator +(segment A,segment B)
{
if(A.empty())return B;
if(B.empty())return A;
segment C;
int i=0,j=0,l=-1;
while(i<(int)A.size()||j<(int)B.size())
{
pii cur;
if(j>=(int)B.size()||(i<(int)A.size()&&A[i].first<B[j].first))
cur=A[i++];
else cur=B[j++];
if(l(cur)==l+1)C.back().second=cur.second;
else C.push_back(cur);
l=cur.second;
}
return C;
}
segment tree[N];
void dfs3(int x,int pre)
{
tree[x].push_back(mk(dfn[x],dfn[x]));
for(int y:G[x])
{
dfs3(y,x);
tree[x]=tree[x]+tree[y];
}
}
segment A[N][4],W[N][4];
bool vis[N];
segment S;
void get(int x,int d)
{
segment cur;cur.push_back({dfn[x],dfn[x]});
if(!d){S=S+cur;return;}
for(int y:G[x])if(!vis[y])get(y,d-1);
}
void dfs4(int x)
{
for(int d=0;d<=3;d++)
{
S.clear();
get(x,d);
W[x][d]=S;
}
if(x==top[x])
{
for(int u=x;u;u=son[u])vis[u]=1;
for(int d=0;d<=3;d++)
{
S.clear();
for(int u=x;u;u=son[u])
{
get(u,d);
if(d)A[u][d]=A[u][d-1];
A[u][d]=A[u][d]+S;
}
}
for(int u=x;u;u=son[u])vis[u]=1;
}
if(!son[x])return;
dfs4(son[x]);
for(int y:G[x])if(y!=son[x])
dfs4(y);
}
void apply(int x,int k,ull v)
{
int lst=x;
for(int i=1;i<=k;i++)
{
lst=x;
x=fa[x];
if(!x)return;
for(auto u:W[x][k-i])DS.add(l(u),r(u),v);
if(i<k)for(auto u:W[lst][k-i-1])DS.add(l(u),r(u),-v);
}
}
void modify(int x,int y,int k,int v)
{
int lstx=0,lsty=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y),swap(lstx,lsty);
for(auto u:A[x][k])DS.add(l(u),r(u),v);
if(lstx&&k)for(auto u:W[lstx][k-1])DS.add(l(u),r(u),-v);
if(son[x]&&k)for(auto u:W[son[x]][k-1])DS.add(l(u),r(u),v);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y),swap(lstx,lsty);
for(auto u:A[y][k])DS.add(l(u),r(u),v);
if(x!=top[x])
for(auto u:A[fa[x]][k])DS.add(l(u),r(u),-v);
if(lstx&&k)for(auto u:W[lstx][k-1])DS.add(l(u),r(u),-v);
if(lsty&&k)for(auto u:W[lsty][k-1])DS.add(l(u),r(u),-v);
if(son[y]&&k)for(auto u:W[son[y]][k-1])DS.add(l(u),r(u),v);
if(k)apply(x,k,v);
}
ull getans(int x,int k)
{
ull res=0;
int lst=x;
for(int i=1;i<=k;i++)
{
lst=x;
x=fa[x];
if(!x)break;
for(auto u:W[x][k-i])res+=DS.ask(l(u),r(u));
if(i<k)for(auto u:W[lst][k-i-1])res+=DS.ask(l(u),r(u));
}
return res;
}
ull query(int x,int y,int k)
{
ull res=0;
int lstx=0,lsty=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y),swap(lstx,lsty);
for(auto u:A[x][k])res+=DS.ask(l(u),r(u));
if(lstx&&k)for(auto u:W[lstx][k-1])res+=DS.ask(l(u),r(u));
if(son[x]&&k)for(auto u:W[son[x]][k-1])res+=DS.ask(l(u),r(u));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y),swap(lstx,lsty);
for(auto u:A[y][k])res+=DS.ask(l(u),r(u));
if(x!=top[x])
for(auto u:A[fa[x]][k])res+=DS.ask(l(u),r(u));
if(lstx&&k)for(auto u:W[lstx][k-1])res+=DS.ask(l(u),r(u));
if(lsty&&k)for(auto u:W[lsty][k-1])res+=DS.ask(l(u),r(u));
if(son[y]&&k)for(auto u:W[son[y]][k-1])res+=DS.ask(l(u),r(u));
if(k)res+=getans(x,k);
return res;
}
int main()
{
int m;
read(n);read(m);
for(int i=1;i<n;i++)
{
int u,v;
read(u);read(v);
T[u].push_back(v);
T[v].push_back(u);
}
dfs(1,0);dfs2(1,1);
dfs3(1,0);dfs4(1);
while(m--)
{
int op,x,y,k,v;
read(op);
if(op==1)
{
read(x);read(y);read(k);read(v);
modify(x,y,k,v);
}
else if(op==2)
{
read(x);read(v);
for(auto u:tree[x])DS.add(l(u),r(u),v);
}
else if(op==3)
{
read(x);read(y);read(k);
printf("%lld\n",query(x,y,k));
}
else if(op==4)
{
read(x);
ull res=0;
for(auto u:tree[x])res+=DS.ask(l(u),r(u));
printf("%lld\n",res);
}
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 13ms
memory: 62120kb
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:
4657223527540 3525260662034 2793343744484 1470432607898 3033666321694 2677934645348 6683382085629 10253617780362 5784732544789 2186592622 4013940978092 1674542130 6524658548 7090115254775 10065755562036 11578510707076 492570862 6857297323516 2834694279 9178745909016 4395772262 4221137767 9630829210 ...
result:
wrong answer 1st numbers differ - expected: '37227703492', found: '4657223527540'
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 613ms
memory: 121892kb
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 2964794112 5224818790 9459319003 13717923473 8673060864 0 11610197664 0 0 9587792729 0 0 0 6539544474 12425650803 0 0 11191496476 0 37597503993 0 0 15164651949 14868775382 34958369318 0 16391028892 0 15726757336 0 2421390...
result:
wrong answer 18th numbers differ - expected: '1424960716', found: '2964794112'
Subtask #3:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 271ms
memory: 154644kb
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 134314511981213 38210069287857 279645312549370 48205939924874 179526731139183 75824457254155 156951554536901 246509099341609 251382675444241 181645863942433 285463128028270 213786734389331 257640861525693 67958670336098 12702704525748 966928739123061 720756746262595 768643901209812 224740493575747...
result:
wrong answer 2nd numbers differ - expected: '134315201201061', found: '134314511981213'
Subtask #4:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 578ms
memory: 121656kb
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 162nd numbers differ - expected: '0', found: '549330330'
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%