本文主要是介绍POJ 2528 Mayor's posters（成段更新），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有t组测试数据，有n张海报，海报按题目给出的顺序覆盖，问最后能看到几张海报。
要用到离散化。因为题目给出的数字是对应区间的，要把它对应的边界上，可以a[i]--或者b[i]++。建树的时候，边界条件是left+1==right，因为区间是连续的。我把输入的数据，对应一个值，在查询的时候，如果当前的颜色是纯色的，那么就不用在往下查询把，对应的颜色的标记flag[i]表标记上，直接返回，最后判断扫一次flag表里有几个值被标记就可以统计出数据。
/*代码风格更新后*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
const int N=20005;struct node
{int lft,rht,co;int mid(){return MID(lft,rht);}
};int a[N],b[N],n;
vector<int> y;
bool flag[N/2];
map<int,int> H;struct Segtree
{node tree[N*4];void build(int lft,int rht,int ind){tree[ind].lft=lft; tree[ind].rht=rht;tree[ind].co=0;if(lft+1!=rht){int mid=tree[ind].mid();build(lft,mid,LL(ind));build(mid,rht,RR(ind));}}void updata(int st,int ed,int ind,int co){int lft=tree[ind].lft,rht=tree[ind].rht;if(st<=lft&&rht<=ed) tree[ind].co=co;else {if(tree[ind].co){tree[LL(ind)].co=tree[ind].co;tree[RR(ind)].co=tree[ind].co;tree[ind].co=0;}int mid=tree[ind].mid();if(st<mid) updata(st,ed,LL(ind),co);if(ed>mid) updata(st,ed,RR(ind),co);}}void query(int st,int ed,int ind){int lft=tree[ind].lft,rht=tree[ind].rht;if(tree[ind].co!=0||lft+1==rht) {flag[tree[ind].co]=1;return;}query(st,ed,LL(ind)); query(st,ed,RR(ind));}
}seg;
int main()
{int t;scanf("%d",&t);while(t--){y.clear(); H.clear();scanf("%d",&n);for(int i=0;i<n;i++) {flag[i]=0;scanf("%d%d",&a[i],&b[i]);b[i]++;y.push_back(a[i]); y.push_back(b[i]);}sort(y.begin(),y.end());y.erase(unique(y.begin(),y.end()),y.end());for(int i=0;i<(int)y.size();i++) H[y[i]]=i;int len=(int)y.size();seg.build(0,len-1,1);for(int i=0;i<n;i++) seg.updata(H[a[i]],H[b[i]],1,i+1);seg.query(1,len,1);int res=0;for(int i=1;i<=n;i++) if(flag[i]) res++;printf("%d\n",res);}return 0;
}
/*代码风格更新前*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define bug puts("here");
using namespace std;
const int N=21005;
int a[N],b[N];
int lisan(int,int);
struct POS
{int x,y;
}pos[N];
struct node
{int left,right,co;int mid(){return left+(right-left)/2;}
};
struct Segtree
{node tree[N*4];void build(int left,int right,int r){tree[r].left=left; tree[r].right=right;tree[r].co=0;if(left+1<right){int mid=tree[r].mid();build(left,mid,r*2);build(mid,right,r*2+1);}}void updata(int be,int end,int r,int co){if(be<=tree[r].left&&tree[r].right<=end){tree[r].co=co;}else{if(tree[r].co!=0){tree[r*2].co=tree[r*2+1].co=tree[r].co;tree[r].co=0;}int mid=tree[r].mid();if(be<mid) updata(be,end,r*2,co);if(end>mid) updata(be,end,r*2+1,co);}}void query(int r){if(tree[r].co!=0||tree[r].left+1==tree[r].right) {a[tree[r].co]=1;return;}else{query(r*2);query(r*2+1);}}
}seg;
int main()
{int t;scanf("%d",&t);while(t--){memset(a,0,sizeof(a));int n,cnt=0,ans=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&pos[i].x,&pos[i].y);pos[i].y++;b[cnt++]=pos[i].x;b[cnt++]=pos[i].y;}int imax=lisan(n,cnt);seg.build(0,imax,1);for(int i=0;i<n;i++){seg.updata(pos[i].x,pos[i].y,1,i+1);}seg.query(1);for(int i=1;i<=n;i++){if(a[i]) ans++;//printf("%d ",a[i]);}//puts("");printf("%d\n",ans);}return 0;
}
int lisan(int n,int cnt)
{sort(b,b+cnt);cnt=unique(b,b+cnt)-b;int imax=0;for(int i=0;i<n;i++){pos[i].x=lower_bound(b,b+cnt,pos[i].x)-b;imax=max(imax,pos[i].x);pos[i].y=lower_bound(b,b+cnt,pos[i].y)-b;imax=max(imax,pos[i].y);//printf("x=%d,y=%d,i=%d\n",pos[i].x,pos[i].y,i+1);}return imax;
}
这篇关于POJ 2528 Mayor's posters（成段更新）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
