Mayor's posters POJ - 2528 线段树区间覆盖

//线段树区间覆盖
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=;
int flag;
struct node{
int l,r;
//vis 是这块区域是否完全被覆盖
bool vis;
}tr[N<<];
struct point
{
int id;
int x;
}post[N<<];
int cmp1(point a,point b)
{
return a.x<b.x;
}
int cmp2(point a,point b)
{
if(a.id==b.id)
return a.x<b.x;
return a.id>b.id;
}
void pushup(int u)
{
tr[u].vis=tr[u<<].vis&&tr[u<<|].vis;
}
void build(int u,int l,int r)
{
tr[u]={l,r,};
if(l==r)
return ;
int mid=l+r>>;
build(u<<,l,mid);
build(u<<|,mid+,r);
}
void query(int u,int l,int r)
{
if(tr[u].vis)
return ;
if(tr[u].l==l&&tr[u].r==r)
{
tr[u].vis=;
flag=;
return;
}
int mid=tr[u].l+tr[u].r>>;
if(r<=mid)
query(u<<,l,r);
else if(l>mid)
query(u<<|,l,r);
else
{
query(u<<,l,mid);
query(u<<|,mid+,r);
}
pushup(u);
}
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
//离散化之前的数据
for(int i=;i<*n;i+=)
{
cin>>post[i].x>>post[i+].x;
post[i].id=post[i+].id=i;
}
//按照离散化之前的数据排序
sort(post,post+*n,cmp1);
//离散化
int tot=,pre=;
for(int i=;i<*n;i++)
{
//如果和上一个一样
//那么排名也就一样
if(post[i].x==pre)
{
post[i].x=tot;
}
//如果不一样,记录当前值
//排名++
else
{
pre=post[i].x;
post[i].x=++tot;
}
}
build(,,*n);
//排序,从后往前贴
//id大的在前
sort(post,post+*n,cmp2);
int ans=;
for(int i=;i<*n;i+=)
{
int l=post[i].x;
int r=post[i+].x;
flag=;
query(,l,r);
if(flag)
ans++;
}
cout<<ans<<endl;
}
return ;
}
上一篇:[NOI2015] 软件包管理器【树链剖分+线段树区间覆盖】


下一篇:做一个logitic分类之鸢尾花数据集的分类