QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#134025#4941. Tree Beautywtn135687WA 94ms79364kbC++145.2kb2023-08-02 20:44:002023-08-02 20:44:03

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:44:03]
  • 评测
  • 测评结果:WA
  • 用时:94ms
  • 内存:79364kb
  • [2023-08-02 20:44:00]
  • 提交

answer

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

const int N = 1e6+10,mo = 1e18+7;
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;
}

int a[N];
int n,q;
vector<int>to[N];
int dfn[N],nfd[N],R[N];
// int L[N],R[N];//儿子编号始终
int dep[N];
int fa[N];
int add[21][N];//给下面每层深度的儿子的加
int num[21][N];//每层深度的儿子的数量

// void bfs(){
//     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;
//     }
// }


void dfs(int u,int fat){
    fa[u]=fat;
    static int cnt;
    dfn[u]=++cnt;
    for(int v:to[u]){
        dfs(v,u);
    }R[u]=cnt;
    num[0][u]=1;
    for(int i=1;i<=20;i++){
        for(int v:to[u])num[i][u]+=num[i-1][v];
    }
}


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";
        if(!(l<=ql&&qr<=r))return ;
        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;
    // }
    void modify(int x,int y,int k){
        if(k==1){modify(1,1,n,dfn[x],R[x],y);return ;}
        int sum=0;
        for(int i=0;i<=20;i++){
            if(y<q_pow(k,i))break;
            add[i][x]+=(y/q_pow(k,i));
            sum+=num[i][x]*(y/q_pow(k,i));
        }
        modify(1,1,n,dfn[x],dfn[x],sum);
    }
    ll query(int x){
        int res=query(1,1,n,dfn[x],dfn[x]);
        for(int i = 1, now = fa[x]; i <= 20 && now; i ++, now = fa[now]){
        for(int j = i; j <= 20 ; j ++){
            res += add[j][now] * num[j - i][x];
            // cerr << res << ' ' << f[now][j] << ' ' << num[x][j - 1] << '\n';
            }
        }
        // for(int i=1;i<=20;i++){
        //     x=fa[x];if(!x)break;
        //     res+=num[i][x]*add[i][x];
        // }
        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);}
    tree.build(1,1,n);
    // bfs();
    dfs(1,0);
    while(q--){
        int op;cin>>op;
        if(op==1){
            int x,y,k;cin>>x>>y>>k;
            tree.modify(x,y,k);
        }
        else {
            int x;cin>>x;
            cout<<tree.query(x)<<"\n";
        }
    }    

}


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




































詳細信息

Test #1:

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

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: 6ms
memory: 36240kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 94ms
memory: 79364kb

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:

0
0
0
76417
0
129963
0
76417
0
0
78607
78607
468817
453762
230471
144023
230470
230470
230470
22826477
11376799
0
144023
230470
5811920
78063
745421
305459
242814
474024
745421
13938831
833215
833215
1072013
476935
833215
493756
230507
7366190
393253
0
256058
750988
528845
393254
232881
1172104
2846...

result:

wrong answer 1st lines differ - expected: '1818724600', found: '0'