#include "circuit.h"
#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
const long long mod = 1e9 + 2022;
int n, m;
vector<int> g[maxn];
long long contribution[maxn];
long long power(long long a, long long b)
{
if (b == 0)
{
return 1LL;
}
if (b % 2 == 0)
{
long long result = power(a, b / 2);
return (result * result) % mod;
}
return (a * power(a, b - 1)) % mod;
}
void dfs(int node, int dep)
{
if (g[node].empty())
{
contribution[node] = power(2, n - dep);
return;
}
for (int i = 0; i < g[node].size(); ++i)
{
dfs(g[node][i], dep + 1);
}
}
long long preffix[maxn];
long long get_sum(int l, int r)
{
if (l == 0)
{
return preffix[r];
}
return (preffix[r] - preffix[l - 1] + mod) % mod;
}
struct segment_tree
{
struct vertex
{
long long sum;
bool lazy;
vertex()
{
sum = 0;
lazy = false;
}
vertex(long long _sum, bool _lazy)
{
sum = _sum;
lazy = _lazy;
}
};
vertex tree[4 * maxn];
void push_lazy(int node, int l, int r)
{
if (tree[node].lazy == true)
{
tree[node].sum = get_sum(l, r) - tree[node].sum;
if (l != r)
{
tree[2 * node].lazy = 1 - tree[2 * node].lazy;
tree[2 * node + 1].lazy = 1 - tree[2 * node + 1].lazy;
}
tree[node].lazy = false;
}
}
void update(int node, int l, int r, int ql, int qr)
{
push_lazy(node, l, r);
if (l > qr || r < ql)
{
return;
}
if (ql <= l && r <= qr)
{
tree[node].lazy = true;
push_lazy(node, l, r);
return;
}
int mid = (l + r) / 2;
update(2 * node, l, mid, ql, qr);
update(2 * node + 1, mid + 1, r, ql, qr);
tree[node].sum = tree[2 * node].sum + tree[2 * node + 1].sum;
}
void update(int l, int r)
{
update(1, 0, m - 1, l, r);
}
};
segment_tree tree;
void init(int N, int M, vector<int> P, vector<int> A)
{
n = N;
m = M;
for (int i = 1; i < P.size(); ++i)
{
g[P[i]].push_back(i);
}
dfs(0, 0);
for (int i = 0; i < m; ++i)
{
preffix[i] = contribution[i + n];
if (i > 0)
{
preffix[i] += preffix[i - 1];
}
preffix[i] %= mod;
}
for (int i = 0; i < m; ++i)
{
if (A[i] == 1)
{
tree.update(i, i);
}
}
}
int count_ways(int L, int R)
{
int l = L - n;
int r = R - n;
tree.update(l, r);
return tree.tree[1].sum;
}
Compilation message
circuit.cpp: In function 'void dfs(int, int)':
circuit.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i = 0; i < g[node].size(); ++i)
| ~~^~~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:134:23: 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 = 1; i < P.size(); ++i)
| ~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccN2BRQ5.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cccW4jI1.o:circuit.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
