#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
const int MAX_N = 2e5 + 9;
const int MOD = 1e9 + 2022;
int mul(int a, int b) {
return 1LL * a * b % MOD;
}
vi adj[MAX_N];
int val[MAX_N], prod[MAX_N];
int n;
void dfs0(int u) {
if (u >= n) {
val[u] = 1;
return;
}
val[u] = sz(adj[u]);
for (int v : adj[u]) {
dfs0(v);
val[u] = mul(val[u], val[v]);
}
}
void dfs1(int u, int curr) {
prod[u] = curr;
const int m = sz(adj[u]);
vi pref(m + 1), suff(m + 1);
pref[0] = 1, suff[m] = 1;
forn(i, m) pref[i + 1] = mul(pref[i], val[adj[u][i]]);
dforn(i, m) suff[i] = mul(suff[i + 1], val[adj[u][i]]);
forn(i, m) dfs1(adj[u][i], mul(mul(curr, pref[i]), suff[i + 1]));
}
const int SZ = 1 << 18;
ii st[2 * SZ];
bool lazy[2 * SZ];
void pass(int u) {
if (u < SZ) {
lazy[2 * u] ^= lazy[u];
lazy[2 * u + 1] ^= lazy[u];
}
if (lazy[u]) swap(st[u].fst, st[u].snd);
lazy[u] = false;
}
void calc(int u) {
st[u].fst = st[2 * u].fst + st[2 * u + 1].fst;
if (st[u].fst >= MOD) st[u].fst -= MOD;
st[u].snd = st[2 * u].snd + st[2 * u + 1].snd;
if (st[u].snd >= MOD) st[u].snd -= MOD;
}
void update(int s, int e, int l = 0, int r = SZ, int u = 1) {
pass(u);
if (e <= l || r <= s) return;
if (s <= l && r <= e) {
lazy[u] = true;
return pass(u);
}
int m = (l + r) / 2;
update(s, e, l, m, 2 * u);
update(s, e, m, r, 2 * u + 1);
calc(u);
}
void init(int N, int M, vi P, vi A) {
n = N;
forsn(i, 1, N + M) adj[P[i]].pb(i);
dfs0(0);
dfs1(0, 1);
forn(i, M) {
st[i + SZ].fst = prod[i + N];
st[i + SZ].snd = 0;
if (!A[i]) swap(st[i + SZ].fst, st[i + SZ].snd);
}
dforsn(i, 1, SZ) calc(i);
}
int count_ways(int L, int R) {
update(L - n, R - n + 1);
return st[1].fst;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |