QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133711 | #4935. Exchange Bottleneck | Vengeful_Spirit# | TL | 0ms | 0kb | C++20 | 3.6kb | 2023-08-02 13:15:43 | 2023-08-02 13:15:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int sz[N],dep[N],dfn[N],son[N],fa[N],top[N];
int n, a[N];
vector<int> e[N];
void dfs(int x,int f){
dep[x]=dep[f]+1;
for(auto v:e[x]){
dfs(v,x);
sz[x]+=sz[v];
if(sz[v]>sz[son[x]])son[x]=v;
}
}
int indec;
void dfs2(int x,int tp){
top[x]=tp;
dfn[x]=++indec;
if(son[x]){
dfs2(son[x],tp);
}
for(auto v:e[x]){
if(v!=son[x]){
dfs2(v,v);
}
}
}
long long tag[18][N<<2];
void modify(int step,int x,int l,int r,int L,int R,int v){
if(l==L&&r==R){
tag[step][x]+=v;
return;
}
else{
int mid=(l+r)/2;
if(R<=mid){
modify(step,x<<1,l,mid,L,R,v);
}
else if(L>mid){
modify(step,x<<1|1,mid+1,r,L,R,v);
} else {
modify(step,x<<1,l,mid,L,mid,v);
modify(step,x<<1|1,mid+1,r,mid+1,R,v);
}
}
}
long long query(int step,int x,int l,int r,int pos){
if(l==r){return tag[step][x];}
else {
int mid=(l+r)/2;
if(pos<=mid) return tag[step][x]+query(step,x<<1,l,mid,pos);
else return tag[step][x]+query(step,x<<1|1,mid+1,r,pos);
}
}
// void modify(int x,int v){
// while(x){
// modify(1,1,n,dfn[top[x]],dfn[x],v);
// x=fa[top[x]];
// }
// }
int bfn[N];
int sonl[N],sonr[N];
void bfs(){
deque<pair<int,int>>q;
q.push_back({1,1});
int inded=0;
while(!q.empty()){
auto [x,d]=q.front();
bfn[x]=++inded;
q.pop_front();
for(auto v:e[x]){
q.push_back({v,d+1});
}
}
}
void DFS(int x){
sonl[bfn[x]]=n+1;
sonr[bfn[x]]=-1;
for(auto y:e[x]){
DFS(y);
sonl[bfn[x]]=min(sonl[x],bfn[y]);
sonr[bfn[x]]=max(sonr[x],bfn[y]);
}
}
void add(int l,int r,int num,int k){
for(int step=0;num;num/=k){
modify(step,1,1,n,l,r,num);
}
}
// 2nd segtree
int t[N<<2];
void MODIFY(int x,int l,int r,int L,int R,int v){
if(l==L&&r==R){
t[x]+=v;
return;
}
else{
int mid=(l+r)/2;
if(R<=mid){
MODIFY(x<<1,l,mid,L,R,v);
}
else if(L>mid){
MODIFY(x<<1|1,mid+1,r,L,R,v);
} else {
MODIFY(x<<1,l,mid,L,mid,v);
MODIFY(x<<1|1,mid+1,r,mid+1,R,v);
}
}
}
long long QUERY(int x,int l,int r,int pos){
if(l==r){return t[x];}
else {
int mid=(l+r)/2;
if(pos<=mid) return t[x]+QUERY(x<<1,l,mid,pos);
else return t[x]+QUERY(x<<1|1,mid+1,r,pos);
}
}
void upd(int x,long long v){
while(x){
// cerr<<x<<" "<<top[x]<<endl;
MODIFY(1,1,n,dfn[top[x]],dfn[x],v);
x=fa[top[x]];
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
// 1 X Y K
// 2 X
cin >> n;
int q;
cin >> q;
for(int i = 2; i <= n; ++i) {
cin >> fa[i];
e[fa[i]].push_back(i);
}
dfs(1, 0);
dfs2(1, 1);
bfs();
DFS(1);
for(int i=2;i<=n;++i)sonr[i]=max(sonr[i],sonr[i-1]);
for(int i=n-1;i;--i)sonl[i]=min(sonl[i],sonl[i+1]);
// for(int i=1;i<=n;++i)cerr<<i<<" "<<bfn[i]<<" "<<sonl[i]<<" "<<sonr[i]<<endl;
for(int i = 1; i <= q; ++i) {
int opt;
cin >> opt;
if(opt == 1) {
int x, y, k;
cin >> x >> y >> k;
int l = bfn[x], r = bfn[x];
long long all=0;
// cerr<<"!!!"<<endl;
while(y) {
// cerr<<l<<" "<<r<<" "<<y<<" "<<k<<endl;
add(l,r,y,k);
all+=(r-l+1)*1ll*y;
y/=k;
l=sonl[l];
r=sonr[r];
if(l>r)break;
}
// cerr<<"!"<<endl;
upd(x,all);
} else {
int x;
cin >> x;
long long ans=QUERY(1,1,n,dfn[x]);
for(int i=0;i<18;++i){
ans+=query(i,1,1,n,bfn[x]);
}
cout<<ans<<"\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
5 1 0 1 0