QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133997#4941. Tree Beautywtn135687RE 3ms40376kbC++144.4kb2023-08-02 20:06:552023-08-02 20:06:59

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 20:06:59]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:40376kb
  • [2023-08-02 20:06:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

const int N = 1e6+10,mo = 1e18+7;

int a[N];
int n,q;
vector<int>to[N];
int dfn[N],nfd[N];
int L[N],R[N];//儿子编号始终
int dep[N];
int depidR[N];
// int sz[N];//最深儿子深度
// void dfs(int u,int fa){
//     sz[u]=1;
//     for(int v:to[u]){
//         dfs(v,u);
//         sz[u]=max(sz[u],sz[v]+1);
//     }
// }
void bfs(){
    // for(int i=1;i<=n;i++)sort(to[i].begin(),to[i].end(),[&](int x,int y){
    //     return sz[x]>sz[y];
    // });
    queue<int>q;int cnt=0;dfn[1]=++cnt;nfd[cnt]=1;
    q.push(1);dep[1]=1;depidR[1]=1;
    while(q.size()){
        int u=q.front();q.pop();
        // cerr<<"u="<<u<<"\n";
        L[u]=cnt+1;
        for(int v:to[u]){
            dep[v]=dep[u]+1;
            dfn[v]=++cnt;nfd[cnt]=v;
            depidR[dep[v]]=cnt;
            q.push(v);
        }
        R[u]=cnt;
    }
    // for(int i=1;i<=n;i++)cerr<<"i="<<i<<" dfn: "<<dfn[i]<<"  LR:"<<L[i]<<" "<<R[i]<<"\n";
}
inline ll q_pow(int a,int b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mo;
        a=a*a%mo;
        b>>=1;
    }
    return res;
}




struct XDS {
    struct Node{
        int sum;
        int t;
        int len;
    }seg[N<<2];
    void build(int id,int l,int r){
        if(l==r){seg[id].len=1;return ;}
        int mid=l+r>>1;
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
        seg[id].len=seg[id<<1].len+seg[id<<1|1].len;
    }
    void setTag(int id,int t){
        seg[id].sum+=seg[id].len*t;
        seg[id].t+=t;
        // cerr<<"setTag:  id="<<id<<" sum="<<seg[id].sum<<" t="<<t<<" len="<<seg[id].len<<"\n";
    }
    void pushDown(int id){
        int t=seg[id].t;
        seg[id<<1].sum+=seg[id<<1].len*t;seg[id<<1|1].sum+=seg[id<<1|1].len*t;
        seg[id<<1].t+=t;seg[id<<1|1].t+=t;
        seg[id].t=0;
    }
    void upDate(int id){
        seg[id].sum=seg[id<<1].sum+seg[id<<1|1].sum;
        // cerr<<"update id="<<id<<" sum="<<seg[id].sum<<"\n";
    }
    void modify(int id,int l,int r,int ql,int qr,int t){
        // cerr<<"add "<<id<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<t<<"\n";
        assert(l<=ql&&qr<=r);
        if(l==ql&&r==qr){
            setTag(id,t);return ;
        }
        pushDown(id);
        int mid=l+r>>1;
        if(qr<=mid)modify(id<<1,l,mid,ql,qr,t);
        else if(ql>mid)modify(id<<1|1,mid+1,r,ql,qr,t);
        else {
            modify(id<<1,l,mid,ql,mid,t);modify(id<<1|1,mid+1,qr,mid+1,r,t);
        }
        upDate(id);
    }
    ll query(int id,int l,int r,int ql,int qr){
        // cerr<<"query tree"<<ql<<" "<<qr<<"\n";
        // cerr<<seg[id].sum<<"!\n";
        if(l==qr&&r==qr)return seg[id].sum;
        pushDown(id);
        int mid=l+r>>1;
        if(qr<=mid)return query(id<<1,l,mid,ql,qr);
        else if(ql>mid)return query(id<<1|1,mid+1,r,ql,qr);
        else return query(id<<1,l,mid,ql,mid)+query(id<<1|1,mid+1,r,mid+1,qr);
    }
    void modify(int l,int r,int y,int k,int d){//该级别的两个端点
        
        if(l>r)return ;
        if(y<q_pow(k,d))return ;
        // cerr<<"modify1   l,r,y,k,d:"<<l<<" "<<r<<" "<<y<<" "<<k<<" "<<d<<"\n";
        
        modify(1,1,n,l,r,y/(q_pow(k,d)));
        


        // cerr<<"lr:"<<l<<" "<<r<<"\n";
        // cerr<<"nfdlr = "<<nfd[l]<<" "<<nfd[r]<<"\n";
        modify(L[nfd[l]],R[nfd[r]],y,k,d+1); 
        
    }
    ll query(int l,int r){
        if(l>r)return 0;
        ll res=query(1,1,n,l,r);
        // cerr<<"query res   "<<l<<" "<<r<<" res= "<<res<<"\n";
        res+=query(L[nfd[l]],R[nfd[r]]);
        // cerr<<"query "<<l<<" "<<r<<" res= "<<res<<"\n";
        return res;
    }

}tree;

inline void solve(){
    cin>>n>>q;
    for(int i=2;i<=n;i++){int fa;cin>>fa;to[fa].push_back(i);}
    // dfs(1,0);
    tree.build(1,1,n);
    bfs();
    
    while(q--){
        int op;cin>>op;
        if(op==1){
            int x,y,k;cin>>x>>y>>k;
            tree.modify(dfn[x],dfn[x],y,k,0);
        }
        else {
            int x;cin>>x;
            cout<<tree.query(dfn[x],dfn[x])<<"\n";
        }
    }    

}



signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int WTN666=1;//cin>>WTN666;
    while(WTN666--){
        solve();
    }
}




































Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 40336kb

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: 3ms
memory: 40376kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Dangerous Syscalls

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:


result: