poj 2528 poster经典线段树+lazy+离散化

时间:2023-03-09 08:06:23
poj 2528 poster经典线段树+lazy+离散化
 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int a[maxn];int b[maxn];int x[maxn*];int flag[maxn];
int cor[maxn<<];
int cnt=;
int trans(int num,int l,int r)
{
// int m=(l+r)>>1;
// if(num==x[m]) return m;
// if(num>x[m]) return trans(num,m+1,r);
// if(num<trans) return trans(num,l,m);
while(l<=r)
{
int m=(l+r)>>;
if(x[m]==num) return m;
if(num>x[m]) l=m+;
else r=m;
}
return -;
}
void pushdown(int rt)
{
if(cor[rt]!=-)
{
cor[rt<<]=cor[rt];
cor[rt<<|]=cor[rt];
cor[rt]=-;
}
}
void update(int a,int b,int i,int l,int r,int rt)
{
if(a<=l&&b>=r)
{
cor[rt]=i;
return;
}
pushdown(rt);
int m=(r+l)>>;
if(a<=m) update(a,b,i,lson);
if(b>m) update(a,b,i,rson);
}
void query(int l,int r,int rt)
{
if(cor[rt]!=-)
{
if(!flag[cor[rt]])
{
cnt++;
flag[cor[rt]]=;
}
return;
}
if(l==r) return;
int m=(r+l)>>;
query(lson);
query(rson);
}
int main()
{
int cases,n;
scanf("%d",&cases);
while(cases--)
{
scanf("%d",&n);
memset(cor,-,sizeof(cor));
int pointer=;
for(int i=;i<n;i++)
{
scanf("%d%d",&a[i],&b[i]);
x[pointer++]=a[i];
x[pointer++]=b[i];
}
sort(x+,x+pointer);
int pointer2=;
for(int i=;i<pointer;i++)
{
if(x[i]!=x[i-]) x[pointer2++]=x[i];
}
for(int i=pointer2-;i>=;i--)
{
if(x[i]!=x[i-]+) x[pointer2++]=x[i-]+;
}
sort(x,x+pointer2);
for(int i=;i<n;i++)
{
int l=trans(a[i],,pointer2-);
int r=trans(b[i],,pointer2-);
update(l,r,i,,pointer2-,);
}
cnt=;
memset(flag,,sizeof(flag));
query(,pointer2-,);
printf("%d\n",cnt);
}
return ;
}