Code[VS]1690 开关灯 题解
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description：
YYX家门前的街上有N(2<=N<=100000)盏路灯，在晚上六点之前，这些路灯全是关着的，六点之后，会有M(2<=m<=100000)个人陆续按下开关，这些开关可以改变从第i盏灯到第j盏灯的状态，现在YYX想知道，从第x盏灯到第y盏灯中有多少是亮着的(1<=i,j,x,y<=N)
输入描述 Input Description：
第 1 行: 用空格隔开的两个整数N和M
第 2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号(0代表按下开关，1代表询问状态), x 和 y
输出描述 Output Description：
第 1..询问总次数 行:对于每一次询问，输出询问的结果
样例输入 Sample Input：
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
样例输出 Sample Output：
1
2
数据范围及提示 Data Size & Hint：
一共4盏灯，5个操作，下面是每次操作的状态(X代表关上的，O代表开着的)：
XXXX -> OOXX -> OXOO -> 询问1~3 -> OOXX -> 询问1~4
——————————————————————————————————————————————
分析：
本题最暴力的思路，是用数组模拟区间开关灯的操作，但是数据量较大，暴力思路会超时。这时考虑使用带延迟标记的线段树。这道题属于比较明显的线段树题。
以下代码：
(代码比较长^_^)
#include "bits/stdc++.h" #define maxN 100010 using namespace std;
typedef long long QAQ; struct Tree
{
int l, r ;
QAQ sum ;//当前开着的灯数量
bool idv;//开关灯的延迟标记
}; QAQ Min(QAQ a, QAQ b)
{
return a > b ? b : a;
} Tree tr[maxN << ]; void Push_down ( int i , int m)
{
if(tr[i].idv)//当前结点有延迟标记
{
tr[i << ].idv = !tr[i << ].idv ;//左
tr[i << | ].idv = !tr[i << | ].idv ;//右
tr[i << ].sum = tr[i << ].r - tr[i << ].l + - tr[i << ].sum ;//所以灯开关状态取反
tr[i << | ].sum = tr[i << | ].r - tr[i << | ].l + - tr[i << | ].sum ;//同上
tr[i].idv = !tr[i].idv ;//清零！！！
}
} void Build_Tree (int x , int y, int i)
{
tr[i].l = x ;//左端点
tr[i].r = y ;//右端点
if( x == y)return ;
else
{
QAQ mid = (tr[i].l + tr[i].r ) >> ;
Build_Tree ( x , mid , i << );//左递归
Build_Tree (mid + , y , i << | );//右递归
}
} void Update_Tree (int q , int w , int i)
{
if( w >= tr[i].r && q <= tr[i].l)//被完全包含
{
tr[i].idv = !tr[i].idv;//延迟标记
QAQ tot = tr[i].r - tr[i].l + ;//当前结点总共的灯
tr[i].sum = tot - tr[i].sum;//开关状态全部取反
return ;
}
else
{
Push_down( i , tr[i].r - tr[i].l + );//信息下传函数
QAQ mid = (tr[i].l + tr[i].r) >> ;
if( q > mid )
{
Update_Tree ( q , w , i << | );
}
else if ( w <= mid )
{
Update_Tree ( q , w , i << );
}
else
{
Update_Tree ( q , w , i << | );
Update_Tree ( q , w , i << );
}
tr[i].sum = tr[i << ].sum + tr[i << | ].sum ;//回溯更新
}
} QAQ Query_Tree (int q , int w , int i )
{
if( w >= tr[i].r && q <= tr[i].l)
{
return tr[i].sum;//被完全包含直接返回值
}
else
{
Push_down( i , tr[i].r - tr[i].l + );
QAQ mid = (tr[i].l + tr[i].r ) >> ;
if( q > mid )
{
return Query_Tree ( q , w , i << | );
}
else if ( w <= mid )
{
return Query_Tree ( q , w , i << );
}
else
{
return Query_Tree ( q , w , i << | ) + Query_Tree ( q , w , i << );
}
}
} int main ( )
{
QAQ N, M;
int op, l, r;
scanf("%d%d", &N, &M);
Build_Tree ( , N , );//建树操作
while (M--)
{
scanf("%d", &op);
if( !op )
{
scanf("%d%d", &l, &r);
Update_Tree ( l , r , );//更新树
}
else
{
scanf("%d%d", &l, &r);
printf("%lld\n", Query_Tree ( l , r , ));//查询
}
}
return ;
}
( 完 )