#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct node{
int s,e,m;
ii val={0,0};
bool lazy=false;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void propo(){
if (!lazy) return;
swap(val.fi,val.se);
if (s!=e){
l->lazy^=true;
r->lazy^=true;
}
lazy=false;
}
void update(int i,ii k){
if (s==e) val=k;
else{
if (i<=m) l->update(i,k);
else r->update(i,k);
val={l->val.fi+r->val.fi,l->val.se+r->val.se};
}
}
void update(int i,int j){
propo();
if (s==i && e==j) lazy^=true;
else{
if (j<=m) l->update(i,j);
else if (m<i) r->update(i,j);
else l->update(i,m),r->update(m+1,j);
l->propo(),r->propo();
val={l->val.fi+r->val.fi,l->val.se+r->val.se};
}
}
} *root=new node(0,100005);
const int MOD=1000002022;
int n,m;
vector<int> al[100005];
int coef[100005];
int arr[100005];
int ss[100005];
void dfs_ss(int i){
if (i<n){
ss[i]=sz(al[i]);
for (auto it:al[i]){
dfs_ss(it);
ss[i]=s[i]*ss[it]%MOD;
}
}
else ss[i]=1;
}
void dfs(int i,int ans){
if (i<n){
vector<int> v;
for (auto it:al[i]) v.pub(ss[it]);
vector<int> f={1},b={1};
rep(x,0,sz(v)) f.pub(f.back()*v[x]%MOD);
rep(x,sz(v),0) b.pub(b.back()*v[x]%MOD);
reverse(all(b));
rep(x,0,sz(v)) dfs(al[i][x],ans*f[x]%MOD*b[x+1]%MOD);
}
else coef[i-n]=ans;
}
void init(signed N, signed M, vector<signed> P, vector<signed> A) {
n=N,m=M;
rep(x,1,n+m) al[P[x]].pub(x);
rep(x,0,m) arr[x]=A[x];
dfs_ss(0);
dfs(0,1);
rep(x,0,m) cout<<coef[x]<<" "; cout<<endl;
rep(x,0,m){
if (A[x]) root->update(x,{coef[x],0});
else root->update(x,{0,coef[x]});
}
}
signed count_ways(signed a, signed b) {
root->update(a-n,b-n);
return root->val.fi;
}
Compilation message
circuit.cpp: In constructor 'node::node(long long int, long long int)':
circuit.cpp:31:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | s=_s,e=_e,m=s+e>>1;
| ~^~
circuit.cpp: In function 'void dfs_ss(long long int)':
circuit.cpp:88:10: error: 's' was not declared in this scope
88 | ss[i]=s[i]*ss[it]%MOD;
| ^
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:18:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
18 | #define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
| ^~~
circuit.cpp:118:2: note: in expansion of macro 'rep'
118 | rep(x,0,m) cout<<coef[x]<<" "; cout<<endl;
| ^~~
circuit.cpp:118:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
118 | rep(x,0,m) cout<<coef[x]<<" "; cout<<endl;
| ^~~~
