1191 数轴染色

1191 数轴染色

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

在一条数轴上有N个点,分别是1~N。一开始所有的点都被染成黑色。接着 我们进行M次操作,第i次操作将[Li,Ri]这些点染成白色。请输出每个操作执行后 剩余黑色点的个数。

输入描述 Input Description

输入一行为N和M。下面M行每行两个数Li、Ri

输出描述 Output Description

输出M行,为每次操作后剩余黑色点的个数。

样例输入 Sample Input

10 3 3 3 5 7 2 8

样例输出 Sample Output

9 6 3

数据范围及提示 Data Size & Hint

数据限制 对30%的数据有1<=N<=2000,1<=M<=2000 对100%数据有1<=Li<=Ri<=N<=200000,1<=M<=200000

分类标签 Tags 点此展开

裸的线段树。

一定要记住如果整个区间都是0了一定要return

啊啊啊啊啊啊啊啊啊啊

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=200001;
 7 void read(int & n)
 8 {
 9     char c='+';int x=0;int flag=0;
10     while(c<'0'||c>'9')
11     {    if(c=='-')    flag=1;    c=getchar();    }
12     while(c>='0'&&c<='9')
13     {    x=x*10+(c-48);    c=getchar();}
14     flag==1?n=-x:n=x;
15 }
16 int n,m;
17 struct node
18 {
19     int l,r,w;
20 }tree[MAXN*4];
21 void update(int k)
22 {
23     tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
24 }
25 void build_tree(int ll,int rr,int k)
26 {
27     
28     tree[k].l=ll;tree[k].r=rr;
29     if(ll==rr)
30     {
31         tree[k].w=1;
32         return ;
33     }    
34     int mid=(ll+rr)>>1;
35     build_tree(ll,mid,k<<1);
36     build_tree(mid+1,rr,k<<1|1);
37     update(k);
38 }
39 void interval_change(int k,int ql,int qr)
40 {
41     if(tree[k].w==0)
42     return ;
43     if(ql<=tree[k].l&&qr>=tree[k].r)
44     {
45         tree[k].w=0;
46         return ;
47     }
48     int mid=(tree[k].l+tree[k].r)>>1;
49     if(ql<=mid)
50         interval_change(k<<1,ql,qr);
51     if(qr>mid)
52         interval_change(k<<1|1,ql,qr);
53     update(k);
54 }
55 int main()
56 {
57     read(n);read(m);
58     build_tree(1,n,1);
59     for(int i=1;i<=m;i++)
60     {
61         int x,y;
62         read(x);read(y);
63         interval_change(1,x,y);
64         printf("%d\n",tree[1].w);
65     }
66     return 0;
67 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【编程基础】C语言循环语句解析

循环语句是一种很重要的结构,这种结构的特点就是在某种条件下,会重复循环执行某一段代码,直到条件不成立为止。这里的条件称为循环条件,重复执行的那段代码称为循环体。...

38750
来自专栏算法channel

Numpy|需要信手拈来的功能

这是一篇Numpy中经常使用的API的不完全总结,欢迎补充和指导。 01 类型转化 凡是使用Numpy的小伙伴,无不遇到类型转化这个问题,并且经常需要通过调试...

33630
来自专栏技术沉淀

Python: 函数式编程

17440
来自专栏Coco的专栏

Javascript正则构造函数与正则表达字面量&&常用正则表达式

18640
来自专栏cs

爬虫前的准备

31960
来自专栏chenjx85的技术专栏

leetcode-832-Flipping an Image

40470
来自专栏数据结构与算法

3110 二叉堆练习3

3110 二叉堆练习3 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 给定N...

29850
来自专栏数据结构与算法

06:整数奇偶排序

06:整数奇偶排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定10个整数的序列,要求对其重新排序。排序要求: 1...

40460
来自专栏赵俊的Java专栏

搜索插入位置

17410
来自专栏编程

Python数据处理(2)-NumPy的ndarray

NumPy是Python中众多科学软件包的基础。它提供了一个特殊的数据类型ndarray,其在向量计算上做了优化。这个对象是科学数值计算中大多数算法的核心。下面...

21950

扫码关注云+社区

领取腾讯云代金券