#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> w;
const ll mod = 1e9+2022;
struct Node{
Node *l_child, *r_child;
int l,r; bool lazy, flipped;
Node(){}
Node(int _l, int _r){
l = _l; r = _r; lazy = false;
int m = (l+r)/2;
if(r-l > 1){
l_child = new Node(l,m);
r_child = new Node(m,r);
}
//cout << l << " " << r << "\n";
}
void push(){
if(!lazy || r-l == 1) return;
else{
lazy = false;
l_child->lazy = !l_child->lazy;
r_child->lazy = !r_child->lazy;
}
}
void flip(int L, int R){
if(R <= l || L >= r) return; //not intersect
else if(L <= l && r <= R) lazy = !lazy;
else if(r-l == 1) lazy = !lazy;
else{
l_child->flip(L,R);
r_child->flip(L,R);
}
}
ll query(){
if(r-l == 1) return lazy * ((w[r] - w[l] + mod) % mod);
else{
push();
return (l_child->query() + r_child->query()) % mod;
}
}
};
ll exp(ll a, ll n){
if(n==0) return 1;
if(n==1) return a%mod;
ll x = exp(a, n/2);
if(n%2==0) return (x*x)%mod;
else return (((x*x)%mod)*a)%mod;
}
const ll p = 2;
const ll q = 223;
const ll r = 2242157;
const ll phi = (p-1)*(q-1)*(r-1);
struct mint{
int vp, vq; ll n;
mint(ll _n){
vp = 0; vq = 0;
n = _n;
while(n%p==0){vp++; n/=p;}
while(n%q==0){vq++; n/=q;}
n = n%mod;
}
mint(int _vp, int _vq, ll _n){
vp = _vp; vq = _vq; n = _n%mod;
}
friend mint operator *(mint a, mint b){
return mint(a.vp+b.vp, a.vq+b.vq, a.n*b.n);
}
mint inv(){
return mint(-vp, -vq, exp(n,phi-1));
}
friend mint operator /(mint a, mint b){
return a * b.inv();
}
ll to_int(){
assert(vp >= 0 && vq >= 0);
ll m=n;
m = (m*exp(p,vp)) % mod;
m = (m*exp(q,vq)) % mod;
return m;
}
};
int n,m;
Node tr(0,100005);
void init(int _n, int _m, std::vector<int> p, std::vector<int> a){
n = _n; m = _m;
//step 1: compute degree
vector<int> adj[n];
vector<int> d(n,0);
vector<mint> d_mod(n,1);
mint prod(1);
for(int i=1; i<n+m; ++i){
adj[p[i]].push_back(i);
d[p[i]]++;
}
for(int i=0; i<n; ++i){
d_mod[i] = mint(d[i]);
prod = prod * d_mod[i];
}
//step 2: dfs to find weight of each leaf
vector<mint> node_w(n+m, mint(1));
node_w[0] = prod;
vector<int> st(1,0);
while(!st.empty()){
int v = st[st.size()-1];
st.pop_back();
//cout << v << "\n";
for(int u : adj[v]){
node_w[u] = node_w[v] / d_mod[v];
cout << u << " " << node_w[u].to_int() << "\n";
if(u < n) st.push_back(u);
}
}
//step 3: build the tree
w.push_back(0);
for(int i=0; i<m; ++i){
w.push_back(w[i]+node_w[i+n].to_int());
//cout << w[i+1] << " ";
}
for(int i=0; i<m; ++i){
if(a[i] == 1) tr.flip(i,i+1);
}
}
int count_ways(int l, int r){
tr.flip(l-n,r-n+1);
return tr.query();
}
int main(){
vector<int> p = {-1, 0, 1, 2, 1, 1, 0};
vector<int> a = {1,0,1,0};
init(3, 4, p,a);
cout << count_ways(3,4) << "\n";
cout << count_ways(4,5) << "\n";
cout << count_ways(3,6) << "\n";
}
Compilation message
/usr/bin/ld: /tmp/cceouYpQ.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccUiEeqR.o:circuit.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
