#include "circuit.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAXN=2e5+6;
const ll mod=1000002022;
ll arr[MAXN];
ll fastpow(ll x,ll p)
{
if(p==0)return 1;
if(p==1)return x;
ll t=fastpow(x,p/2);
t*=t;t%=mod;
if(p%2==1)
{
t*=x;
t%=mod;
}
return t;
}
struct segment_tree
{
ll tree[4*MAXN];
ll lazy[4*MAXN];
void build(ll l,ll r,ll idx)
{
lazy[idx]=0;
if(l==r)
{
tree[idx]=arr[l]%mod;
return;
}
ll mid=(l+r)/2;
build(l,mid,idx*2);
build(mid+1,r,idx*2+1);
tree[idx]=(tree[idx*2]+tree[idx*2+1])%mod;
}
void push(ll l,ll r,ll idx)
{
if(lazy[idx]==0)return;
tree[idx]=mod-tree[idx];
tree[idx]%=mod;
if(l!=r)
{
lazy[idx*2]^=lazy[idx];
lazy[idx*2+1]^=lazy[idx];
}
lazy[idx]=0;
}
void update(ll idx,ll l,ll r,ll ql,ll qr)
{
push(l,r,idx);
if(qr<l)return;
if(ql>r)return;
if(l>=ql&&r<=qr)
{
lazy[idx]^=1;
push(l,r,idx);
//cout<<"%%% "<<l<<" "<<r<<" "<<tree[idx]<<endl;
return;
}
//cout<<"## "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
ll mid=(l+r)/2;
update(idx*2,l,mid,ql,qr);
update(idx*2+1,mid+1,r,ql,qr);
tree[idx]=(tree[idx*2]+tree[idx*2+1])%mod;
//cout<<"%%% "<<l<<" "<<r<<" "<<tree[idx]<<endl;
}
ll query(ll l,ll r,ll idx,ll ql,ll qr)
{
push(l,r,idx);
if(l>qr)return 0;
if(r<ql)return 0;
//cout<<"%% "<<l<<" "<<r<<" "<<tree[idx]<<endl;
if(l>=ql&&r<=qr)return tree[idx];
ll mid=(l+r)/2;
return (query(l,mid,idx*2,ql,qr)+query(mid+1,r,idx*2+1,ql,qr))%mod;
}
}tr;
ll m,n;
ll all_prod=1,sum1;
vector<ll>g[MAXN];
ll path_prod[MAXN];
ll subtree_prod[MAXN];
void dfs_subtrees(ll u)
{
subtree_prod[u]=max(1ll,(ll)g[u].size());
for(auto xd:g[u])
{
dfs_subtrees(xd);
subtree_prod[u]*=subtree_prod[xd];
subtree_prod[u]%=mod;
}
}
void dfs_prods(ll u)
{
if(g[u].size()==0)return;
vector<ll>pref_prods;
vector<ll>suf_prods;
for(ll i=0;i<g[u].size();i++)
{
if(i==0)pref_prods.push_back(max(1ll,subtree_prod[g[u][i]]));
else
{
pref_prods.push_back((pref_prods.back()*max(1ll,subtree_prod[g[u][i]]))%mod);
}
}
for(ll i=g[u].size()-1;i>=0;i--)
{
if(i==g[u].size()-1)suf_prods.push_back(max(1ll,subtree_prod[g[u][i]]));
else
{
suf_prods.push_back((suf_prods.back()*max(1ll,subtree_prod[g[u][i]]))%mod);
}
}
reverse(suf_prods.begin(),suf_prods.end());
for(ll i=0;i<g[u].size();i++)
{
ll prod1=1;
if(i>0)prod1*=pref_prods[i-1];
if(i+1<g[u].size())prod1*=suf_prods[i+1];
prod1%=mod;
//cout<<u<<" -> "<<g[u][i]<<" "<<path_prod[u]<<" * "<<prod1<<endl;
path_prod[g[u][i]]=(path_prod[u]*prod1)%mod;
dfs_prods(g[u][i]);
}
}
vector<int>a1;
ll slow_update(int l,int r)
{
for(int i=l;i<=r;i++)a1[i]=1-a1[i];
ll ret=0;
for(int i=0;i<a1.size();i++)
{
ret+=((ll)a1[i]*path_prod[n+i])%mod;
ret%=mod;
}
return ret;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
m=M;n=N;
a1=a;
for(ll i=1;i<N+M;i++)
{
g[P[i]].push_back(i);
}
for(ll i=0;i<N;i++)
{
ll t=g[i].size();
all_prod*=t;
all_prod%=mod;
}
path_prod[0]=1;
dfs_subtrees(0);
dfs_prods(0);
//cout<<all_prod<<endl;
for(ll i=0;i<M;i++)
{
//arr[i]=(all_prod*fastpow(path_prod[N+i],mod-2))%mod;
//cout<<path_prod[N+i]<<"|"<<arr[i]<<" ";
arr[i]=path_prod[N+i]%mod;
//cout<<path_prod[N+i]<<" ";
sum1+=arr[i];sum1%=mod;
if(A[i]==0)arr[i]=(mod-arr[i])%mod;
}
//cout<<endl;
tr.build(0,M-1,1);
//cout<<sum1<<" "<<tr.query(0,m-1,1,0,m-1)<<endl;
}
int count_ways(int L, int R) {
return slow_update(L-n, R-n);
//tr.update(1,0,m-1,L-n,R-n);
//return ((sum1+tr.query(0,m-1,1,0,m-1))%mod)/2ll;
}
Compilation message
circuit.cpp: In function 'void dfs_prods(long long int)':
circuit.cpp:101:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(ll i=0;i<g[u].size();i++)
| ~^~~~~~~~~~~~
circuit.cpp:111:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | if(i==g[u].size()-1)suf_prods.push_back(max(1ll,subtree_prod[g[u][i]]));
| ~^~~~~~~~~~~~~~~
circuit.cpp:118:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(ll i=0;i<g[u].size();i++)
| ~^~~~~~~~~~~~
circuit.cpp:122:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | if(i+1<g[u].size())prod1*=suf_prods[i+1];
| ~~~^~~~~~~~~~~~
circuit.cpp: In function 'long long int slow_update(int, int)':
circuit.cpp:134:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i=0;i<a1.size();i++)
| ~^~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:143:8: error: 'a' was not declared in this scope
143 | a1=a;
| ^
