#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#ifdef DEBUG
auto& operator<<(auto& os, pair<auto, auto> &p) {
return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto& os, const auto &v) {
os<<"{";
for(auto it=begin(v);it!=end(v);++it) {
if(it != begin(v)) os<<", ";
os<<(*it);
}
return os<<"}";
}
void dbg_out(auto... x) {
((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif
const ll mod = 1000002022;
struct SegTree {
int base;
vector<ll> tree, inv;
vector<bool> lazy;
void merge(int v) {
tree[v] = tree[v*2] + tree[v*2+1];
inv[v] = inv[v*2] + inv[v*2+1];
}
void build(int v, int l, int r, const vector<ll> &vals, const vector<int> &a) {
if(l+1 == r) {
tree[v] = vals[l];
if(!a[l]) swap(tree[v], inv[v]);
return;
}
int mid = (l + r) / 2;
build(v*2, l, mid, vals, a);
build(v*2+1, mid, r, vals, a);
merge(v);
}
SegTree(const vector<ll> &vals, const vector<int> &a) {
base = bit_ceil(uint(vals.size()));
tree.assign(2*base, 0);
inv.assign(2*base, 0);
lazy.assign(2*base, 0);
build(1, 0, base, vals, a);
}
void push(int v) {
if(lazy[v]) {
swap(tree[v*2], inv[v*2]);
lazy[v*2] = !lazy[v*2];
swap(tree[v*2+1], inv[v*2+1]);
lazy[v*2+1] = !lazy[v*2+1];
lazy[v] = false;
}
}
void update(int v, int l, int r, int a, int b) {
if(r <= a || b <= l) return;
if(a <= l && r <= b) {
swap(tree[v], inv[v]);
lazy[v] = !lazy[v];
return;
}
push(v);
int mid = (l + r) / 2;
update(v*2, l, mid, a, b);
update(v*2+1, mid, r, a, b);
merge(v);
}
};
int n, m;
vi p, a;
vector<vi> g;
vector<ll> mult;
void dfs_mult(int v) {
if(v >= n) return;
dbg(v, g[v]);
mult[v] = ll(sz(g[v]));
for(auto e : g[v]) {
dfs_mult(e);
if(e < n)
mult[v] = mult[v] * mult[e] % mod;
}
}
vector<ll> weight;
void dfs(int v, ll w) {
if(v >= n) {
weight[v - n] = w;
return;
}
dbg(v, w);
vector<ll> pref(sz(g[v]) + 1, 1), suff(sz(g[v]) + 1, 1);
rep(i,0,sz(g[v])) {
pref[i+1] = (pref[i] * mult[g[v][i]]) % mod;
suff[i+1] = (suff[i] * mult[g[v][sz(g[v]) -i-1]]) % mod;
}
dbg(pref, suff);
rep(i,0,sz(g[v])) {
ll we = pref[i] * suff[i] % mod;
dfs(g[v][i], w * we % mod);
}
}
SegTree *tree;
void init(int N, int M, vi P, vi A) {
n = N; m = M; p = P; a = A;
g.resize(n);
rep(i,1,n+m)
g[p[i]].push_back(i);
mult.assign(n+m, 1);
dfs_mult(0);
dbg(mult);
weight.resize(m);
dfs(0, 1);
dbg(weight);
tree = new SegTree(weight, a);
}
int count_ways(int L, int R) {
tree->update(1,0,tree->base,L-n,R-n+1);
dbg(tree->tree);
dbg(tree->inv);
dbg(tree->lazy);
return tree->tree[1];
// rep(i,L-n,R-n+1)
// a[i] = !a[i];
// ll res = 0;
// rep(i,0,m)
// if(a[i]) res = (res + weight[i]) % mod;
// return (int)res;
}
Compilation message
circuit.cpp: In constructor 'SegTree::SegTree(const std::vector<long long int>&, const std::vector<int>&)':
circuit.cpp:58:10: error: 'bit_ceil' was not declared in this scope
58 | base = bit_ceil(uint(vals.size()));
| ^~~~~~~~
