木条染色_题解

题目

描述

小明是一个非常浪漫的画家,他喜欢画各种奇奇怪怪的画,虽然没人理解他画的究竟是什么东西。 有一天,他突发奇想,对于一根木条,他每次从木条中选取一个区间[l,r]进行染色,经过多次染色后,他想知道在[a,b]区间中有几个未被染色的子区间? 可惜小明虽然画画非常厉害,但是并不擅长解决这类问题,于是,他拿着这根木条来找你,希望你能够给他帮助。 假设木条无限长,所有查询都在木条长度范围内,未被染色的子区间是指,木条上染过色的区间的间断部分。

输入

第一行一个整数T,代表数据组数。 对于每组数据,第一行给出两个整数n,q,分别代表染色的区间个数,以及查询个数。 之后n行,每行两个整数l,r,表示将l到r的区间进行染色,包含l,r两个节点。 之后q行,每行两个整数a,b,表示询问a到b总共有多少未被染色的子区间。 两组数据之间用一个空行隔开。 T < 20
n < 10000
q < 100000
0 < = l < r < 1000000
0 < = a < = b < 1000000

输出

对于每次询问,输出一个整数,表示查询结果。 每组数据之后,请输出一个空行。

提示

对于第一组数据,[0,1),(2,3),(4,+ )是未染色的子区间,因此查询[1,3]可以找到(2,3)这个子区间,而对于[3,4]不能找到,对于[5,5]可以找到[5,5]。
对于第二组数据,[0,1)和(8,+ )是未染色的子区间,因此对于[0,5]只有子区间[0,1),对于查询[0,9],有子区间[0,1)和(8,9],对于查询[9,9],有[9,9]这个子区间。


思路

使用标记法,首先就是区分染色的和未染色的区间,通过染色起点++染色终点–后每一个点的标记值加上前一个点的标记值形成新的标记值,这样标记为0的就是空区间中的点,非0的就是非空区间中的点。然后通过大区间标号(即一个空区间和他右边的一个非空区间进行合并形成大区间然后给每个区间从小到大标号),这样两个点之间的空区间标记数之差就是两点间的空区间数了。注意处理最前面的空区间和最后面的空区间,最前面的空区间是直接判断点在不在空区间中,如果在的话答案++。为大区间标号的时候,向染色设计的最大范围后面多标一个,以应对查询范围在染色范围右端的情况。


代码

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
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstring>
#include<cmath>
using namespace std;
#define SIZE 1000005
#define mm(a,b) memset(a,b,sizeof(a))
int a[SIZE],b[SIZE],anse[SIZE/10+5];
void solve()
{
int n,q,i,d,t,ml=0;
mm(a,0);
mm(b,0);
scanf("%d%d",&n,&q);
//cin>>n>>q;
for(i=0;i<n;i++)
{
scanf("%d%d",&d,&t);
//cin>>d>>t;
a[d]++;
a[t]--;
ml=max(ml,t);
}
int num=1,ans;
b[0]=1;
for(i=1;i<=ml+1;i++) //+1确保从空区间开始空区间结束
{
a[i]+=a[i-1];
b[i]=num;
if(a[i]==0&&a[i-1]!=0)num++; //下一个在空区间内的点归入下一个大区间
}
for(i=0;i<q;i++)
{
scanf("%d%d",&d,&t);
//cin>>d>>t;
if(t>ml)t=ml+1;
if(d>ml)d=ml+1;
ans=b[t]-b[d];
if((d>0&&a[d]==0&&a[d-1]==0)||(d==0&&a[d]==0)) //对开始为空区间的情况进行讨论
ans++;
anse[i]=ans;
//cout<<ans<<endl;
}
for(i=0;i<q;i++)
printf("%d\n",anse[i]);
//cout<<anse[i]<<endl;
printf("\n");
}
int main()
{
int t;
scanf("%d",&t);
//cin>>t;
while(t--)solve();
return 0;
}