#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 2e5+10;
const int mod = 1000002022;
int n, m, p[maxn], a[maxn];
vector<int> g[maxn];
int c[maxn], pw2[maxn], prd[maxn];
int tr0[4*maxn],tr1[4*maxn],lz[4*maxn];
void build(int no, int l, int r) {
if(l == r) {
tr0[no] = c[l]*prd[l];
tr1[no] = 0;
return;
}
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
build(f1,l,mid);
build(f2,mid+1,r);
}
void flush(int no, int l, int r) {
if(lz[no] == 0) return;
swap(tr0[no],tr1[no]);
if(l != r) {
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
lz[f1]^= 1;
lz[f2]^= 1;
}
}
void att(int no, int l, int r, int L, int R) {
flush(no,l,r);
if(l > R || r < L) return;
if(l >= L && r <= R) {
lz[no] = 1;
flush(no,l,r);
}
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
att(f1,l,mid,L,R);
att(f2,mid+1,r,L,R);
tr0[no] = (tr0[f1]+tr0[f2])%mod;
tr1[no] = (tr1[f1]+tr1[f2])%mod;
}
void dfssz(int u) {
c[u] = g[u].size();
if(u >= n) c[u] = 1;
if(u >= n) return;
for(auto v : g[u]) {
dfssz(v);
c[u] = c[u]*c[v]%mod;
}
}
void dfs(int u) {
vector<int> pf(g[u].size()+1), sf(g[u].size()+1);
for(int i = 0; i < (int) g[u].size(); i++) {
int v = g[u][i];
pf[i] = c[v];
if(i!=0) pf[i] = pf[i]*pf[i-1]%mod;
}
for(int i = (int) g[u].size()-1; i >= 0; i--) {
int v = g[u][i];
sf[i] = c[v];
if(i != (int) g[u].size()-1) sf[i] = sf[i]*sf[i+1]%mod;
}
for(int i = 0; i < (int) g[u].size(); i++) {
int v = g[u][i];
prd[v] = prd[u];
if(i != 0) prd[v] = prd[v]*pf[i-1]%mod;
if(i != (int) g[u].size()-1) prd[v] = prd[v]*sf[i+1]%mod;
}
for(auto v : g[u]) {
dfs(v);
}
}
int ans = 0;
void init(int32_t N, int32_t M, vector<int32_t> P, vector<int32_t> A) {
n = N;
m = M;
for(int i = 1; i < n+m; i++) {
p[i] = P[i];
g[p[i]].pb(i);
}
for(int i = 0; i < m; i++) {
a[i] = A[i];
}
pw2[0] = 1;
for(int i = 1; i <= n+m; i++) {
pw2[i] = pw2[i-1]*2%mod;
}
dfssz(0);
prd[0] = 1;
dfs(0);
build(1,n,n+m);
for(int i = n; i < n+m; i++) {
if(a[i-n] == 1) att(1,n,n+m,i,i);
}
for(int i = n; i < n+m; i++) ans+= a[i-n]*prd[i];
for(int i = 0; i < n+m; i++) {
// cout << i << " = " << c[i] << " " << prd[i] << endl;
}
}
int32_t count_ways(int32_t L, int32_t R) {
att(1,n,n+m,L,R);
return tr1[1];
for(int i = L; i <= R; i++) {
ans-= a[i-n]*prd[i]; ans%=mod; ans+= mod; ans%= mod;
a[i-n]^=1;
ans+= a[i-n]*prd[i]; ans%=mod;
}
return ans;
}
Compilation message
circuit.cpp: In function 'void flush(long long int, long long int, long long int)':
circuit.cpp:35:31: warning: unused variable 'mid' [-Wunused-variable]
35 | int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
10348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
10344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
10348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
19500 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
19500 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
10344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
10348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
10348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
