QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#133786#4941. Tree BeautyVengeful_SpiritTL 3ms28068kbC++204.0kb2023-08-02 14:00:482023-08-02 14:01:02

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 14:01:02]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:28068kb
  • [2023-08-02 14:00:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
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){
  sz[x]=1;
  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;
int dfnr[N];
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);
    }
  }
  dfnr[x]=indec;
}
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);
  }
}
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[bfn[x]],bfn[y]);
    sonr[bfn[x]]=max(sonr[bfn[x]],bfn[y]);
  }
}
void add(int l,int r,int num,int k){
  if(l<1||l>n||r<1||r>n) return ;
  for(int step=0;num;num/=k,++step){
    modify(step,1,1,n,l,r,num);
  }
}


// 2nd segtree
int t[N<<2],tg[N<<2];
void pushdown(int x){
  t[x<<1]+=tg[x];t[x<<1|1]+=tg[x];
  tg[x<<1]+=tg[x];tg[x<<1|1]+=tg[x];
  tg[x]=0;
}
void MODIFY(int x,int l,int r,int L,int R,int v){
  if(l==L&&r==R){
    t[x]+=v;
    tg[x]+=v;
    return;
  }
  else{
    pushdown(x);
    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 L, int R){
  if(l==r){return t[x];}
  else {
    pushdown(x);
    int mid=(l+r)/2;
    if(R<=mid) return QUERY(x<<1,l,mid,L,R);
    else if(L>mid) return QUERY(x<<1|1,mid+1,r,L,R);
    return QUERY(x<<1,l,mid,L,mid)+QUERY(x<<1|1,mid+1,r,mid+1,R);
  }
}
// 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]];
//   }
// }

signed 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;
      if(k==1) {
        MODIFY(1,1,n,dfn[x],dfnr[x],y);
      } else {
      int l = bfn[x], r = bfn[x];
      l = sonl[l];
      r = sonr[r];
      long long all=0;
      all=y;
      y/=k;
      while(y) {
        add(l,r,y,k);
        all+=(r-l+1)*1ll*y;
        y/=k;
        l=sonl[l];
        r=sonr[r];
        if(l>r)break;
      }
      if(x) MODIFY(1,1,n,dfn[x],dfn[x],all);
      }
    } else {
      int x;
      cin >> x;
      long long ans=QUERY(1,1,n,dfn[x],dfnr[x]);
      int l=bfn[x],r=bfn[x];
      for(int i=0;i<18;++i){
        ans+=query(i,1,1,n,bfn[x])*(r-l+1);
        l=sonl[l];
        r=sonr[r];
        if(l>r)break;
      }
      cout<<ans<<"\n";
    }
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 28068kb

input:

5 5
1 1 3 3
1 1 99 2
2 1
2 3
1 3 2 3
2 3

output:

245
97
99

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 13736kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Time Limit Exceeded

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1818724600
1818724600
1818724600
672469600
2920352548
1987509504
2920352548
2782801948
2920352548
2920352548
7518672977
11295020015
7543062544
4383229800
19258702398
22947288874
15221147536
15428570536
14322314536
9119623396
12969783379
26872020588
25039643385
22398749036
27923029652
31534374661
745...

result: