| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1315081 | Rares | 디지털 회로 (IOI22_circuit) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e5+10;
const int MOD=1000002022;
int c[MAXN],n,m,s[MAXN],a[MAXN];
vector <int> g[MAXN];
void dfs (int node){
int aux=g[node].size();
s[node]=max (1LL*1,aux);
for (auto x:g[node]){
dfs (x);
s[node]=1LL*s[node]*s[x]%MOD;
}
}
void solve (int node){
vector <int> dpp(g[node].size ()),dps(g[node].size ());
for (int i=0;i<g[node].size ();++i){
int x=g[node][i];
if (i==0) dpp[i]=s[x];
else dpp[i]=1LL*dpp[i-1]*s[x];
}
for (int i=g[node].size ()-1;i>=0;--i){
int x=g[node][i];
if (i==g[node].size ()-1) dps[i]=s[x];
else dps[i]=1LL*dps[i+1]*s[x];
}
for (int i=0;i<g[node].size ();++i){
int crt=c[node],x=g[node][i];
if (i!=0) crt=1LL*crt*dpp[i-1]%MOD;
if (i!=g[node].size()-1) crt=1LL*crt*dps[i+1]%MOD;
c[x]=crt;
solve (x);
}
}
struct AINT{
int aint[4*MAXN],lazy[4*MAXN],sum[MAXN];
void init (int node, int l, int r){
if (l==r){
sum[node]=c[l+n];
if (a[l]) aint[node]=sum[node];
else aint[node]=0;
return;
}
int mij=(l+r)/2;
init (2*node,l,mij);
init (2*node+1,mij+1,r);
sum[node]=(sum[2*node]+sum[2*node+1])%MOD;
aint[node]=(aint[2*node]+aint[2*node+1])%MOD;
}
void lz (int node, int l, int r){
if (lazy[node]==0) return;
aint[node]=(sum[node]-aint[node]+MOD)%MOD;
if (l!=r){
lazy[2*node]^=lazy[node];
lazy[2*node+1]^=lazy[node];
}
lazy[node]=0;
}
void update (int node, int l, int r, int ql, int qr){
lz (node,l,r);
if (r<ql or l>qr) return;
if (ql<=l and r<=qr){
lazy[node]^=1;
lz (node,l,r);
return;
}
int mij=(l+r)/2;
update (2*node,l,mij,ql,qr);
update (2*node+1,mij+1,r,ql,qr);
aint[node]=(aint[2*node]+aint[2*node+1])%MOD;
}
void update (int l, int r){
l-=n;
r-=n;
update (1,0,m-1,l,r);
}
}v;
void init (int N, int M, vector <int> p, vector <int> A){
n=N;
m=M;
for (int i=0;i<m;++i) a[i]=A[i];
for (int i=1;i<p.size ();++i){
g[p[i]].push_back (i);
}
dfs (0);
c[0]=1;
solve (0);
v.init (1,0,m-1);
}
int count_ways (int l, int r){
v.update (l,r);
cout <<v.aint[1];
}