QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133711#4935. Exchange BottleneckVengeful_Spirit#TL 0ms0kbC++203.6kb2023-08-02 13:15:432023-08-02 13:15:46

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 13:15:46]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-08-02 13:15:43]
  • 提交

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

output:


result: