Line Painting

1019. Line Painting @ Timus Online Judge

题目大意，给你一个线段，每次会在线段上一个区间染色（初始白色，染色黑白），然后最后问你最长的白色线段的两端在哪。

显然，线段长度初始 $10^9$ ，离散化一手，接下来该怎么做？

$5000$ ，直接暴力估计都可以直接搞了，不过这道题目放在数据结构当中应该是想让我们用线段树做，那就老老实实用线段树吧。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 31000
#define NN 61000
using namespace std;
struct node
{
	int lc,rc,co,d;
}tr[NN];int len;
inline void pushlazy(int x,int k){tr[x].co=k;}
inline void updata(int x)
{
	if(tr[tr[x].lc].co==tr[tr[x].rc].co)tr[x].co=tr[tr[x].lc].co;
	else tr[x].co=-1;
}
inline void pushdown(int x)
{
	if(tr[x].co!=-1)
	{
		pushlazy(tr[x].lc,tr[x].co);
		pushlazy(tr[x].rc,tr[x].co);
	}
}
int be[N];
void bt(int l,int r)
{
	int x=++len;tr[x].co=0;
	if(l+1<r)
	{
		int mid=(l+r)>>1;
		tr[x].lc=len+1;bt(l,mid);
		tr[x].rc=len+1;bt(mid,r);
	}
}
void change(int x,int l,int r,int ll,int rr,int k)
{
	if(tr[x].co==k)return ;
	if(l==ll && r==rr){pushlazy(x,k);return ;}
	pushdown(x);
	int mid=(l+r)>>1;
	if(rr<=mid)change(tr[x].lc,l,mid,ll,rr,k);
	else if(mid<=ll)change(tr[x].rc,mid,r,ll,rr,k);
	else change(tr[x].lc,l,mid,ll,mid,k),change(tr[x].rc,mid,r,mid,rr,k);
	updata(x);
}
int ansl,ansr,suml,sumr;
inline void gen()
{
	if(be[sumr]-be[suml]>be[ansr]-be[ansl])ansl=suml,ansr=sumr;
}
void Query(int x,int l,int r)
{
	if(tr[x].co==1)
	{
		gen();suml=sumr=r;
		return ;
	}
	else if(tr[x].co==0)
	{
		sumr=r;
		return ;
	}
	int mid=(l+r)>>1;
	Query(tr[x].lc,l,mid);Query(tr[x].rc,mid,r);
}
int ll[N],rr[N],type[N],m;
struct Lisan
{
	int *x,val;
}li[N];int top,n;
inline bool cmp(Lisan x,Lisan y){return x.val<y.val;}
int main()
{
	scanf("%d",&m);m++;
	ll[1]=0;rr[1]=1e9;type[1]=0;
	li[++top].x=&ll[1];li[top].val=ll[1];
	li[++top].x=&rr[1];li[top].val=rr[1];
	for(int i=2;i<=m;i++)
	{
		char st[10];scanf("%d%d%s",&ll[i],&rr[i],st+1);
		if(st[1]=='b')type[i]=1;
		li[++top].x=&ll[i];li[top].val=ll[i];
		li[++top].x=&rr[i];li[top].val=rr[i];
	}
	sort(li+1,li+top+1,cmp);
	n=*li[1].x=1;be[1]=li[1].val;
	for(int i=2;i<=top;i++)
	{
		if(li[i].val!=li[i-1].val)n++,be[n]=li[i].val;
		*li[i].x=n;
	}
	bt(1,n);
	for(int i=2;i<=m;i++)change(1,1,n,ll[i],rr[i],type[i]);
	Query(1,1,n);
	gen();
	printf("%d %d\n",be[ansl],be[ansr]);
	return 0;
}

总结一下建立在线段区间上的线段树应该怎么写：

  1. 线段树的端点直接维护的便是一段区间，区间长度为 $1$ 的点是叶子节点。
  2. 强行将线段上一个个长度为 $1$ 的区间看成点，然后像普通数组一样维护，至于点的编号可以采取左（右）端点的编号，或者用其余方法赋予编号，反正方法很多，看个人喜好，我个人喜欢直接采取左端点编号，简单好想好思考。

当然，我个人推荐第一种。为什么，因为第一种离散化考虑起来比较方便，第二种就比较麻烦了。