#include "circuit.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
constexpr int mod = 1'000'002'022;
struct SegTree {
int n, N;
vi prefix;
int prefSum(int l, int r) {
return (prefix[r] - prefix[l] + mod) % mod;
}
vi tree;
vi lazy;
SegTree() = default;
SegTree(vi values, vector<signed> assignment) {
n = values.size();
N = 1;
while (N < n) N *= 2;
prefix = vi(n + 1);
loop(i, n) {
prefix[i + 1] = (prefix[i] + values[i]) % mod;
}
tree = vi(2 * N);
lazy = vi(2 * N);
loop(i, n) {
tree[N + i] = assignment[i] ? values[i] : 0;
}
for (int i = N - 1; i >= 1; i--) {
tree[i] = (tree[2 * i] + tree[2 * i + 1]) % mod;
}
}
int get(int l, int r, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1) {
tr = N;
}
if (lazy[i]) {
tree[i] = (prefSum(tl, tr) - tree[i] + mod) % mod;
if (tr - tl > 1) {
lazy[2 * i] ^= true;
lazy[2 * i + 1] ^= true;
}
lazy[i] = false;
}
if (tr <= l || tl >= r) {
return tree[i];
}
if (tl >= l && tr <= r) {
tree[i] = (prefSum(tl, tr) - tree[i] + mod) % mod;
if (tr - tl > 1) {
lazy[2 * i] ^= true;
lazy[2 * i + 1] ^= true;
}
return tree[i];
}
int tm = (tl + tr) / 2;
return (get(l, r, 2 * i, tl, tm) + get(l, r, 2 * i + 1, tm, tr)) % mod;
}
};
int n, m;
vvi children;
vector<signed> assignment;
vi c;
int dfs(int node) { //a
if (node >= n) {
return { assignment[node - n] };
}
vii counts; //c, a
for (int child : children[node]) {
int res = dfs(child);
counts.push_back({c[child], res});
}
/*
2 children:
a =
1 * (a[0] * b[1] + b[0] * a[1]) +
2 * (a[0] * a[1])
=
1 * (a[0] * (c[1] - a[1]) + (c[0] - a[0]) * a[1]) +
2 * (a[0] * a[1])
= a[0] * c[1] + c[0] * a[1]
*/
/*
a - b
|
c - d
|
e
c = e * 1 + d * 1
a = c * 1 + b * 2 = (e * 1 + d * 1) + b * 2
*/
return (counts[0].first * counts[1].second + counts[0].second * counts[1].first) % mod;
}
vi factors;
void cDfs(int node) {
if (node >= n) {
c[node] = 1;
return;
}
vii out;
c[node] = children[node].size();
for (int child : children[node]) {
cDfs(child);
c[node] = (c[node] * c[child]) % mod;
}
}
void factorDfs(int node, int factor) {
if (node >= n) {
factors[node - n] = factor;
return;
}
factorDfs(children[node][0], (factor * c[children[node][1]]) % mod);
factorDfs(children[node][1], (factor * c[children[node][0]]) % mod);
}
SegTree segTree;
void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
n = N;
m = M;
children = vvi(n);
assignment = A;
c = vi(n + m);
factors = vi(m);
for (int i = 1; i < n + m; i++) {
children[P[i]].push_back(i);
}
cDfs(0);
factorDfs(0, 1);
segTree = SegTree(factors, assignment);
}
signed count_ways(signed L, signed R) {
int res = segTree.get(L - n, R - n + 1);
// for (int i = L; i <= R; i++) {
// assignment[i - n] ^= 1;
// }
// int res = 0;
// loop(i, m) {
// res = (res + assignment[i] * factors[i]) % mod;
// }
return res;
/*
3 children:
a =
1 * (a[0] * b[1] * b[2] + b[0] * a[1] * b[2] + b[0] * b[1] * a[2]) +
2 * (a[0] * a[1] * b[2] + a[0] * b[1] * a[2] + b[0] * a[1] * a[2]) +
3 * (a[0] * a[1] * a[2])
=
1 * (a[0] * (c[1] - a[1]) * (c[2] - a[2]))
2 * (a[0] * a[1] * (c[2] - a[2]))
3 * (a[0] * a[1] * a[2])
=
(1 + 2 - 3) * (a[0] * a[1] * a[2])
a[0] * c[1] * c[2]
2 * (a[0] * a[1] * c[2]) - 2 * (a[0] * a[1] * c[2])
C = c[0] * c[1] * c[2] * 3
b = C - a
=
2 children:
a =
1 * (a[0] * b[1] + b[0] * a[1]) +
2 * (a[0] * a[1])
=
1 * (a[0] * (c[1] - a[1]) + (c[0] - a[0]) * a[1]) +
2 * (a[0] * a[1])
= a[0] * c[1] + c[0] * a[1]
C = c[0] * c[1] * 2
b = C - a
=
*/
//return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
438 ms |
5464 KB |
2nd lines differ - on the 1st token, expected: '394586018', found: '357186114' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
438 ms |
5464 KB |
2nd lines differ - on the 1st token, expected: '394586018', found: '357186114' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
