题解 SP7259 【LITE - Light Switching】

发表于 | 更新于 | 阅读次数：

线段树裸题

我们将灯开着视为1，关着视为0。

那么一段区间开着的灯的数量就是这段区间的和，这样很容易就能想到用线段树来维护。

每次反转可以用懒标记来维护，

反转后开着的灯的数量就是这段区间的长度减去现在的这段区间开着的灯的数量

即 $f[k]=(r-l+1)-f[k]$;

比较好理解，可以当成线段树的入门题来做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h>
#define swap mswap
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
int a[8000100],f[8000010],n,m;
char s[2000100];
void swap(int &x,int &y)
{
	x^=y^=x^=y;
}
void read(int &x)
{
	x=0;
	char ch=getchar();
	int pd=1;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			pd=-pd;
		}
		ch=getchar();
	}
	while(ch<='9'&&ch>='0')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=pd;
}
void write(const int &x)
{
	char f[100001];
	int s=0;
	int tmp=x;
	if(tmp==0)
	{
		putchar('0');
		return;
	}
	if(tmp<0)
	{
		tmp=-tmp;
		putchar('-');
	}
	while(tmp>0)
	{
		f[s++]=tmp%10+'0';
		tmp/=10;
	}
	while(s>0)
	{
		putchar(f[--s]);
	}
}
void build(int k,int l,int r)
{
	if(l==r)
	{
		a[k]=s[l]-'0';
		f[k]=a[k];
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	f[k]=f[k<<1]+f[k<<1|1];
}
void add(int k,int l,int r)
{
	a[k]^=1;
	f[k]=r-l+1-f[k];
}
void push_down(int k,int l,int r)
{
	int mid=(l+r)>>1;
	if(a[k]&1)
	{
		add(k<<1,l,mid);
		add((k<<1)|1,mid+1,r);
		add(k,l,r);
	}
	f[k]=f[k<<1]+f[(k<<1)|1];
}
void change(int k,int l,int r,int p,int q)
{
	
	if(l>q||r<p)return;
	if(l>=p&&r<=q)
	{
		a[k]^=1;
		push_down(k,l,r);
		return;
	}
	int mid=(l+r)>>1;
	push_down(k,l,r);
	change(k<<1,l,mid,p,q);
	change(k<<1|1,mid+1,r,p,q);
	f[k]=f[k<<1]+f[(k<<1)|1];
}
int query(int k,int l,int r,int p,int q)
{
	push_down(k,l,r);
	if(l>q||r<p)
	{
		return 0;
	}
	if(l>=p&&r<=q)
	{
		return f[k];
	}
	int ans=0;
	int mid=(l+r)>>1;
	if(p<=mid)
	{
		ans+=query(k<<1,l,mid,p,q);
	}
	if(q>mid)
	{
		ans+=query((k<<1)|1,mid+1,r,p,q);
	}
	return ans;
}
int main()
{
	memset(a,0,sizeof(a));
	memset(f,0,sizeof(f));
	read(n);
	read(m);
	for(register int i=1;i<=m;++i)
	{
		int z=0,x=0,y=0;
		read(z);
		read(x);
		read(y);
		if(z==0)
		{
			change(1,1,n,x,y);
		}
		else 
		{
			write(query(1,1,n,x,y));puts("");
		}
	}
}