poj 2528 Mayor‘s posters"/>
poj 2528 Mayor‘s posters
题目链接如下：
2528 -- Mayor's posters
目录
1.没过但是不知道为什么没过的方法一
2.过了的方法二
1.没过但是不知道为什么没过的方法一
首先来个没过的解法：（很奇怪啊，很多测试都测过了，但是还是没过不知道为啥。
思路就是反过来贴，在构造线段树的时候用一个数组记录区间是否已经被覆盖了。
然后再离散化区间，也就是压缩区间。
举个例子，有个输入有三个区间长这样：
[1,10],[1,4],[9,10]
我们先排个序1 1 4 9 10 10
再去重变成1 4 9 10
再映射一下1 2 3 4
然后用这1-4建立线段树，以后用到其他的数字就映射到1-4的数字。
这个方法是打标记，试想一下对上面那个区间打标记，从后往前，我们发现，[9 10] [1 4]两个区间打完之后，其实就相当于1234都打上了覆盖的标记，那么其实再标记[1 10]的时候我们就会发现不能覆盖，所以计数是2，但是其实应该是3，所以我们这里应该给4和9之间再插一个数字来避免这种情况。
代码如下所示：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<algorithm>
#include<cstring>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<cmath>using namespace std;#define MAXN 20001int pl[MAXN],pr[MAXN];// 记录输入的左区间右区间
int port[MAXN],id[MAXN];// 用于区间压缩
int cnt;
int s[4*MAXN],e[4*MAXN];// 记录节点的左右子树
bool covered[4*MAXN];// 记录
int T;
int n;void build_tree(int l, int r, int rt)
{
// s[rt] = l;
// e[rt] = r;
// covered[rt] = false;
//
// if(l != r){
// build_tree(l, (l + r) / 2, rt << 1);
// build_tree((l + r) / 2 + 1, r, rt << 1 | 1);
// }if (l>r) return;s[rt]=l;e[rt]=r;covered[rt]=false;if (l!=r){build_tree(l,(l+r)/2,rt << 1);build_tree((l+r)/2+1,r,rt << 1 | 1);}
}bool query(int l,int r,int rt){if (covered[rt]== true) return false;bool res=false;if (l==s[rt] && r==e[rt]){covered[rt]=true;return true;}else if (r<=(s[rt]+e[rt])/2){res=query(l,r,rt<<1);}else if (l>(s[rt]+e[rt])/2){res=query(l,r,(rt<<1)+1);}else{res=query(l,(s[rt]+e[rt])/2,rt<<1) || query((s[rt]+e[rt])/2+1,r,(rt<<1)+1);}if (covered[rt<<1] && covered[(rt<<1)+1]){covered[rt]= true;}return res;
}int main()
{scanf("%d",&T);int res;while (T--){cnt=0;scanf("%d",&n);for (int i = 0; i < n; ++i) {scanf("%d %d", &pl[i], &pr[i]);port[cnt++]=pl[i];port[cnt++]=pr[i];}sort(port,port+cnt);cnt=unique(port,port+cnt)-port;for (int i = 1; i < cnt; ++i) {if (port[i]-port[i-1]>1){port[cnt++]=port[i-1]+1;}}sort(port,port+cnt);build_tree(1,cnt,1);for (int i = 0; i < cnt; ++i) {id[port[i]]=i+1;}res=0;for (int i = n-1; i >= 0; --i) {if (query(id[pl[i]],id[pr[i]],1)){res++;}}printf("%d\n",res);}return 0;
}但是他就是过不了寄了，也不知道为什么。
不过突然发现我上边更新cnt循环里边有问题，咋在循环的时候还改条件了...
这里边粘一个AC的：
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e4+5;
int t,n,l[maxn],r[maxn],section[maxn<<2],cnt,res;
struct node {bool val;
} seg[maxn<<4];
void PushDown(int rt) {if(seg[rt].val) {seg[rt].val=0;seg[rt<<1].val=1;seg[rt<<1|1].val=1;}
}
bool Query(int L,int R,int l,int r,int rt) {if(L<=l&&r<=R)return seg[rt].val;int mid=(l+r)>>1;bool flag=1;PushDown(rt);if(L<=mid)flag&=Query(L,R,l,mid,rt<<1);if(R>mid)flag&=Query(L,R,mid+1,r,rt<<1|1);return flag;
}
void Update(int L,int R,int l,int r,int rt) {if(L<=l&&r<=R) {seg[rt].val=1;return ;}int mid=(l+r)>>1;PushDown(rt);if(L<=mid)Update(L,R,l,mid,rt<<1);if(R>mid)Update(L,R,mid+1,r,rt<<1|1);seg[rt].val=(seg[rt<<1].val&seg[rt<<1|1].val);
}
void Build(int l,int r,int rt) {if(l==r) {seg[rt].val=0;return ;}int mid=(l+r)>>1;Build(l,mid,rt<<1);Build(mid+1,r,rt<<1|1);seg[rt].val=(seg[rt<<1].val&seg[rt<<1|1].val);
}
int main() {scanf("%d",&t);while(t--) {cin >>n;cnt=0,res=0;for(int i=1; i<=n; i++) {//存下每个值准备离散化cin >>l[i]>>r[i];section[++cnt]=l[i];section[++cnt]=r[i];}Build(1,cnt+1,1);//初始化线段树，注意范围sort(section+1,section+1+cnt);//排序int len=unique(section+1,section+1+cnt)-section-1;//获得去重之后的长度for(int i=n; i>=1; i--) {int ll=lower_bound(section+1,section+1+len,l[i])-section;int rr=lower_bound(section+1,section+1+len,r[i])-section;if(!Query(ll,rr,1,len,1))res++;//判断区间是否有空Update(ll,rr,1,len,1);}cout <<res<<endl;}return 0;
}参考博客：
POJ - 2528 奇怪的测试数据_weixin_30725467的博客-CSDN博客
2.过了的方法二
说说和上边改了的点，首先是思路的改变：
这次正着来，但是给每个点打上一个标记记录这是第几个输入的区间，pushdown用于动态更新区间，然后可想而知，后粘贴的会位于先占区间的上面的树节点的位置，我们在最后遇到第一个打上标签的节点就直接返回即可。
然后和方法一不同的是这里修改了插入新节点的方式...至少是正确的插入方式了...
离谱的是这里用hash好像会re，换成二分反而能ac，有一种可能是m>nlogn了...但是这里m好像最大也就4n，也就是10000的区间数量级别？可能有些恶心的数据？不太懂。
代码如下所示：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<algorithm>
#include<cstring>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<cmath>using namespace std;const int MAXN=11111;struct node{int l,r,id;
}segTree[MAXN*16+5];
int pl[MAXN+5],pr[MAXN+5];// 记录输入的左区间右区间
int port[MAXN*4+5],id[MAXN*4+5];// 用于区间压缩
int vis[MAXN];
int cnt;
int T;
int n;
int res;void pushdown(int rt){if (segTree[rt].id!=-1){segTree[rt<<1].id=segTree[rt].id;segTree[rt<<1|1].id=segTree[rt].id;segTree[rt].id=-1;}
}void buildTree(int l, int r, int rt)
{segTree[rt].l=l;segTree[rt].r=r;segTree[rt].id=-1;if (l!=r){int mid=(l+r)/2;buildTree(l,mid,rt << 1);buildTree(mid+1,r,rt << 1 | 1);}
}void update(int l,int r,int rt,int id){if (segTree[rt].l==l && segTree[rt].r==r){segTree[rt].id=id;return;}pushdown(rt);int mid=(segTree[rt].l+segTree[rt].r)/2;if (r<=mid){update(l,r,rt<<1,id);}else if (l>mid){update(l,r,rt<<1|1,id);}else{update(l,mid,rt<<1,id);update(mid+1,r,rt<<1|1,id);}
}void query(int l,int r,int rt){if (segTree[rt].id!=-1){if (!vis[segTree[rt].id]){vis[segTree[rt].id]=true;res++;}segTree[rt].id=-1;return;}if (l==r) return;pushdown(rt);int mid=(segTree[rt].l+segTree[rt].r)/2;if (r<=mid){query(l,r,rt<<1);}else if (l>mid){query(l,r,rt<<1|1);}else{query(l,mid,rt<<1);query(mid+1,r,rt<<1|1);}
}int BSearch(int low,int high,int num)
{int mid;while(low<=high){mid=(low+high)/2;if(num==port[mid])return mid;else if(port[mid]>num)high=mid-1;else low=mid+1;}return low;
}int main()
{scanf("%d",&T);int m;while (T--){cnt=0;scanf("%d",&n);memset(vis, 0, sizeof(vis));for (int i = 0; i < n; ++i) {scanf("%d %d", &pl[i], &pr[i]);port[cnt++]=pl[i];port[cnt++]=pr[i];}sort(port,port+cnt);
// cnt=unique(port,port+cnt)-port;m=1;for (int i = 1; i < cnt; ++i) {if (port[i]!=port[i-1]){port[m++]=port[i];}}for (int i = m-1; i >= 1; --i) {if (port[i]-port[i-1]>1){port[m++]=port[i-1]+1;}}sort(port,port+m);buildTree(1,m,1);
// for (int i = 0; i < m; ++i) {cout<<port[i]<<":"<<i+1<<endl;
// id[port[i]]=i+1;
// }for (int i = 0; i < n; ++i) {int l= BSearch(0,m-1,pl[i]);int r= BSearch(0,m-1,pr[i]);
// cout<<l<<","<<r<<endl;update(l+1,r+1,1,i);}res=0;query(1,m,1);printf("%d\n",res);}return 0;
}//1
//4
//1 3
//1 10
//1 4
//6 10//1
//5
//1 4
//2 6
//8 10
//3 4
//7 10//1
//4
//1 3 1 10 1 4 6 10参考博客：
poj2528（线段树，离散化）_林伏案的博客-CSDN博客_poj2528
更多推荐
poj 2528 Mayor‘s posters
发布评论