| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 51098 | Accepted: 14788 |
Description
Input
Output
Sample Input
1 5 1 4 2 6 8 10 3 4 7 10
Sample Output
4
题意：
给定一些海报，可能相互重叠，告诉你每个海报
的宽度（高度都一样的）和先后叠放顺序，问没有被完全盖住的有多少张？
题解：
首先对n海报进行离散化
再线段树找出现的就好了
代码写得挫
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define maxn 200051 #define mod 10007 #define eps 1e-9 const int inf=0x3f3f3f3f; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } //****************************************************************** struct node { int x,index,jj; }a[100001]; bool cmp(node a,node b) { return a.x<b.x; } struct ss { int l,r,tag,v; }tr[100001]; int n,aa[100001],bb[100001],hash[100001]; void pushdown(int k) { if(tr[k].tag==0)return; if(tr[k].l==tr[k].r)return; tr[k<<1].tag=tr[k].tag; tr[k<<1|1].tag=tr[k].tag; tr[k<<1].v=tr[k].tag; tr[k].v=tr[k].tag; tr[k].tag=0; } void build(int k,int s,int t) { tr[k].l=s; tr[k].r=t; tr[k].tag=0; if(t==s){ tr[k].v=0;return; } int mid=(s+t)>>1; build(k<<1,s,mid); build(k<<1|1,mid+1,t); } void update(int k,int s,int t,int c) { if(tr[k].tag){ pushdown(k); } if(s==tr[k].l&&tr[k].r==t) { tr[k].tag=c; tr[k].v=c; return; } int mid=(tr[k].l+tr[k].r)>>1; if(t<=mid)update(k<<1,s,t,c); else if(s>mid)update(k<<1|1,s,t,c); else { update(k<<1,s,mid,c); update(k<<1|1,mid+1,t,c); } } void ask(int k,int s,int t) { if(tr[k].l==s&&t==tr[k].r&&tr[k].tag){ hash[tr[k].tag]=1; return ; } int mid=(tr[k].l+tr[k].r)>>1; if(t<=mid)ask(k<<1,s,t); else if(s>mid)ask(k<<1|1,s,t); else { ask(k<<1,s,mid); ask(k<<1|1,mid+1,t); } } int main() { int T=read(); while(T--) { memset(hash,0,sizeof(hash)); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i*2-1].x,&a[i*2].x); a[i*2-1].index=i; a[i*2].index=i; a[i*2-1].jj=1; a[i*2].jj=2; } a[0].x=0; sort(a+1,a+n*2+1,cmp); //for(int i=1;i<=n*2;i++)cout<<a[i].index<<" "<<a[i].x<<endl; int tmp=1; for(int i=1;i<=n*2;i++){ if(a[i].x==a[i-1].x)tmp--; if(a[i].jj%2==1) aa[a[i].index]=tmp; else bb[a[i].index]=tmp; tmp++; }//for(int i=1;i<=n;i++)cout<<" "<<aa[i]<<" "<<bb[i]<<endl; build(1,1,tmp-1); for(int i=1;i<=n;i++){ update(1,aa[i],bb[i],i); }//for(int i=1;i<=16;i++)cout<<tr[i].tag<<endl; ask(1,1,tmp-1); int ans=0; for(int i=1;i<=n;i++) { if(hash[i])ans++; } cout<<ans<<endl; } return 0; }
POJ2528Mayor's posters 线段树+离散化
原文：http://www.cnblogs.com/zxhl/p/4766286.html
