#include "circuit.h"
#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
const int MOD=1000002022, MAXN=(1<<3);
// maxn maxn
int n, m;
vector<int> parent, a;
vector<int> adj[MAXN];
int subtree[2*MAXN];
long long factor[2*MAXN];
long long ones[2*MAXN-1], zeros[2*MAXN-1];
int lazy[2*MAXN-1]={0};
long long power(long long n, long long k)
{
long long result=1, mul=n;
for (int i=0; i<32; i++)
{
if (k&(1<<i))
result=result*mul%MOD;
mul=mul*mul%MOD;
}
return result;
}
void calcsize(int x)
{
if (x>=n)
subtree[x]=0;
else
subtree[x]=1;
for (auto y : adj[x])
{
calcsize(y);
subtree[x]=subtree[x]+subtree[y];
}
return;
}
void calcfactor(int x, long long current)
{
if (x!=0)
current=current*power(2, subtree[x])%MOD;
factor[x]=current;
for (auto y : adj[x])
calcfactor(y, current);
return;
}
void propagate(int x, int l, int r)
{
if (r-l==1)
{
lazy[x]=0;
return;
}
if (lazy[x]==0)
return;
swap(ones[2*x+1], zeros[2*x+1]);
swap(ones[2*x+2], zeros[2*x+2]);
lazy[2*x+1]=(lazy[2*x+1]+1)%2;
lazy[2*x+2]=(lazy[2*x+2]+1)%2;
lazy[x]=0;
return;
}
void update(int x, int l, int r, int lt, int rt)
{
if (l>=rt || r<=lt)
return;
propagate(x, l, r);
if (l>=lt && r<=rt)
{
swap(ones[x], zeros[x]);
lazy[x]=(lazy[x]+1)%2;
return;
}
update(2*x+1, l, (l+r)/2, lt, rt);
update(2*x+2, (l+r)/2, r, lt, rt);
ones[x]=(ones[2*x+1]+ones[2*x+2])%MOD;
zeros[x]=(zeros[2*x+1]+zeros[2*x+2])%MOD;
return;
}
void buildtree(int x, int l, int r)
{
if (r-l==1)
{
if (l>=m)
{
ones[x]=0;
zeros[x]=0;
return;
}
if (a[l]==1)
{
ones[x]=factor[l+n];
zeros[x]=0;
}
else
{
ones[x]=0;
zeros[x]=factor[l+n];
}
return;
}
buildtree(2*x+1, l, (l+r)/2);
buildtree(2*x+2, (l+r)/2, r);
ones[x]=(ones[2*x+1]+ones[2*x+2])%MOD;
zeros[x]=(zeros[2*x+1]+zeros[2*x+2])%MOD;
return;
}
void init(int N, int M, vector<int> P, vector<int> A)
{
n=N;
m=M;
parent=P;
a=A;
for (int i=1; i<n+m; i++)
adj[parent[i]].push_back(i);
calcsize(0);
calcfactor(0, 1);
buildtree(0, 0, MAXN);
//for (int i=0; i<n+m; i++)
// cout << factor[i] << ' ';
//cout << '\n';
//cout << "root " << ones[0] << ' ' << zeros[0] << '\n';
//for (int i=0; i<m; i++)
// cout << zeros[i+MAXN-1] << ' ' << ones[i+MAXN-1] << '\n';
return;
}
int count_ways(int l, int r)
{
l=l-n;
r=r-n;
update(0, 0, MAXN, l, r+1);
//long long total=(ones[0]+MOD-zeros[0])%MOD;
long long total=ones[0];
return total;
}
Compilation message
/usr/bin/ld: /tmp/ccSvG7mY.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccskv6GZ.o:circuit.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
