线段树离散化+区间修改

POJ - 2528 - Mayor's posters

先说结论,这题数据太弱

这题直接按照1,2,3...离散化有问题,例如数据

1
3
2 4
1 2
4 5

应该输出3,但是直接错误的离散化导致输出为2

对于相邻两个点,如果距离差大于1,则额外增加一个点,即可解决问题

这一题的数据范围为1e7,但最多只有2e5种不同的端点值,可以离散化到2e5<<2去

但是本题离散化处理仍是有必要的,离散化处理可以大大降低时间复杂度(数组越长,update,query的递归层数越多)

另外,本题只需要维护一个lazy标记数字即可,没必要额外开一个tree数组,最终查询所有长度为1的区间(即[i,i])对应的不同的lazy值个数即为最终答案.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <cstdlib>
#include <iostream>
using namespace std;
#define N 200000+2
#define MAX(a,b) (a>b?a:b)
int lazy[N<<2];
set<int> ans_set;
void push_down(int left,int right,int root){
    if(lazy[root]){
        int left_root = root<<1;
        int right_root = root<<1|1;
        lazy[left_root] = lazy[root];
        lazy[right_root] = lazy[root];
        lazy[root] = 0;
    }
}
void update(int left,int right,int root,int update_left,int update_right,int new_val){
    if(update_left <= left && update_right >= right){
        lazy[root] = new_val;
    }else{
        push_down(left,right,root);
        int mid = (left+right)>>1;
        int left_root = root<<1;
        int right_root = root<<1|1;
        if(update_left <= mid){
            update(left,mid,left_root,update_left,update_right,new_val);
        }
        if(update_right > mid){
            update(mid+1,right,right_root,update_left,update_right,new_val);
        }
    }
}

void query_all(int left,int right,int root){
    if(left == right){
        if(lazy[root])
            ans_set.insert(lazy[root]);
        return; // 最后只需要看lazy个数
    }else{
        push_down(left,right,root);
        int mid = (left+right)>>1;
        query_all(left,mid,root<<1);
        query_all(mid+1,right,root<<1|1);
    }
}
typedef pair<int,int> pii;
int binarySearch(int head,int tail,int val,const vector<int>& vec){
    int ans = 0;
    while(head <= tail){
        int mid = (head+tail)>>1;
        if(vec[mid] > val){
            tail = mid - 1;
        }else if(vec[mid] < val){
            head = mid + 1;
        }else{
            ans = mid;
            break;
        }
    }
    return ans;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int q;
        int l,r;
        int maxn = 0;
        scanf("%d",&q);
        vector<pii> vec;
        set<int> st;
        for(int i = 0; i < q; i++){
            scanf("%d%d",&l,&r);
            vec.push_back(make_pair(l,r));
            st.insert(l);
            st.insert(r);
        }

        vector<int> ord;
        for(set<int> :: iterator it = st.begin(); it != st.end(); it++){
            ord.push_back(*it);
        }
        int tp = ord.size();
        for(int i = 1; i < tp; i++){
            if(ord[i] - ord[i-1] > 1){
                ord.push_back(ord[i-1]+1);
            }
        }
        sort(ord.begin(),ord.end());

        int g = ord.size();
        
        for(int i = 0; i < q; i++){
            vec[i].first = binarySearch(0,g-1,vec[i].first,ord) + 1;
            vec[i].second = binarySearch(0,g-1,vec[i].second,ord) + 1;
            maxn = MAX(maxn,vec[i].second);
        }

        for(int i = 0; i < q; i++){
            update(1,maxn,1,vec[i].first,vec[i].second,i+1);
        }

        query_all(1,maxn,1);
        printf("%d
",ans_set.size());
        ans_set.clear();
    }
    system("pause");
    return 0;
}