题目
Description
在数轴上进行一系列操作。每次操作有两种类型，一种是在线段[a,b]上涂上颜色，另一种将[a,b]上的颜色擦去。
问经过一系列的操作后，有多少条单位线段[k,k+1]被涂上了颜色
Input
第一行两个整数n，m，表示数轴从0到n，操作数为m
接下来m行，每行三个整数op，a，b，op=0时表示将[a,b]上的颜色擦去，op=1时表示在线段[a,b]上涂上颜色
n,m<=100000
Output
输出一个整数，表示有多少条单位线段[k,k+1]被涂上了颜色
Sample Input
10 10
1 0 8
0 2 8
1 0 1
1 2 10
1 9 10
0 2 7
0 3 6
1 0 2
0 2 7
0 2 7
Sample Output
5
思路：
很明显的一道线段树区间修改，区间查询的题目；
不同的是，这一题维护的是每个区间是否覆盖，而不是加减；
那么就要分两种情况来看，一种涂颜色，另一种擦去；
就比如：
a[p].f=x; if(x==-1) a[p].v=0; if(x==1) a[p].v=a[p].r-a[p].l+1;
那么lazy标记下传是也是一样的；
if(a[p].f==1) { a[L(p)].v=a[L(p)].r-a[L(p)].l+1; a[R(p)].v=a[R(p)].r-a[R(p)].l+1; a[L(p)].f=1; a[R(p)].f=1; a[p].f=0; } else if(a[p].f==-1) { a[L(p)].v=0; a[R(p)].v=0; a[L(p)].f=-1; a[R(p)].f=-1; a[p].f=0; }
L（p）代表p左节点的编号，R（p）代表p右节点的编号；
这样就ok了
那么还有要注意的是，题目是求线段，而我们操作是维护区间节点；
所以读入的每一个y值都要减一个1；
最后直接查询根节点也就是1-n，包涵的1的个数就可以了；
代码
#include<bits/stdc++.h> typedef long long ll; using namespace std; inline ll read() { ll a=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();} return a*f; } ll n,m,aa[500001]; struct sbbb { ll l,r,v,f; }a[1000001]; inline ll R(ll x)//求左节点编号 { return x*2+1; } inline ll L(ll x)//求右节点编号 { return x*2; } inline void doit(ll p)//维护 { a[p].v=a[L(p)].v+a[R(p)].v; } inline void build(ll p,ll l,ll r) { a[p].l=l;a[p].r=r; if(l==r) { a[p].v=aa[l]; return; } ll mid=(l+r)>>1; build(L(p),l,mid); build(R(p),mid+1,r); doit(p); } inline void push_down(ll p) { if(a[p].f==1)//分情况 { a[L(p)].v=a[L(p)].r-a[L(p)].l+1;//涂颜色，覆盖 a[R(p)].v=a[R(p)].r-a[R(p)].l+1; a[L(p)].f=1; a[R(p)].f=1;//标记下传 a[p].f=0; } else if(a[p].f==-1) { a[L(p)].v=0;//擦去 a[R(p)].v=0; a[L(p)].f=-1;//标记下传 a[R(p)].f=-1; a[p].f=0; } } inline void change(ll p,ll l,ll r,ll x) { if(l<=a[p].l&&r>=a[p].r) { a[p].f=x;//分两种情况，只与覆盖有关 if(x==-1) a[p].v=0; if(x==1) a[p].v=a[p].r-a[p].l+1; return; } push_down(p); ll mid=(a[p].l+a[p].r)>>1; if(l<=mid) change(L(p),l,r,x); if(r>mid) change(R(p),l,r,x); doit(p); } inline ll findout(ll p)//最后找就不要那么麻烦了，直接访问根节点 { //根节点包括1--n push_down(p); return a[p].v; } int main() { n=read();m=read(); build(1,0,n);//建树 for(ll i=1;i<=m;i++) { ll f=read(),x=read(),y=read(); if(f==1) change(1,x,y-1,1);//题目是求线段，而我们操作是维护区间节点 //所以读入的每一个y值都要减一个1； else change(1,x,y-1,-1); } printf("%lld\n",findout(1)); return 0; }
原文链接: https://www.cnblogs.com/wzx-RS-STHN/p/13197738.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/359760
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
