#include "circuit.h" #include <bits/stdc++.h> #define int long long const int mod = 1e9+2022; using namespace std; vector<int> prsum; int summ(int l,int r) { return prsum[r]-(l>0?prsum[l-1]:0); } struct seggy{ int n; vector<int> lazy,tree; void build(int l,int r,int idx,vector<int>&v) { if(l==r) { tree[idx] = v[l]; return; } int mid = l+r>>1; build(l,mid,2*idx,v); build(mid+1,r,2*idx+1,v); tree[idx] = tree[2*idx]+tree[2*idx+1]; } seggy(vector<int>&v){ n = v.size(); lazy.resize(4*n,0),tree.resize(4*n,0); build(0,n-1,1,v); } void pass(int l,int r,int idx) { if(lazy[idx]==0) return; tree[idx] = summ(l,r)-tree[idx]; lazy[idx] = 0; if(l==r)return; lazy[2*idx]^=1; lazy[2*idx+1]^=1; } int query(int l,int r,int L,int R,int idx) { pass(l,r,idx); if(l>R||r<L)return 0ll; if(l>=L&&r<=R)return tree[idx]; int mid = l+r>>1; return query(l,mid,L,R,2*idx)+query(mid+1,r,L,R,2*idx+1); } int query(int l,int r) { return query(0,n-1,l,r,1); } void update(int l,int r,int L,int R,int idx) { pass(l,r,idx); if(l>R||r<L)return; if(l>=L&&r<=R) { lazy[idx]=1; pass(l,r,idx); return; } int mid = l+r>>1; update(l,mid,L,R,2*idx); update(mid+1,r,L,R,2*idx+1); tree[idx] = tree[2*idx]+tree[2*idx+1]; } void update(int l,int r) { update(0,n-1,l,r,1); } }; vector<int> dumy = {0,1}; seggy mile(dumy); int n,m; vector<int> p,v; vector<int> coeff; void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) { n = N,m = M; p.resize(n+m),v.resize(m); vector<int> mult(n+m,1); coeff.resize(m); vector<vector<int>> graph(n+m); for(int i = 0; i < n+m; i++) p[i] = P[i]; for(int i = 0; i < m; i++) v[i] = A[i]; for(int i = 1; i < n+m; i++) graph[p[i]].push_back(i); vector<int> hlp(n+m,1); function<void(int)> dfs = [&](int cur) { if(graph[cur].empty())return; for(int a: graph[cur]) dfs(a); int k = graph[cur].size(); vector<int> suf(k,1); vector<int> pref(k,1); for(int i = 0; i < k; i++) pref[i] = (i>0?pref[i-1]:1)*mult[graph[cur][i]]%mod; for(int i = k-1; i >= 0; i--) suf[i] = (i<k-1?suf[i+1]:1)*mult[graph[cur][i]]%mod; for(int i = 0; i <k;i++) hlp[graph[cur][i]]=(i>0?pref[i-1]:1)*(i<k-1?suf[i+1]:1)%mod; for(int a :graph[cur]) mult[cur]=mult[a]*mult[cur]%mod; mult[cur]=k*mult[cur]%mod; }; dfs(0); function<void(int,int)> pass = [&](int cur,int run){ if(cur>=n) coeff[cur-n] = run*hlp[cur]%mod; else { for(int a: graph[cur]) pass(a,run*hlp[cur]%mod); } }; pass(0,1); prsum.resize(m); for(int i = 0; i < m; i++) prsum[i] = (i>0?prsum[i-1]:0)+coeff[i]; mile = seggy(coeff); for(int i = 0; i< m; i++) if(!v[i]) mile.update(i,i); } signed count_ways(signed L, signed R) { mile.update(L-n,R-n); return mile.tree[1]%mod; }