程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2528 Mayor&#39;s posters（線段樹區間修改+離散化）

POJ 2528 Mayor&#39;s posters（線段樹區間修改+離散化）

編輯：C++入門知識

POJ 2528 Mayor's posters（線段樹區間修改+離散化）

題意：在牆上貼海報,海報可以互相覆蓋,問最後可以看見幾張海報。

該題是線段樹區間修改+離散化的應用。

不難想到，每次對一個最長10^7的線段進行線段樹的區間修改，最後統計。

線段樹的復雜度是log10^7，應該不會超時，但是會超內存。所以想到要離散化，將區間端點值有映射成一個盡量小的值。

但是該題求的是覆蓋情況，如果按照單純的點對點的離散化，那樣會出現錯誤答案。

例如：依次貼[1,10], [1,3], [5,10] ，離散化後1->1, 3->2, 5->3, 10->4

那麼第一次讓離散後的區間[1,4]變成1，第二次讓[1,2]變成2，第三次讓[3,4]變成3，那麼最終答案成了2，其實是3。

問題之所在就在於：小的區間不會覆蓋大區間的所有部分。解決方法就是在相鄰區間端點大於1時再添加一個二者中間的數當作“空白”區域。

不會離散化的先學學離散化吧，一般用二分來維護比較簡單。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 11111;
int T,n,ans,setv[maxn<<4],X[maxn<<3];
bool vis[maxn];
struct node {
    int l, r;
    node(int ll=0, int rr=0):l(ll), r(rr) {}
    bool operator < (const node& rhs) const {
        return l < rhs.l || (l == rhs.l && r < rhs.r);
    }
}a[maxn];
void pushdown(int o) {
    if(setv[o]) {
        setv[o<<1] = setv[o<<1|1] = setv[o];
        setv[o] = 0;
    }
}
void update(int L, int R, int v, int l, int r, int o) {
    int m = (l + r) >> 1;
    if(L <= l && r <= R) {
        setv[o] = v; return ;
    }
    pushdown(o);
    if(L <= m) update(L, R, v, l, m, o<<1);
    if(m < R) update(L, R, v, m+1, r, o<<1|1);
}
void query(int l, int r, int o) {
    int m = (l + r) >> 1;
    if(setv[o]) {
        if(!vis[setv[o]]) {
            vis[setv[o]] = true;
            ++ans;
        }
        return ;
    }
    if(l == r) return ;
    query(l, m, o<<1);
    query(m+1, r, o<<1|1);
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        int cnt = 0;
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&a[i].l,&a[i].r);
            X[cnt++] = a[i].l; X[cnt++] = a[i].r;
        }
        sort(X, X+cnt);
        cnt = unique(X, X+cnt) - X;
        int m = cnt;
        for(int i=1;i X[i-1]+1) X[m++] = X[i] + 1;
        }
        sort(X, X + m);
        memset(vis, false, (n+1)*sizeof(vis[0]));
        memset(setv, 0, sizeof(setv));
        for(int i=1;i<=n;i++) {
            int lc = lower_bound(X, X + m, a[i].l) - X + 1;
            int rc = lower_bound(X, X + m, a[i].r) - X + 1;
            update(lc, rc, i, 1, m, 1);
        }
        ans = 0;
        query(1, m, 1);
        printf("%d\n",ans);
    }
    return 0;
}