#include "circuit.h"
#include <iostream>
#include <vector>
#include <array>
#define ll long long
using namespace std;
vector <ll> adj[200000];
bool B[200000];
array<ll, 2> st[400000];
bool lazy[400000];
ll n, m, sz[200000], X[200000], M = 1e9 + 2022;
void dfs(ll u) {
sz[u] = adj[u].size();
for (auto v : adj[u]) {
dfs(v);
sz[u] *= sz[v];
sz[u] %= M;
}
if (!sz[u]) sz[u] = 1;
}
void solve(ll u, ll w) {
X[u] = w;
vector <ll> pref, suf;
pref.resize(adj[u].size());
suf.resize(adj[u].size());
for (int i=0; i<adj[u].size(); ++i) {
pref[i] = sz[adj[u][i]];
if (i) {
pref[i] *= pref[i-1];
pref[i] %= M;
}
}
for (int i=adj[u].size()-1; i>=0; --i) {
suf[i] = sz[adj[u][i]];
if (i != adj[u].size()-1) {
suf[i] *= suf[i+1];
suf[i] %= M;
}
}
for (int i=0; i<adj[u].size(); ++i) {
solve(adj[u][i], (w * (((i ? pref[i-1] : 1) * (i != adj[u].size()-1 ? suf[i+1] : 1)) % M))%M);
}
}
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = {X[l], 0};
if (B[l]) swap(st[id][0], st[id][1]);
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id][0] = st[id*2][0] + st[id*2+1][0];
st[id][1] = st[id*2][1] + st[id*2+1][1];
}
void push(ll id) {
if (lazy[id]) {
lazy[id*2] ^= 1;
lazy[id*2+1] ^= 1;
swap(st[id*2][0], st[id*2][1]);
swap(st[id*2+1][0], st[id*2+1][1]);
lazy[id] = 0;
}
}
void update(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql) return;
else if (ql <= l && r <= qr) {
lazy[id] ^= 1;
swap(st[id][0], st[id][1]);
return;
}
ll mid = (l+r)/2;
push(id);
update(id*2, l, mid, ql, qr);
update(id*2+1, mid+1, r, ql, qr);
st[id][0] = st[id*2][0] + st[id*2+1][0];
st[id][1] = st[id*2][1] + st[id*2+1][1];
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N, m = M;
for (int i=N; i<N+M; ++i) {
B[i] = A[i-N];
}
for (int i=1; i<P.size(); ++i) {
adj[P[i]].push_back(i);
}
dfs(0);
solve(0, 1);
build(1, n, n+m-1);
}
int count_ways(int L, int R) {
update(1, n, n+m-1, L, R);
return st[1][1];
}
int main() {
init(3, 4, {-1, 0, 1, 2, 1, 1, 0}, {1, 0, 1, 0});
cout << count_ways(3, 4) << '\n';
cout << count_ways(4, 5) << '\n';
cout << count_ways(3, 6) << '\n';
}
Compilation message
circuit.cpp: In function 'void solve(long long int, long long int)':
circuit.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (int i=0; i<adj[u].size(); ++i) {
| ~^~~~~~~~~~~~~~
circuit.cpp:37:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | if (i != adj[u].size()-1) {
| ~~^~~~~~~~~~~~~~~~~~
circuit.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i=0; i<adj[u].size(); ++i) {
| ~^~~~~~~~~~~~~~
circuit.cpp:43:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | solve(adj[u][i], (w * (((i ? pref[i-1] : 1) * (i != adj[u].size()-1 ? suf[i+1] : 1)) % M))%M);
| ~~^~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i=1; i<P.size(); ++i) {
| ~^~~~~~~~~
/usr/bin/ld: /tmp/ccb76jSq.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc2GTFnq.o:circuit.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
