ural 1019. Line Painting 线段树离散化

题目链接:

http://acm.timus.ru/problem.aspx?space=1&num=1019

题意:

初始0~1e9都染成白色，[l,r]染成w/b, 是开区间。
样例：
4
1 999999997 b
40 300 w
300 634 w
43 47 b
输出 47 634

题解:

类比上一篇博客，不同的是开区间
还是那组样例
2
0 3 b
4 999999999 b
输出 3 4

所以不用将r延伸一个单位
注意边界

数字很大，所以采用离散化。

代码:

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 #define MS(a) memset(a,0,sizeof(a))
  5 #define MP make_pair
  6 #define PB push_back
  7 const int INF = 0x3f3f3f3f;
  8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  9 inline ll read(){
 10     ll x=0,f=1;char ch=getchar();
 11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 13     return x*f;
 14 }
 15 //////////////////////////////////////////////////////////////////////////
 16 const int maxn = 20010+10;
 17 
 18 int x[maxn],y[maxn],c[maxn],tmp[2*maxn],vis[maxn];
 19 int cnt;
 20 char ch;
 21 
 22 struct node{
 23     int l,r,col,lazy;
 24 }t[maxn<<2];
 25 
 26 void build(int rt,int l,int r){
 27     t[rt].l=l,t[rt].r=r,t[rt].col=1,t[rt].lazy=-1;
 28     if(l == r-1) return ;
 29     int mid = (l+r)/2;
 30     build(rt<<1,l,mid);
 31     build(rt<<1|1,mid,r);
 32 }
 33 
 34 void pushdown(int rt){
 35     if(t[rt].lazy != -1){
 36         t[rt<<1].lazy = t[rt<<1|1].lazy = 1;
 37         t[rt].lazy = -1;
 38         t[rt<<1].col = t[rt<<1|1].col = t[rt].col;
 39         t[rt].col = -1;
 40     }
 41 }
 42 
 43 void update(int rt,int l,int r,int col){
 44     int L = t[rt].l, R = t[rt].r;
 45     if(l<=L && R<=r){
 46         t[rt].col = col;
 47         t[rt].lazy = 1;
 48         return ;
 49     }
 50     pushdown(rt);
 51     int mid = (L+R)/2;
 52     if( l >= mid )  
 53         update(rt<<1|1,l,r,col);
 54     else  
 55         if( r <= mid )  
 56             update(rt<<1,l,r,col); 
 57         else  
 58         {  
 59             update(rt<<1,l,mid,col);
 60             update(rt<<1|1,mid,r,col);
 61         }  
 62 }
 63 
 64 void query(int rt){
 65     int L = t[rt].l, R = t[rt].r;
 66     if(t[rt].lazy == 1){
 67         for(int i=L; i<R; i++)
 68             vis[i] = t[rt].col;
 69         return ;
 70     }
 71     if(L == R) return ;
 72     pushdown(rt);
 73     query(rt<<1);
 74     query(rt<<1|1);
 75 }
 76 
 77 int main(){
 78     int n=read();
 79     x[0] = 0, y[0] = 1e9, c[0] = 1;
 80     tmp[cnt++]=x[0],tmp[cnt++]=y[0];
 81     for(int i=1; i<=n; i++){
 82         scanf("%d%d %c",&x[i],&y[i],&ch);
 83         tmp[cnt++] = x[i];
 84         tmp[cnt++] = y[i];
 85         if(ch == 'w') c[i] = 1;
 86     }
 87     sort(tmp,tmp+cnt);
 88     cnt = unique(tmp,tmp+cnt)-tmp;
 89 
 90     build(1,0,cnt);
 91 
 92     for(int i=0; i<=n; i++){
 93         int p1,p2;
 94         p1 = lower_bound(tmp,tmp+cnt,x[i])-tmp;
 95         p2 = lower_bound(tmp,tmp+cnt,y[i])-tmp;
 96         update(1,p1,p2,c[i]);
 97     }   
 98 
 99 
100     memset(vis,1,sizeof(vis));
101     query(1);
102 
103     vis[cnt] = 0;
104     tmp[cnt] = 1e9;
105     int s=0,e=0,ts,te;
106     for(int i=0; i<cnt; i++){
107         int color=vis[i],j=i;
108         ts = tmp[i];  
109         while(color==1 && vis[j]==1 && j<=cnt) ++j;
110         te = tmp[j];
111         if(te-ts > e-s){
112             s=ts,e=te;
113         }
114         i = j;
115     }  
116     printf("%d %d
",s,e);
117 
118     return 0;
119 }

ural 1019. Line Painting 线段树 离散化

题目链接:

题意:

题解:

代码:

ural 1019. Line Painting 线段树离散化