本文主要是介绍Ural 1019 A Line painting(线段树，成段更新离散化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：
http://acm.timus.ru/problem.aspx?space=1&num=1019
题目大意：
一条线段上有点0～10^9. 初始时全部都是白色。 然后会有一些操作:把【a b】区间染成白色，或者把【a,b】区间染成黑色。
最后，求最长的一段白色。
分析与总结：
线段树成段更新染色。当然，由于数据量小，也可以直接暴力。
1. 在离散化问题上卡了我很久，WA了很多次，主要是因为这个线段是的点是0～10^9，0和10^9这两点是必须要添加上去的。
2. 在最后扫描连续的白色区间时，要注意结尾边界
代码：
1. 线段树
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define STOP puts("Stop here~");
#define FF(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,s,t) for(int i=(s); i<(t); ++i)
#define mid ((left+right)>>1)
#define lson rt<<1, left, m
#define rson rt<<1|1, m+1, right
const int MAXN = 100000;int col[MAXN],arr[MAXN<<1];
int A[MAXN],B[MAXN];
char C[MAXN];
int vis[MAXN];void update(int rt,int left,int right,int l,int r,int data){if(l<=left && right<=r){col[rt] = data;return;}if(col[rt] == data) return;if(col[rt] != -1){col[rt<<1] = col[rt<<1|1] = col[rt];col[rt] = -1;}int m = mid;if(l <= m) update(lson,l,r,data);if(r > m) update(rson,l,r,data);
}
void query(int rt,int left,int right){if(col[rt] >= 0){FOR(i,left,right+1) vis[i]=col[rt];return;}if(left!=right && col[rt]==-1){int m = mid;query(lson);query(rson);}
}int binary(int left,int right,int x){while(left < right){int m = (left+right)>>1;if(arr[m] >= x) right=m;else left=m+1;}return left;
}
int main(){int n; char ch[3];while(~scanf("%d",&n)){int kk=0;arr[kk++] = 0;arr[kk++] = 1e9;FF(i,n){scanf("%d%d%s",&A[i],&B[i],ch);C[i] = ch[0];arr[kk++]=A[i]; arr[kk++]=B[i];}sort(arr,arr+kk);int end = kk;kk = 1;FOR(i,1,end){if(arr[i]!=arr[i-1])arr[kk++]=arr[i];}end = kk;FOR(i,1,end){if(arr[i]>arr[i-1]+1) arr[kk++]=arr[i-1]+1;}sort(arr,arr+kk);memset(col,-1,sizeof(col));col[1] = 0;FF(i,n){int a=binary(0,kk,A[i]);int b=binary(0,kk,B[i]);if(C[i]=='b'){update(1,1,kk-1,a+1,b,1);}else{update(1,1,kk-1,a+1,b,0);}}int i=1,maxx=-1,ans_x=0,ans_y=kk-1;query(1,1,kk-1);memcpy(col,vis,sizeof(vis));while(i<kk){if(col[i]==0){int j = i+1;while(col[j]==0 && j<kk)++j;--j;int ll=arr[j]-arr[i-1];if(ll > maxx){maxx=ll;ans_x=i-1; ans_y=j;}i = j;}++i;}printf("%d %d\n",arr[ans_x], arr[ans_y]);}return 0;
}
2. 暴力
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define STOP puts("Stop here~");
#define FF(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,s,t) for(int i=(s); i<(t); ++i)
const int MAXN = 100000;int col[MAXN],arr[MAXN<<1];
int A[MAXN],B[MAXN];
char C[MAXN];int binary(int left,int right,int x){while(left < right){int m = (left+right)>>1;if(arr[m] >= x) right=m;else left=m+1;}return left;
}
int main(){int n; char ch[3];while(~scanf("%d",&n)){int kk=0;arr[kk++] = 0;arr[kk++] = 1e9;FF(i,n){scanf("%d%d%s",&A[i],&B[i],ch);C[i] = ch[0];arr[kk++]=A[i]; arr[kk++]=B[i];}sort(arr,arr+kk);int end = kk;kk = 1;FOR(i,1,end){if(arr[i]!=arr[i-1])arr[kk++]=arr[i];}end = kk;FOR(i,1,end){if(arr[i]>arr[i-1]+1) arr[kk++]=arr[i-1]+1;}sort(arr,arr+kk);memset(col,0,sizeof(col));FF(i,n){int a=binary(0,kk,A[i]);int b=binary(0,kk,B[i]);if(C[i]=='b'){FOR(i,a+1,b+1)col[i]=1;}else{FOR(i,a+1,b+1)col[i]=0;}}int i=1,maxx=-1,ans_x=0,ans_y=kk-1;while(i<kk){if(col[i]==0){int j = i+1;while(col[j]==0 && j<kk)++j;--j;int ll=arr[j]-arr[i-1];if(ll > maxx){maxx=ll;ans_x=i-1; ans_y=j;}i = j;}++i;}printf("%d %d\n",arr[ans_x], arr[ans_y]);}return 0;
}
—— 生命的意义，在于赋予它意义士。
原创 http://blog.csdn.net/shuangde800 ， By D_Double (转载请标明)
这篇关于Ural 1019 A Line painting(线段树，成段更新离散化)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
