# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1212261 | mmario99 | Digital Circuit (IOI22_circuit) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll MOD = 1000002022;
static int gN, gM;
static vector<int> parentArr;
static vector<vector<int>> children;
static vector<ll> Sval;
static vector<ll> Wval;
static vector<ll> upVal;
static vector<ll> coef;
static vector<int> leafState;
struct SegTree
{
int n;
struct Node
{
ll sum;
ll totCoef;
bool flip;
};
vector<Node> st;
SegTree(int _n=0) : n(_n)
{
if (n > 0) st.resize(4*n);
}
void build(int p, int l, int r)
{
if (l == r)
{
st[p].totCoef = coef[l] % MOD;
st[p].sum = (coef[l] * leafState[l]) % MOD;
st[p].flip = false;
return;
}
int m = (l + r) >> 1;
build(p<<1, l, m);
build(p<<1|1, m+1, r);
st[p].totCoef = (st[p<<1].totCoef + st[p<<1|1].totCoef) % MOD;
st[p].sum = (st[p<<1].sum + st[p<<1|1].sum) % MOD;
st[p].flip = false;
}
inline void applyFlip(int p)
{
st[p].sum = (st[p].totCoef - st[p].sum) % MOD;
if (st[p].sum < 0) st[p].sum += MOD;
st[p].flip = !st[p].flip;
}
inline void push(int p)
{
if (!st[p].flip) return;
applyFlip(p<<1);
applyFlip(p<<1|1);
st[p].flip = false;
}
void updateRange(int p, int l, int r, int i, int j)
{
if (j < l || i > r) return;
if (l >= i && r <= j)
{
applyFlip(p);
return;
}
push(p);
int m = (l + r) >> 1;
updateRange(p<<1, l, m, i, j);
updateRange(p<<1|1, m+1, r, i, j);
st[p].sum = (st[p<<1].sum + st[p<<1|1].sum) % MOD;
}
void init_build(int _n)
{
n = _n;
st.resize(4*n);
build(1, 0, n-1);
}
void invertInterval(int L, int R)
{
updateRange(1, 0, n-1, L, R);
}
ll queryAll() const
{
return st[1].sum;
}
};
static SegTree seg;
void init(int N, int M, int P[], int A[])
{
gN = N;
gM = M;
parentArr.resize(N+M);
for(int i = 0; i < N+M; i++)
{
parentArr[i] = P[i];
}
children.assign(N+M, {});
for(int i = 1; i < N+M; i++)
{
int p = parentArr[i];
children[p].push_back(i);
}
leafState.resize(M);
for(int i = 0; i < M; i++)
{
leafState[i] = A[i];
}
Sval.assign(N+M, 0LL);
for(int v = N+M-1; v >= 0; v--)
{
if (v >= N)
{
Sval[v] = 1;
}
else
{
ll prod = 1;
int d = (int)children[v].size();
for(int c : children[v])
{
prod = (prod * Sval[c]) % MOD;
}
prod = (prod * d) % MOD;
Sval[v] = prod;
}
}
Wval.assign(N+M, 1LL);
for(int v = 0; v < N; v++)
{
int d = (int)children[v].size();
if (d == 0) continue;
vector<ll> pref(d), suf(d);
for(int i = 0; i < d; i++)
{
pref[i] = Sval[ children[v][i] ];
suf[i] = pref[i];
}
for(int i = 1; i < d; i++)
{
pref[i] = (pref[i] * pref[i-1]) % MOD;
}
for(int i = d-2; i >= 0; i--)
{
suf[i] = (suf[i] * suf[i+1]) % MOD;
}
for(int i = 0; i < d; i++)
{
ll left = (i > 0 ? pref[i-1] : 1LL);
ll right = (i+1 < d ? suf[i+1] : 1LL);
ll w = (left * right) % MOD;
int c = children[v][i];
Wval[c] = w;
}
}
upVal.assign(N+M, 1LL);
vector<int> queue;
queue.reserve(N+M);
queue.push_back(0);
for(int idx = 0; idx < (int)queue.size(); idx++)
{
int v = queue[idx];
for(int c : children[v])
{
upVal[c] = (upVal[v] * Wval[c]) % MOD;
queue.push_back(c);
}
}
coef.assign(M, 0LL);
for(int i = 0; i < M; i++)
{
coef[i] = upVal[N + i];
}
seg = SegTree(M);
seg.init_build(M);
}
int count_ways(int L, int R)
{
int l = L - N;
int r = R - N;
seg.invertInterval(l, r);
ll ans = seg.queryAll() % MOD;
return (int)ans;
}