区间开关灯模型

P3870 [TJOI2009] 开关

先看一道经典的区间开关灯问题的模型，维护一个lz 每次异或操作就好了

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}


int n,q,m;

// int e[N],ne[N],w[N],h[N],idx;
// void add(int a,int b,int c){
	// e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
// }



struct Segment{
	int l,r;
	int lz;
	int s;
}tr[N<<2];

void pushup(int u){
	tr[u].s = tr[u<<1].s + tr[u<<1|1].s;
}

void pushdown(int u){
	if(tr[u].lz){
		tr[u<<1].lz^=1;
		tr[u<<1|1].lz^=1;
		tr[u<<1].s = tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].s;
		tr[u<<1|1].s = tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].s;
		tr[u].lz = 0;
	}
}

void build(int u,int l,int r){
	tr[u] = {l,r,0,0};
	if(l==r)return;
	int mid = (l+r)/2;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}

void modify(int u,int l,int r){
	if(l<=tr[u].l&&tr[u].r<=r){
		tr[u].lz^=1;
		tr[u].s = tr[u].r-tr[u].l+1-tr[u].s;
		return;
	}
	
	pushdown(u);
	
	int mid = (tr[u].l+tr[u].r)/2;
	if(l<=mid)modify(u<<1,l,r);
	if(r>mid)modify(u<<1|1,l,r);
	pushup(u);
}


int query(int u,int l,int r){
	if(l<=tr[u].l&&tr[u].r<=r){
		return tr[u].s;
	}
	
	pushdown(u);
	int res = 0;
	int mid = (tr[u].l+tr[u].r)/2;
	if(l<=mid)res+=query(u<<1,l,r);
	if(r>mid)res+=query(u<<1|1,l,r);
	return res;
	
}






void solve()
{
	cin>>n>>q;
	build(1,1,n);
	
	while(q--){
		int op,l,r;cin>>op>>l>>r;
		if(!op)modify(1,l,r);
		else cout<<query(1,l,r)<<"\n";
	}

}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;
	//cin>>_;
	_ = 1;
	while(_--)solve();
	return 0;
}

E. Danil and a Part-time Job

再看一道这个问题的树上版本

结合一下dfn序处理区间问题就好了

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 2e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}


int n,q,m;

// int e[N],ne[N],w[N],h[N],idx;
// void add(int a,int b,int c){
	// e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
// }
int cost[N];
int dfn[N],in[N],out[N],times;
vector<int>g[N];

struct Segment{
	int l,r;
	int lz;
	int s;
}tr[N<<2];


void dfs(int u){
	in[u] = ++times;
	dfn[times] = u;
	for(int &t:g[u])dfs(t);
	out[u] = times;
}


void pushup(int u){
	tr[u].s = tr[u<<1].s + tr[u<<1|1].s;
}

void pushdown(int u){
	if(tr[u].lz){
		tr[u<<1].lz^=1;
		tr[u<<1|1].lz^=1;
		tr[u<<1].s = tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].s;
		tr[u<<1|1].s = tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].s;
		tr[u].lz = 0;
	}
}

void build(int u,int l,int r){
	tr[u] = {l,r};
	if(l==r){
		tr[u].lz = 0;
		tr[u].s = cost[dfn[l]];
		return;
	}
	int mid = (l+r)/2;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}

void modify(int u,int l,int r){
	if(l<=tr[u].l&&tr[u].r<=r){
		tr[u].lz^=1;
		tr[u].s = tr[u].r-tr[u].l+1-tr[u].s;
		return;
	}
	
	pushdown(u);
	
	int mid = (tr[u].l+tr[u].r)/2;
	if(l<=mid)modify(u<<1,l,r);
	if(r>mid)modify(u<<1|1,l,r);
	pushup(u);
}


int query(int u,int l,int r){
	if(l<=tr[u].l&&tr[u].r<=r){
		return tr[u].s;
	}
	
	pushdown(u);
	int res = 0;
	int mid = (tr[u].l+tr[u].r)/2;
	if(l<=mid)res+=query(u<<1,l,r);
	if(r>mid)res+=query(u<<1|1,l,r);
	return res;
	
}






void solve()
{
	cin>>n;
	for(int i=2;i<=n;++i){int fa;cin>>fa;g[fa].push_back(i);}
	dfs(1);
	for(int i=1;i<=n;i++)cin>>cost[i];
	build(1,1,n);
	cin>>q;

	while(q--){
		string op;cin>>op;
		int id;cin>>id;
		if(op=="get")cout<<query(1,in[id],out[id])<<"\n";
		else modify(1,in[id],out[id]);
	}
	
	
	
	
	

}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;
	//cin>>_;
	_ = 1;
	while(_--)solve();
	return 0;
}