#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
const int mod = 1000002022;
void add(int &a, int b){
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
vector <int> adj[N], pre[N], suf[N];
int sz[N], val[N];
void dfs(int u){
sz[u] = 1;
for (int i = 0; i < adj[u].size(); ++ i){
int v = adj[u][i];
dfs(v);
if (!i) pre[u].pb(sz[v]);
else pre[u].pb(1ll * pre[u].back() * sz[v] % mod);
suf[u].pb(0);
sz[u] += sz[v];
}
for (int i = adj[u].size() - 1; i >= 0; -- i){
int v = adj[u][i];
if (i == int(adj[u].size() - 1)) suf[u][i] = sz[v];
else suf[u][i] = 1ll * suf[u][i + 1] * sz[v] % mod;
}
}
void get(int u){
for (int i = 0; i < adj[u].size(); ++ i){
int v = adj[u][i];
val[v] = val[u];
if (i > 0) val[v] = 1ll * val[v] * pre[u][i - 1] % mod;
if (i < adj[u].size() - 1) val[v] = 1ll * val[v] * suf[u][i + 1] % mod;
}
}
int sum[2][4 * N];
bool used[N], rev[N];
void mer(int s){
sum[0][s] = 0;
sum[1][s] = 0;
for (int i = 0; i <= 1; ++ i){
for (int j = 2 * s; j <= 2 * s + 1; ++ j) add(sum[i][s], sum[i][j]);
}
}
void build(int s, int l, int r, int n){
rev[s] = 0;
if (l == r){
sum[0][s] = used[l] * val[l + n];
sum[1][s] = (1 ^ used[l]) * val[l + n];
return;
}
int mid = l + r >> 1;
build(2 * s, l, mid, n);
build(2 * s + 1, mid + 1, r, n);
mer(s);
}
int kk, gg;
void init(int n, int m, int p[], int a[]){
kk = n;
gg = m;
for (int i = 1; i < n + m; ++ i) adj[p[i]].pb(i);
dfs(0);
val[0] = 1;
get(0);
for (int i = 0; i < m; ++ i) used[i] = a[i];
build(1, 0, m - 1, n);
}
void down(int s){
if (!rev[s]) return;
for (int i = 2 * s; i <= 2 * s + 1; ++ i) {
rev[i] ^= 1;
swap(sum[0][i], sum[1][i]);
}
rev[s] = 0;
}
void upd(int s, int l, int r, int u, int v){
if (u <= l && r <= v){
rev[s] ^= 1;
swap(sum[0][s], sum[1][s]);
return;
}
int mid = l + r >> 1;
down(s);
if (mid >= u) upd(2 * s, l, mid, u, v);
if (mid + 1 <= v) upd(2 * s + 1, mid + 1, r, u, v);
mer(s);
}
int count_ways(int l, int r){
upd(1, 0, gg - 1, l - kk, r - kk);
return sum[0][1];
}
Compilation message
circuit.cpp: In function 'void dfs(int)':
circuit.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (int i = 0; i < adj[u].size(); ++ i){
| ~~^~~~~~~~~~~~~~~
circuit.cpp: In function 'void get(int)':
circuit.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i = 0; i < adj[u].size(); ++ i){
| ~~^~~~~~~~~~~~~~~
circuit.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if (i < adj[u].size() - 1) val[v] = 1ll * val[v] * suf[u][i + 1] % mod;
| ~~^~~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'void build(int, int, int, int)':
circuit.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int mid = l + r >> 1;
| ~~^~~
circuit.cpp: In function 'void upd(int, int, int, int, int)':
circuit.cpp:98:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
98 | int mid = l + r >> 1;
| ~~^~~
/usr/bin/ld: /tmp/ccv2no0B.o: in function `main':
stub.cpp:(.text.startup+0x128): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
