POJ - 2528 Mayor's posters （离散化+线段树区间修改）

时间：2024-04-12 00:03:53

https://cn.vjudge.net/problem/POJ-2528

题意

给定一些海报，可能相互重叠，告诉你每个海报的宽度（高度都一样的）和先后叠放顺序，问没有被完全盖住的有多少张？

分析

海报最多10000张，但是墙有10000000块瓷砖长，海报不会落在瓷砖中间。

如果直接建树，就算不TLE,也会MLE。即单位区间长度太多。

其实10000张海报，有20000个点，最多有19999个区间。对各个区间编号，就是离散化。然后建树。

可以直接进行区间修改，最后再统计。

这里采用比较巧妙的方法，倒着来统计，每次看这个将覆盖的区间是否已经完全被覆盖了。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <stack>

#include <set>

#include <bitset>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define ms(a, b) memset(a, b, sizeof(a))

#define pb push_back

#define mp make_pair

#define pii pair<int, int>

#define eps 0.0000000001

#define IOS ios::sync_with_stdio(0);cin.tie(0);

#define random(a, b) rand()*rand()%(b-a+1)+a

#define pi acos(-1)

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int inf = 0x3f3f3f3f;

const int maxn =  + ;

const int maxm =  + ;

const int mod = ;

pii poster[maxn];

int x[maxn<<];

int Hash[];

struct ND{

    int l,r;

    bool covered;

}tree[maxn<<];

void build(int rt,int l,int r){

    tree[rt].l=l;

    tree[rt].r=r;

    tree[rt].covered=false;

    if(l==r) return;

    int mid = (l+r)>>;

    build(rt<<,l,mid);

    build(rt<<|,mid+,r);

}

void pushup(int rt){

    tree[rt].covered=tree[rt<<].covered&tree[rt<<|].covered;

}

bool update(int rt,double l,double r){

    if(tree[rt].covered) return false;

    if(l<=tree[rt].l&&r>=tree[rt].r) return tree[rt].covered=true;

    bool res;

    if(tree[rt<<].r>=r) res=update(rt<<,l,r);

    else if(l>=tree[rt<<|].l) res=update(rt<<|,l,r);

    else{

        bool b1=update(rt<<,l,tree[rt<<].r);

        bool b2=update(rt<<|,tree[rt<<|].l,r);

        res=b1||b2;

    }

    pushup(rt);

    return res;

}

int n;

int main() {

#ifdef LOCAL

    freopen("in.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

#endif

    int T,cas=;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        int cnt=;

        for(int i=;i<n;i++){

            scanf("%d%d",&poster[i].first,&poster[i].second);

            x[cnt++]=poster[i].first;

            x[cnt++]=poster[i].second;

        }

        sort(x,x+cnt);

        cnt=unique(x,x+cnt)-x;

        build(,,cnt-);

        for(int i=;i<cnt;i++) Hash[x[i]]=i;

        int res=;

        for(int i=n-;i>=;i--){

            if(update(,Hash[poster[i].first],Hash[poster[i].second]))

                res++;

        }

        printf("%d\n",res);

    }

    return ;

}

---恢复内容结束---

相关文章