Mayor's posters POJ

Mayor's posters POJ"/>

Mayor's posters POJ

Mayor's posters

题目链接：POJ - 2528

题意：在一个长度为10000000的墙上贴海报，共10000个，后贴的海报会覆盖之前的海报，给出海报的张贴范围及顺序，问最后还能看到几张海报；

x范围太大，需要离散化，然后倒序插入；

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
using namespace std;
const int maxn=10010;
struct node{int l, r;
}input[maxn];
int n;
int Hash[10000010], x[maxn<<1];
struct Node{int l, r;bool v;
}tr[maxn<<3];
void build(int m, int l, int r){tr[m].l=l;tr[m].r=r;tr[m].v=false;if(l==r) return;int mid=(l+r)>>1;build(m<<1, l, mid);build(m<<1|1, mid+1, r);
}
bool updata(int m, int l, int r){if(tr[m].v) return false;if(tr[m].l==l&&tr[m].r==r){tr[m].v=true;return true;}int temp;int mid=(tr[m].l+tr[m].r)>>1;if(r<=mid) temp=updata(m<<1, l, r);else if(l>mid) temp=updata(m<<1|1, l, r);else{bool t1=updata(m<<1, l, mid);bool t2=updata(m<<1|1, mid+1, r);temp=t1||t2;}tr[m].v=tr[m<<1].v&&tr[m<<1|1].v;return temp;
}
void init(){scanf("%d", &n);int cnt=0;for(int i=0; i<n; i++){scanf("%d%d", &input[i].l, &input[i].r);x[cnt++]=input[i].l;x[cnt++]=input[i].r;}sort(x, x+cnt);cnt=unique(x, x+cnt)-x;int num=1;for(int i=0; i<cnt; i++){Hash[x[i]]=i+1;	}build(1, 1, cnt);int ans=0;for(int i=n-1; i>=0; i--){int l=input[i].l, r=input[i].r;if(updata(1, Hash[l], Hash[r])) ans++;}printf("%d\n", ans);
}
int main(){int T;scanf("%d", &T);while(T--){init();}return 0;
}