1019.Line Painting(线段树离散化）

离散化都忘记怎么写了注意两个端点离散化后用线段树更新区间混色为-1 黑为2 白为1 因为N不大最后直接循环标记这一段的颜色查找
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 using namespace std;
  7 #define N 100010
  8 #define LL long long
  9 struct node
 10 {
 11     int d,id;
 12     char c;
 13 }li[N<<1];
 14 int q[N][3],pp[N];
 15 int s[N<<2],cnt[N],cc[N];
 16 void build(int l,int r,int w)
 17 {
 18     s[w] = 1;
 19     if(l==r-1)
 20     {
 21         return ;
 22     }
 23     int m = (l+r)>>1;
 24     build(l,m,w<<1);
 25     build(m,r,w<<1|1);
 26 }
 27 void update(int a,int b,int d,int l,int r,int w)
 28 {
 29     if(a<=l&&b>=r)
 30     {
 31         s[w] = d;
 32         return ;
 33     }
 34     if(l==r-1)
 35     return ;
 36     if(s[w]>0&&s[w]!=d)
 37     {
 38         s[w<<1] = s[w<<1|1] = s[w];
 39         s[w] = -1;
 40     }
 41     int m = (l+r)>>1;
 42     if(a<=m)
 43     update(a,b,d,l,m,w<<1);
 44     if(b>m)
 45     update(a,b,d,m,r,w<<1|1);
 46 }
 47 void query(int l,int r,int w)
 48 {
 49     int i;
 50     if(s[w]>0)
 51     {
 52         for(i = l ; i < r; i++)
 53         cnt[i] = s[w];
 54         return ;
 55     }
 56     if(l==r-1)
 57     return ;
 58     int m = (l+r)>>1;
 59     query(l,m,w<<1);
 60     query(m,r,w<<1|1);
 61 }
 62 bool cmp(node a,node b)
 63 {
 64     return a.d<b.d;
 65 }
 66 int main()
 67 {
 68     int i,n;
 69     char c[10];
 70     scanf("%d",&n);
 71     for(i = 0 ; i < n ; i++)
 72     {
 73         scanf("%d%d%s",&q[i][0],&q[i][1],c);
 74         if(c[0]=='b')
 75         cc[i+1] = 2;
 76         else
 77         cc[i+1] = 1;
 78         li[2*i].d = q[i][0];
 79         li[2*i].id = -(i+1);
 80         li[2*i+1].d = q[i][1];
 81         li[2*i+1].id = i+1;
 82     }
 83     sort(li,li+2*n,cmp);
 84     int tt = li[0].d,g=1;
 85     for(i = 0 ; i < 2*n ; i++)
 86     {
 87         if(li[i].d!=tt)
 88         {
 89             g++;
 90             tt = li[i].d;
 91         }
 92         if(li[i].id<0)
 93         {
 94             q[-li[i].id][0] = g;
 95             pp[g] = li[i].d;
 96         }
 97         else
 98         {
 99             q[li[i].id][1] = g;
100             pp[g] = li[i].d;
101         }
102     }
103     build(0,g,1);
104     for(i = 0; i <= g ; i++)
105     cnt[i] = 1;
106     for(i = 1 ; i <= n ; i++)
107     {
108         update(q[i][0],q[i][1],cc[i],0,g,1);
109     }
110     query(0,g,1);
111     int maxz=0,ss,ee,ts,te;
112     cnt[0] = 1;
113     cnt[g+1] = 1;
114     pp[g+1] = 1000000000;
115     for(i = 0 ; i <= g ; i++)
116     {
117         if(cnt[i]!=1)
118         continue;
119         ss = pp[i];
120         while(cnt[i]==1&&i<=g)
121         i++;
122         ee = pp[i];
123         if(ee-ss+1>maxz)
124         {
125             ts = ss;
126             te = ee;
127             maxz = ee-ss+1;
128         }
129     }
130     printf("%d %d
",ts,te);
131     return 0;
132 }
View Code
1019.Line Painting(线段树 离散化）

1019.Line Painting(线段树离散化）
