oj.uz

답안 #635462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635462 2022-08-26T09:49:17 Z Mahdi Sumtree (INOI20_sumtree) C++17
10 / 100
 269 ms 46740 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5, NN=3e5+5, M=1e9+7;
int ans, q, n, r, st[N], fn[N], siz[N], num[N], ss[N];
int f[N+NN], rf[N+NN];
vector<int>g[N];

int tav(int a, int b){
    int res=1;
    while(b){
        if(b&1)
            res=1LL*res*a%M;
        a=1LL*a*a%M;
        b>>=1;
    }
    return res;
}

int C(int x, int y){
    //cout<<"fuck : "<<f[x]<<", "<<rf[y]<<", "<<rf[x-y]<<'\n';
    ll res=1LL*f[x]*rf[y]%M;
    res=res*rf[x-y]%M;
    return res;
}

void pre(){
    f[0]=1;
    for(int i=1;i<N+NN;++i)
        f[i]=1LL*f[i-1]*i%M;
    rf[N+NN-1]=tav(f[N+NN-1], M-2);
    for(int i=N+NN-2;i>=0;--i)
        rf[i]=1LL*(i+1)*rf[i+1]%M;
}

struct seg_tree{
    int sz, h[3*N], lz[3*N], a[3*N], b[3*N];
    vector<int>ve;
    vector<pii>ev;

    seg_tree(){
        sz=1;
        while(sz<n)
            sz<<=1;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(lz, 0, sizeof(lz));
        fill(h, h+2*sz, 1);
    }

    int suma(int x, int lx, int rx, int l, int r){
        //cout<<"\n"<<x<<", "<<a[x]<<", "<<lx<<", "<<rx<<", "<<l<<", "<<r;
        if(lx>=r || rx<=l)
            return 0;
        //cout<<"\nwtf : \n";
        if(lx>=l && rx<=r)
            return a[x];
        //cout<<"comon ";
        int m=(lx+rx)/2;
        return suma(2*x+1, lx, m, l, r)+suma(2*x+2, m, rx, l, r);
    }

    void adda(int x, int v){
        x=st[x];
        x+=sz-1;
        a[x]+=v;
        while(x){
            --x;
            x/=2;
            a[x]+=v;
        }
    }

    int sumb(int x, int lx, int rx, int l, int r){
        if(lx>=r || rx<=l)
            return 0;
        if(lx>=l && rx<=r)
            return b[x];
        int m=(lx+rx)/2;
        return sumb(2*x+1, lx, m, l, r)+sumb(2*x+2, m, rx, l, r);
    }

    void addb(int x, int v){
        x=st[x];
        x+=sz-1;
        b[x]+=v;
        while(x){
            --x;
            x/=2;
            b[x]+=v;
        }
    }

    void add(int x, int lx, int rx, int l, int r, int t){
        if(lx>=r || rx<=l)
            return;
        if(lx>=l && rx<=r){
            h[x]+=t;
            lz[x]+=t;
            return;
        }
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        add(2*x+1, lx, m, l, r, t);
        add(2*x+2, m, rx, l, r, t);
        h[x]=-max(-h[2*x+1], -h[2*x+2]);
    }

    void add(int l, int r, int t){
        add(0, 0, sz, l, r, t);
    }
    
    int min(int x, int lx, int rx, int i){
        if(lx==rx-1)
            return h[x];
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        if(i<m)
            return min(2*x+1, lx, m, i);
        return min(2*x+2, m, rx, i);    
    }

    void opr(int x, int lx, int rx, int r){
        if(lx>=r)
            return;
        if(rx<=r){
            ve.push_back(x);
            ev.push_back({lx, rx});
            return;
        }
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        opr(2*x+2, m, rx, r);
        opr(2*x+1, lx, m, r);
    }

    int fr(int x, int lx, int rx, int val){
        if(lx+1==rx){
            if(h[x]>=val)
                return lx;
            return rx;
        }
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        if(h[2*x+2]>=val)
            return fr(2*x+1, lx, m, val);
        return fr(2*x+2, m, rx, val);
    }

    int par(int u){
        u=st[u];
        opr(0, 0, sz, u+1);
        int hh=min(0, 0, sz, u);
        int res=0;
        for(int i=0;i<ve.size();++i){
            if(ve[i]<hh){
                res=fr(ve[i], ev[i].F, ev[i].S, hh);
                break;
            }
        }
        ve.clear();
        ev.clear();
        return res;
    }
};

void dfs(int &tm, const int &v, const int &p=-1){
    st[v]=tm++;
    ss[v]=1;
    for(int u: g[v]){
        if(u!=p){
            dfs(tm, u, v);
            ss[v]+=ss[u];
        }
    }
    fn[v]=tm;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    pre();
    cin>>n>>r;
    for(int i=0;i<n-1;++i){
        int u, v;
        cin>>u>>v;
        g[--u].push_back(--v);
    }
    int tm=0;
    dfs(tm, 0);
    seg_tree A;
    ans=C(r+n-1, n-1);
    cout<<ans<<'\n';
    siz[0]=n;
    num[0]=r;
    cin>>q;
    while(q--){
        int t, u;
        cin>>t>>u;
        --u;
        if(t==1){
            int v;
            cin>>v;
            int w=A.par(u);
            //cout<<w<<'\n';
            A.add(st[u], fn[u], 1);
            ans=1LL*ans*tav(C(num[w]+siz[w]-1, siz[w]-1), M-2)%M;
            //cout<<ans<<'\n';
            siz[u]=ss[u]-A.suma(0, 0, A.sz, st[u], fn[u]);
            //cout<<"  : "<<ss[u]<<' '<<", "<<st[u]<<", "<<fn[u]<<' '<<siz[u]<<'\n';
            A.adda(u, siz[u]);
            siz[w]-=siz[u];
            A.adda(w, -siz[u]);
            num[u]=v-A.sumb(0, 0, A.sz, st[u], fn[u]);
            A.addb(u, num[u]);
            num[w]-=num[u];
            A.addb(w, -num[u]);
            ans=1LL*ans*C(num[w]+siz[w]-1, siz[w]-1)%M;
            ans=1LL*ans*C(num[u]+siz[u]-1, siz[u]-1)%M;
        }
        else{
            A.add(st[u], fn[u], -1);
            int w=A.par(u);
            ans=1LL*ans*tav(C(num[w]+siz[w]-1, siz[w]-1), M-2)%M;
            ans=1LL*ans*tav(C(num[u]+siz[u]-1, siz[u]-1), M-2)%M;
            A.adda(u, -siz[u]);
            siz[w]+=siz[u];
            A.adda(w, siz[u]);
            A.addb(u, -num[u]);
            num[w]+=num[u];
            A.addb(w, num[u]);
            ans=1LL*ans*C(num[w]+siz[w]-1, siz[w]-1)%M;
        }
        cout<<ans<<'\n';
    }
}
/*
5 4
1 2
2 3
2 4
3 5
4  
1 3 3
1 5 2
2 3
1 2 5
*/

Compilation message

Main.cpp: In member function 'int seg_tree::par(int)':
Main.cpp:176:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         for(int i=0;i<ve.size();++i){
      |                     ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 23100 KB Output is correct
2 Correct 65 ms 23016 KB Output is correct
3 Correct 67 ms 23168 KB Output is correct
4 Correct 75 ms 23056 KB Output is correct
5 Correct 71 ms 23528 KB Output is correct
6 Correct 15 ms 18388 KB Output is correct
7 Correct 15 ms 18476 KB Output is correct
8 Correct 14 ms 18396 KB Output is correct
9 Correct 76 ms 23436 KB Output is correct
10 Correct 68 ms 23460 KB Output is correct
11 Correct 67 ms 23888 KB Output is correct
12 Correct 73 ms 24848 KB Output is correct
13 Correct 66 ms 22696 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 18260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 91 ms 46740 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 269 ms 25960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 23100 KB Output is correct
2 Correct 65 ms 23016 KB Output is correct
3 Correct 67 ms 23168 KB Output is correct
4 Correct 75 ms 23056 KB Output is correct
5 Correct 71 ms 23528 KB Output is correct
6 Correct 15 ms 18388 KB Output is correct
7 Correct 15 ms 18476 KB Output is correct
8 Correct 14 ms 18396 KB Output is correct
9 Correct 76 ms 23436 KB Output is correct
10 Correct 68 ms 23460 KB Output is correct
11 Correct 67 ms 23888 KB Output is correct
12 Correct 73 ms 24848 KB Output is correct
13 Correct 66 ms 22696 KB Output is correct
14 Incorrect 14 ms 18260 KB Output isn't correct
15 Halted 0 ms 0 KB -