QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#647252#4941. Tree BeautyVermeilWA 507ms49164kbC++175.5kb2024-10-17 13:01:482024-10-17 13:01:50

Judging History

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

  • [2024-10-17 13:01:50]
  • 评测
  • 测评结果:WA
  • 用时:507ms
  • 内存:49164kb
  • [2024-10-17 13:01:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
using ll = long long;

struct SegTree{
    vector<ll> seg, lazy;
    int sz;
    SegTree(int n){
        sz = n;
        seg.resize(sz * 4, 0);
        lazy.resize(sz * 4, 0);
    }
    void prop(int x, int s, int e){
        if (!lazy[x]) return;
        seg[x] += lazy[x] * (e - s + 1);
        if (s ^ e){
            for (int i:{x*2,x*2+1}){
                lazy[i]+=lazy[x];
            }
        }
        lazy[x] = 0;
    }
    void upd(int x, int s, int e, int l, int r, ll v){
        if (e < l || r < s) return;
        prop(x, s, e);
        if (l <= s && e <= r){
            lazy[x] = v;
            prop(x, s, e);
            return;
        }
        int m = (s + e) / 2;
        upd(x * 2, s, m, l, r, v);
        upd(x * 2 + 1, m + 1, e, l, r, v);
        seg[x] = seg[x * 2] + seg[x * 2 + 1];
    }
    ll qry(int x, int s, int e, int l, int r){
        if (e < l || r < s) return 0;
        prop(x, s, e);
        if (l <= s && e <= r) return seg[x];
        int m = (s + e) / 2;
        return qry(x * 2, s, m, l, r) + qry(x * 2 + 1, m + 1, e, l, r);
    }

    void upd(int l, int r, ll v){
        upd(1, 1, sz, l, r, v);
    }
    ll qry(int l, int r){
        return qry(1, 1, sz, l, r);
    }
};


int n, q;
vector<int> g[101010];
int par[101010];
ll dp[101010][19];
ll updPar[101010][19];
ll P[101010];
int L[101010], R[101010];
int B[101010], revB[101010];
int idx = 0;
void dfs(int x){
    L[x] = ++idx;
    for (int i: g[x]){
        par[i] = x;
        dfs(i);
        for (int j=0;j<18;j++){
            dp[x][j + 1] += dp[i][j];
        }
    }
    dp[x][0] = 1;
    R[x] = idx;
}
void bfs(){
    queue<int> que;
    que.push(1);
    int bfn = 0;
    while(!que.empty()){
        int x = que.front();
        que.pop();
        B[x] = ++bfn;
        revB[bfn] = x;
        for (int i: g[x]){
            que.push(i);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>q;
    for (int i=2;i<=n;i++){
        int x;cin>>x;
        g[x].push_back(i);
    }
    dfs(1);
    bfs();
    SegTree s1(n), s2(n), s3(n);
    while (q--){
        ll op, y, k;
        int x;
        for (int i=1;i<=n;i++){

        }
        cin>>op;
        if (op==1){
            cin>>x>>y>>k;
            if (k > 1){
                ll div = 1;
                ll sum = 0;
                ll val = y;
                for (int i=0;i<19;i++){
                    if (!val) break;
                    updPar[x][i] += val;
                    sum += val * dp[x][i];
                    val /= k;
                    div *= k;
                }
                P[x] += y;
                s2.upd(L[x], L[x], sum);
                int l = B[x], r = B[x];
                ll ny = y;
                for (int i=1;i<=18;i++){
                    int nl = 0, nr = 0;
                    int lo, hi;
                    lo = 1, hi = n;
                    while (lo <= hi){
                        int mid = (lo + hi) / 2;
                        int ver = B[par[revB[mid]]];
                        if (ver < l) lo = mid + 1;
                        else hi = mid - 1;
                    }
                    nl = lo;
                    lo = 1, hi = n;
                    while (lo <= hi){
                        int mid = (lo + hi) / 2;
                        int ver = B[par[revB[mid]]];
                        if (ver <= r) lo = mid + 1;
                        else hi = mid - 1;
                    }
                    nr = hi;
                    if (nr < nl) break;
                    ny /= k;
//                    cout<<nl<<" "<<nr<<" "<<revB[nl]<<" "<<revB[nr]<<" "<<ny<<endl;
                    s3.upd(nl, nr, ny);
                    l = nl;
                    r = nr;
                }
            }
            else{
                s1.upd(L[x], R[x], y);
            }
        }
        else{
            cin>>x;
            ll ans = 0;
            ans += s1.qry(L[x], R[x]);
            ans += s2.qry(L[x], R[x]);
//            cout<<"s1+s2 : "<<ans<<endl;
            int cur = par[x];
            vector<ll> intervals = {1};
            int l = B[x], r = B[x];
            for (int i=1;i<19;i++){
                int nl = 0, nr = 0;
                int lo, hi;
                lo = 1, hi = n;
                while (lo <= hi){
                    int mid = (lo + hi) / 2;
                    int ver = B[par[revB[mid]]];
                    if (ver < l) lo = mid + 1;
                    else hi = mid - 1;
                }
                nl = lo;
                lo = 1, hi = n;
                while (lo <= hi){
                    int mid = (lo + hi) / 2;
                    int ver = B[par[revB[mid]]];
                    if (ver <= r) lo = mid + 1;
                    else hi = mid - 1;
                }
                nr = hi;
                if (nr < nl){
                    while (intervals.size() < 19){
                        intervals.push_back(0);
                    }
                    break;
                }
                intervals.push_back(nr - nl + 1);
                l = nl;
                r = nr;
            }
            for (int d=1;cur;d++,cur=par[cur]){
                for (int i=0;i+d<19;i++){
                    ans += updPar[cur][i + d] * intervals[i];
                }
            }
            cout<<ans<<'\n';
        }
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 13976kb

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: 0ms
memory: 8316kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 507ms
memory: 49164kb

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
2695839402
1987509504
2695839402
2707607620
2695839402
2695839402
6169484781
8462490815
6059721540
3956948412
16426173198
19999836240
12388618336
12596041336
11489785336
7327275384
10382901054
22395595829
20563218626
17544502851
21935873619
25432295194
7454...

result:

wrong answer 5th lines differ - expected: '2920352548', found: '2695839402'