Ural 1019 Line Painting

点击打开链接ural 1019

思路：离散化
分析：
1 这一题的区间的最大值为10^9而n最大为5000，很明显就是利用离散化
2 题目中说了区间[0,10^9]刚开始为白色，而给定重刷的区间的值是大于0小于10^9的，所以我们应该开始就要考虑到0和10^9.
3 然后我们应该注意这题是对线段染色，所以我们应该要注意在处理的时候应该要把这些区间看成点来处理，然后会有两种方法分别是暴力和线段树

代码

线段树

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 10010;
struct Node{
    int left;
    int right;
    int mark;
    char color;
};
Node node[4*MAXN] , tmp[MAXN];
int n , pos;
int num[MAXN];

//二分查找
int search(int x){
    int left , right;
    left = 1 , right = pos-1;
    while(left <= right){
        int mid = (left + right)>>1;
        if(num[mid] == x)
           return mid;
        else if(num[mid] > x)
           right = mid-1;
        else
           left = mid+1;
    }
}

//建立线段树
void buildTree(int left , int right , int pos){
    node[pos].left = left;
    node[pos].right = right;
    node[pos].mark = 0;
    if(left == right)
      return;
    int mid = (left+right)>>1;
    buildTree(left , mid , pos<<1);
    buildTree(mid+1 , right , (pos<<1)+1); 
}

//向下更新
void push_down(int pos){
    if(node[pos].mark != -1){
       node[pos<<1].mark = node[(pos<<1)+1].mark = node[pos].mark;
       node[pos].mark = -1;
    }
}

//更新
void update(int left , int right , int value , int pos){
    if(left <= node[pos].left && right >= node[pos].right){
       node[pos].mark = value;
       return;
    }
    push_down(pos);
    int mid = (node[pos].left + node[pos].right)>>1;
    if(right <= mid)
      update(left , right , value , pos<<1);
    else if(left > mid)
      update(left , right , value , (pos<<1)+1);
    else{
      update(left , mid , value , pos<<1); 
      update(mid+1 , right , value , (pos<<1)+1);
    }
}

//询问
int query(int index , int pos){
    if(node[pos].left == node[pos].right)
       return node[pos].mark;
    push_down(pos);
    int mid = (node[pos].left + node[pos].right)>>1;
    if(index <= mid)
       return query(index , pos<<1);
    else
       return query(index , (pos<<1)+1);
}

int main(){
    while(scanf("%d" , &n) != EOF){
        pos = 1;
        num[pos++] = 0;
        num[pos++] = 1e9;
        for(int i = 0 ; i < n ; i++){
           scanf("%d %d %c" , &tmp[i].left , &tmp[i].right , &tmp[i].color);
           num[pos++] = tmp[i].left;
           num[pos++] = tmp[i].right;
        }
        sort(num+1 , num+pos);
        pos = unique(num+1 , num+pos)-num;
        //离散化
        for(int i = 0 ; i < n ; i++){
           tmp[i].left = search(tmp[i].left);
           tmp[i].right = search(tmp[i].right);
        }
        buildTree(1 , pos-1 , 1);
        //更新
        for(int i = 0 ; i < n ; i++){
           int value = 0;
           if(tmp[i].color == 'b')
              value = 1;
           update(tmp[i].left , tmp[i].right-1 , value , 1);
        }
        //求解最长的白色区间
        int left , right;
        left = right = 0;
        for(int i = 1 ; i < pos-1 ; i++){
           if(!query(i , 1)){
              int j = i+1;
              while(j < pos-1 && !query(j , 1))
                   j++;
              int dis = num[j]-num[i];
              if(dis > right-left){
                 left = num[i];
                 right = num[j];
              }
              i = j;
           }
        }
        printf("%d %d\n" , left , right);
    }
    return 0;
}

暴力

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100010;
struct Node{
    int left;
    int right;
    int mark;
    char color;
};
Node node[MAXN];
int vis[MAXN];
int num[MAXN];
int pos;

//二分查找
int search(int x){
    int left = 1 , right = pos-1;
    while(left <= right){
        int mid = (left+right)>>1; 
        if(num[mid] == x)
          return mid;
        else if(num[mid] > x)
          right = mid-1;
        else
          left = mid+1;
    }
}

int main(){
    int n;
    while(scanf("%d" , &n) != EOF){
        pos = 1;
        num[pos++] = 0;
        num[pos++] = 1e9;
        for(int i = 0 ; i < n ; i++){
            scanf("%d %d %c" , &node[i].left , &node[i].right , &node[i].color);
            num[pos++] = node[i].left;
            num[pos++] = node[i].right;
        }
        sort(num+1 , num+pos);
        pos = unique(num+1 , num+pos)-num;
        for(int i = 0 ; i < n ; i++){
           node[i].left = search(node[i].left);
           node[i].right = search(node[i].right);
        }
        //染色
        memset(vis , 0 , sizeof(vis));
        for(int i = 0 ; i < n ; i++){
            int value = 0;
            if(node[i].color == 'b')
              value = 1;
            for(int j = node[i].left ; j < node[i].right ; j++)
              vis[j] = value;
        }
        int left , right;
        left = right = 0;
        //找最大的连续的白色区间
        for(int i = 1 ; i < pos-1 ; i++){
           if(!vis[i]){
             int j = i+1;
             while(j < pos-1 && !vis[j])
                  j++;
             int dis = num[j]-num[i];
             if(dis > right-left){
                right = num[j];
                left = num[i];
             }
             i = j;
           }
        }
        printf("%d %d\n" , left , right);
    }
    return 0;
}