poj2528 Mayor's posters（线段树，离散化）-白红宇

poj2528 Mayor's posters（线段树，离散化）

阅读量：2441 次

发布时间：2019-05-10

本文共 1123 字，大约阅读时间需要 3 分钟。

离散化的思想：

对于这样的数据

（3，10000），

（9，1000000），

（5，100000），

（1，1000），

（7，1000000）

我们可以将其处理为

（2，7），

（5，9），

（3，8），

（1，6），

（4，9）

我们再对离散化之后的数据进行处理就行了。

题目意思：

n（n<=10000)个人依次贴海报,给出每张海报所贴的范围li，ri（1<=li<=ri<=10000000)。

求出最后还能看见多少张海报。

参考代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN = 10000+5;struct Node{	int l,r;	int c;}tree[14*MAXN];	//线段树struct Seg{	int l,r;}s[MAXN];	//存储报纸的范围struct Seg2{	int p;	int index;}a[2*MAXN];	//存放端点信息bool cmp(Seg2 x,Seg2 y){	return x.p
        
         =l && tree[node].r<=r){		tree[node].c=v;		return;	}	if (tree[node].c>0){		tree[2*node].c=tree[2*node+1].c=tree[node].c;		tree[node].c=0;	}	int mid=(tree[node].l+tree[node].r)/2;	if (r<=mid)		update(2*node,l,r,v);	else if (mid
         
          0){ if (color[tree[node].c]==0){ ans++; color[tree[node].c]++; } return; } if (tree[node].l==tree[node].r) return; count(2*node); count(2*node+1);}void solve(int n,int t){ build(1,1,t); //cout<<"--------"<
          
           0) s[a[i].index].l=t; else s[-a[i].index].r=t; } /* for (int i=1;i<=n;i++){ printf("%d %d\n",s[i].l,s[i].r); } */ solve(n,t); } return 0;}