Submission #1242308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242308		Bahamin	Sumtree (INOI20_sumtree)	C++20	30 / 100	182 ms	46348 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#pragma GCC target("sse4")
#pragma GCC optimize("07")
#pragma GCC optimize ("unroll-loops")

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
#define lid id << 1
#define rid id << 1 | 1
#define mid ((r + l) >> 1)
const int MAX_N = 3e5 + 1;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

const int h = MAX_N, w = MAX_N;
vector<ll> inv(h+w+1);
vector<ll> fact(h+w+1);
vector<ll> fact_inv(h+w+1);

inline int md(ll x) {x %= MOD; return x + (x < 0 ? MOD : 0);}
inline int ADD(ll a, ll b) { return md(a+b); }
inline int SUB(ll a, ll b) { return md(a-b); }
inline int MUL(ll a, ll b) { return md(1ll*a*b); }
inline int POW(ll a, ll b) { int res=1;while(b){if(b&1)res=MUL(res,a);a=MUL(a,a);b>>=1;}return res; }
inline int DIV(ll a, ll b) { return MUL(a, POW(b, MOD-2)); }

inline int comb(ll n, ll k){
    if (n<0 || k<0) return 0LL;
    if (n < k) return 0LL;
    return fact[n] * fact_inv[n - k] % MOD * fact_inv[k] % MOD;
};

void init()
{
    inv[1] = 1;
    for(int i=2; i<h+w+1; i++){
        inv[i] = MOD - (MOD/i) * inv[MOD%i] % MOD;
    }
    fact[0] = 1; 
    fact_inv[0] = 1; 
    for(int i=1; i<h+w+1; i++){
        fact[i] = fact[i-1] * i % MOD;
        fact_inv[i] = fact_inv[i-1] * inv[i] % MOD;
    }
}

int st[MAX_N];
int fi[MAX_N];
int rev[MAX_N];
int sz[MAX_N];
int timer = 0;
vector<int> adj[MAX_N];
int have[MAX_N];
int seg2[MAX_N];
int mul = 1;
int zero = 0;
int n, rr;

void dfs(int u, int p)
{
    st[u] = timer++;
    rev[st[u]] = u;
    sz[u] = 1;
    for (int v : adj[u]) if (v != p) dfs(v, u), sz[u] += sz[v];
    fi[u] = timer;
}

int seg1[MAX_N << 2];

void upd1(int x, bool y, int l, int r, int id)
{
    if (l == r - 1) 
    {
        if (y) seg1[id] = fi[rev[l]];
        else seg1[id] = 0;
        return;
    }
    if (x < mid) upd1(x, y, l, mid, lid);
    else upd1(x, y, mid, r, rid);
    seg1[id] = max(seg1[lid], seg1[rid]);
}

int get1(int s, int t, int x, int l, int r, int id)
{
    // cout << s << " " << t << " " << x << " " << l << " " << r << endl;
    if (seg1[id] <= x) return -INF;
    if (l == r - 1) return l;
    if (t < mid) return get1(s, t, x, l, mid, lid);
    else if (s >= mid) return get1(s, t, x, mid, r, rid);
    else if (t >= r)
    {
        if (seg1[rid] > x) return get1(s, t, x, mid, r, rid);
        else return get1(s, t, x, l, mid, lid);
    } else 
    {
        int ind = get1(s, t, x, mid, r, rid);
        if (ind < 0) return get1(s, t, x, l, mid, lid);
        else return ind;
    }
}

inline int getpar(int u)
{
    return rev[get1(0, st[u], st[u], 0, n, 1)];
}

inline void upd2(int x, int y, int l, int r, int id)
{
    if (seg2[x] == 0) zero--;
    if (y == 0) zero++;
    if (seg2[x]) mul = DIV(mul, seg2[x]);
    if (y) mul = MUL(mul, y); 
    seg2[x] = y;
}   

pair<ll, ll> fen[MAX_N];

inline void upd3(int x, ll y, ll z)
{
    x++;
    for (int i = x; i < MAX_N; i += i & (-i)) fen[i].first += y, fen[i].second += z;
}

inline pair<ll, ll> get3(int x)
{
    x++;
    pair<ll, ll> re;
    for (int i = x; i > 0; i -= i & (-i)) re.first += fen[i].first, re.second += fen[i].second;
    return re;
}

inline pair<ll, ll> get3(int l, int r)
{
    pair<ll, ll> x = get3(r - 1);
    pair<ll, ll> y = get3(l - 1);
    return make_pair(x.first - y.first, x.second - y.second);
}

inline void calc(int u)
{
    auto ge = get3(st[u] + 1, fi[u]);
    ll x = have[u] - ge.second;
    ll y = sz[u] - ge.first;
    upd2(st[u], comb(x + y - 1, y - 1), 0, n, 1);
}

inline void add(int u, int x)
{   
    have[u] = x;
    int p = getpar(u);
    auto xx = get3(st[u] + 1, fi[u]);
    upd3(st[u], sz[u] - xx.first, have[u] - xx.second);
    upd3(st[p], xx.first - sz[u], xx.second - have[u]);
    calc(u), 0;
    calc(p), 0;
    upd1(st[u], true, 0, n, 1);
}

inline void rem(int u)
{
    int p = getpar(u);
    auto xx = get3(st[u] + 1, fi[u]);
    upd3(st[u], xx.first - sz[u], xx.second - have[u]);
    upd3(st[p], -xx.first + sz[u], -xx.second + have[u]);
    have[u] = -1;
    upd2(st[u], 1, 0, n, 1);
    calc(p);
    upd1(st[u], false, 0, n, 1);
}

void solve() {
    init();
    cin >> n >> rr;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    fill(seg2, seg2 + n, 1);
    fill(have, have + n + 1, -1);
    dfs(1, 0);
    have[1] = rr;
    upd3(st[1], sz[1], rr);
    upd1(st[1], true, 0, n, 1);
    calc(1);
    cout << (zero ? 0 : mul) << "\n";
    int q;
    cin >> q;
    while (q--)
    {
        int c;
        cin >> c;
        if (c == 1)
        {
            int v, x;
            cin >> v >> x;
            add(v, x);
        } else 
        {
            int v;
            cin >> v;
            rem(v);
        }
        cout << (zero ? 0 : mul) << "\n";
    }
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30