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 ;
}
---恢复内容结束---