[C++知识库]POJ - 2528 Mayor‘s posters（set，线段树）

POJ - 2528 Mayor’s posters

set做法

从后往前扫描，查询当前l-r区间是否已经被完全覆盖，然后将l~r覆盖一遍。
我们考虑只把一部分的点放到set中以起到跟上述做法同样的效果：类似于离散化，只把每张海报的l,r,r+1三个点插入set，当l-r区间内没有点留在set中时，l-r区间一定是被完全覆盖了，这样时间复杂度降到了O(nlogn)，而且代码量比线段树小非常多。

#include<cstdio>
#include<vector>
#include<set>
using namespace std;
typedef pair<int,int> PII;
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n); 
        vector<PII> seg(n);
        set<int> left;
        for(int i=0;i<n;i++)
        {
            int l,r;scanf("%d%d",&l,&r);
            seg[i]=(PII){l,r};
            left.insert(l),left.insert(r+1);
        }
        int cnt=0;
        for(int i=n-1;i>=0;i--)
        {
        	int l=seg[i].first,r=seg[i].second;
            if(*left.lower_bound(l)<=r) cnt++;
            while(*left.lower_bound(l)<=r) left.erase(left.lower_bound(l));   
        }                                          
        printf("%d\n",cnt);
    }
    return 0;
}

离散化+线段树

区间覆盖问题，每一次都有编号为i的海报占有一部分区间，所以我们可以把这个海报占用的区间设置一个编号，然后经过n次操作后我们判断哪些编号出现了即可（没有出现即被其它编号替换了)。这其实就是一个线段树区间修改的操作，最后再区间查询即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 20010;
const int INF = 0x3f3f3f3f;
vector<PII> post;
vector<int> alls;
struct Node
{
	int l,r;
	int lazy,minv;
}tr[N*4];
void pushup(int u)
{
	tr[u].minv =min(tr[u<<1].minv,tr[u<<1|1].minv);
}
void build(int u,int l,int r)
{
	if(l==r) tr[u]=(Node){l,r,INF,0};
	else
	{
		tr[u]=(Node){l,r,0,0};
		int mid=(l+r)>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
}
void pushdown(int u)
{
	Node &root=tr[u],&left =tr[u<<1],&right=tr[u<<1|1];
	if(root.lazy)
	{
		left.minv=right.minv=left.lazy=right.lazy=root.lazy;
		root.lazy=0;
	}
}
void modify(int u,int l,int r,int v)
{
	if(tr[u].l>=l&&tr[u].r<=r) tr[u].minv=tr[u].lazy=v;
	else
	{
		pushdown(u);
		int mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) modify(u<<1,l,r,v);
		if(r>mid) modify(u<<1|1,l,r,v);
		pushup(u);
	}
}
int query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].minv;
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	int v=INF;
	if(l<=mid) v=min(v,query(u<<1,l,r));
	if(r>mid) v=min(v,query(u<<1|1,l,r));
	return v;
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		memset(tr, 0, sizeof tr);
		post.clear(), alls.clear();
		int n;scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			int l,r;scanf("%d%d", &l, &r);
			post.push_back((PII){l,r});
			alls.push_back(l);alls.push_back(r+1);
		}
		sort(alls.begin(),alls.end());
		alls.erase(unique(alls.begin(),alls.end()),alls.end());
		build(1,1,alls.size());
		for(int i=0;i<(int)post.size();i++)
		{
			int x=post[i].first,y=post[i].second;
			x=lower_bound(alls.begin(),alls.end(),post[i].first)-alls.begin()+1;
			y=lower_bound(alls.begin(),alls.end(),post[i].second)-alls.begin()+1;
			post[i]=(PII){x,y};
			modify(1,post[i].first,post[i].second,i+1);
		}
		int cnt=0;
		for(int i=0;i<(int)post.size();i++)
			if(query(1,post[i].first,post[i].second)==i+1)
				cnt++;
		printf("%d\n",cnt);
	}
	return 0;
}