HDU-1199 && ZOJ-2301---Color the Ball 区间染色-离散化非线段树做法

Color the Ball

Time limit 2000 ms
Memory limit 65536 kB

题目链接http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2301
（这是ZOJ的链接–数据笔HDU的加强了。。）

There are infinite balls in a line (numbered 1 2 3 …), and initially all of them are paint black. Now Jim use a brush paint the balls, every time give two integers a b and follow by a char ‘w’ or ‘b’, ‘w’ denotes the ball from a to b are painted white, ‘b’ denotes that be painted black. You are ask to find the longest white ball sequence.

Input

First line is an integer N (<=2000), the times Jim paint, next N line contain a b c, c can be ‘w’ and ‘b’.
There are multiple cases, process to the end of file.

Output

Two integers the left end of the longest white ball sequence and the right end of longest white ball sequence (If more than one output the small number one). All the input are less than 2^31-1. If no such sequence exists, output “Oh, my god”.

Sample Input

3
1 4 w
8 11 w
3 5 b

Sample Output

8 11

---

题目大意：w是给区间染白的意思，b是给区间染黑的意思，我们要求的是最长的白色区间的最小头尾标号。

网上的代码基本上都是离散化+线段树过的，但实际上对于本题的规模可以直接暴力模拟染色，当然，也需要离散化的，我之前有写过一篇离散化+线段树的–海报覆盖：
https://blog.csdn.net/qq_43906000/article/details/89179991
不过海报覆盖的数据是错误的，按照标准的做法反而WA。。。我们离散化区间覆盖的时候需要将每个分隔开的区间仍然保持分隔状态：

sort(a+1,a+p);
int tot=p;
for (int i=2; i<p; i++) {
	if (a[i]-a[i-1]>1) a[tot++]=a[i-1]+1;
	if (a[i]-a[i-1]>2) a[tot++]=a[i]-1;
}

即对于每个数的前后判断是否该加上一个隔板。
然后就是一个简单的模拟了。。。
代码如下：

#include <bits/stdc++.h>
using namespace std;
const int mac=4e3+10;
int a[mac*4],col[mac*2],lish[mac*4],cnt,l[mac],r[mac],mp[mac*4];
#define cls(a) memset(a,0,sizeof(a))
int find(int x)
{
	int l=0,r=cnt-1,mid;
	while (l<=r){
		mid=(l+r)>>1;
		if (lish[mid]==x) return mid;
		if (lish[mid]<x) l=mid+1;
		else r=mid-1;
	}
}
int main()
{
	int n,p=1;
	char ch[10];
	while (~scanf ("%d",&n)){
		cls(a);cls(col);
        cls(l);cls(r);
        cls(lish);cls(mp);       
        p = 1;cnt = 0;      
	for (int i=1; i<=n; i++){	
		scanf ("%d%d%s",&l[i],&r[i],ch);
		if (ch[0]=='w') col[i]=1;
		a[p++]=l[i],a[p++]=r[i];
	}
	sort(a+1,a+p);
	int tot=p;
	for (int i=2; i<p; i++){
		if (a[i]-a[i-1]>1) a[tot++]=a[i-1]+1;
		if (a[i]-a[i-1]>2) a[tot++]=a[i]-1;
	}
	p=tot;
	sort(a+1,a+p);
	int o=-1; cnt=1;
	for (int i=1; i<p; i++){
		if (o!=a[i]) {
			o=a[i]; lish[cnt++]=a[i];
		}
	}
	for (int i=1; i<=n; i++){
		int la=find(l[i]),rb=find(r[i]);
		if (col[i])
		   for (int j=la; j<=rb; j++) 	
		       mp[j]=1;	   
		else 
		   for (int j=la; j<=rb; j++) 	
		       mp[j]=0;	  
	} 
	int ks=1;
	while (!mp[ks] && ks<cnt) ks++;
	if (ks>=cnt) {
		printf ("Oh, my god\n");
		return 0;
	}
	int ll=ks,rr,len=0,su=0;
	for (int i=ks; i<cnt; i++){
		if (mp[i]!=1){
			int len2=lish[i-1]-lish[i-su]+1;
			if (len2>len) {
				ll=lish[i-su];rr=lish[i-1];
				len=len2;
			}
			su=0;
		}
		else su++;
	}
	if (mp[cnt-1]){
		int len2=lish[cnt-1]-lish[cnt-su]+1;
			if (len2>len) {
				ll=lish[cnt-su];rr=lish[cnt-1];
				len=len2;
			}
	}
	printf ("%d %d\n",ll,rr);}
	return 0;
}