#include <bits/stdc++.h>
#ifndef SKY
#include "circuit.h"
#endif // SKY
using namespace std;
#define N 500010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back
int n,times;
vector<int>g[N];
ii cnt[N];
ll f[N],dp[N];
const ll mod=1000002022;
void selfmull(ll&u,ll v)
{
v%=mod;
u=u*v%mod;
}
struct IT_nhan
{
ll ST[N*4]={};
void init(int n)
{
for(int i=1;i<=n*4;i++)
ST[i]=1;
}
void update(int id,int l,int r,int u,int v,ll val)
{
if(l>v||r<u)
return;
// cout<<l<<" "<<r<<" "<<u<<" "<<v<<" "<<val<<endl;
if(l>=u&&r<=v)
{
selfmull(ST[id],val);
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,v,val);
update(id*2+1,mid+1,r,u,v,val);
}
ll get(int id,int l,int r,int i)
{
//cout<<id<<" "<<l<<" "<<r<<" "<<i<<endl;
if(l>i||r<i)
return 1;
ll res=ST[id];
if(l==r)
return res;
int mid=(l+r)/2;
selfmull(res,get(id*2,l,mid,i));
selfmull(res,get(id*2+1,mid+1,r,i));
return res;
}
}nhan;
struct IT_cong
{
struct node
{
ll sum=0,val=0;
int t=0;
}ST[N*4];
void down(int id)
{
if(ST[id].t==0)
return;
ST[id*2].t^=1;
ST[id*2+1].t^=1;
ST[id*2].val=(ST[id*2].sum-ST[id*2].val);
ST[id*2+1].val=(ST[id*2+1].sum-ST[id*2+1].val);
ST[id].t=0;
}
void update(int id,int l,int r,int i,ll val)
{
if(l>i||r<i)
return;
if(l==r)
{
// cout<<i<<" "<<val<<endl;
ST[id].sum=val;
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,i,val);
update(id*2+1,mid+1,r,i,val);
ST[id].sum=ST[id*2].sum+ST[id*2+1].sum;
}
void flip(int id,int l,int r,int u,int v)
{
if(l>v||r<u)
return;
// cout<<l<<" "<<r<<" "<<u<<" "<<v<<endl;
if(l>=u&&r<=v)
{
ST[id].val=(ST[id].sum-ST[id].val);
ST[id].t^=1;
//cout<<ST[id].val<<endl;
return;
}
down(id);
int mid=(l+r)/2;
flip(id*2,l,mid,u,v);
flip(id*2+1,mid+1,r,u,v);
ST[id].val=ST[id*2].val+ST[id*2+1].val;
}
}cong;
void DFS(int u)
{
f[u]=max(1,(int)g[u].size());
cnt[u].fs=++times;
for(auto v:g[u])
{
DFS(v);
selfmull(f[u],f[v]);
}
cnt[u].sc=times;
ll S=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
nhan.update(1,1,n,cnt[v].fs,cnt[v].sc,S);
selfmull(S,f[v]);
}
S=1;
for(int i=g[u].size()-1;i>=0;i--)
{
int v=g[u][i];
nhan.update(1,1,n,cnt[v].fs,cnt[v].sc,S);
selfmull(S,f[v]);
}
}
void init(int NNN, int MMM, vector<int> P, vector<int> A)
{
n=NNN+MMM;
for(int i=1;i<n;i++)
g[P[i]].pb(i);
nhan.init(n);
DFS(0);
for(int i=NNN;i<n;i++)
{
dp[i]=nhan.get(1,1,n,cnt[i].fs);
// cout<<i<<" "<<dp[i]<<endl;
cong.update(1,1,n,i+1,dp[i]);
}
for(int i=0;i<MMM;i++)
if(A[i]==1)
cong.flip(1,1,n,NNN+i+1,NNN+i+1);assert(0);
}
int count_ways(int L, int R)
{
cong.flip(1,1,n,L+1,R+1);
return (cong.ST[1].val%mod+mod*mod)%mod;
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
vector<int>P(n+m),A(m);
for(int i=0;i<n+m;i++)
cin>>P[i];
for(int i=0;i<m;i++)
cin>>A[i];
init(n,m,P,A);
int q;
cin>>q;
while(q--)
{
int L,R;
cin>>L>>R;
cout<<count_ways(L,R)<<endl;
}
return 0;
}
#endif
Compilation message
circuit.cpp: In function 'void DFS(int)':
circuit.cpp:135:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for(int i=0;i<g[u].size();i++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
24272 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
24272 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
24272 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
63 ms |
37880 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
63 ms |
37880 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
24272 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
24272 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
24272 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
