Mayor‘s posters(线段树+离散化) [kuangbin带你飞]刷题记录

线段树+离散化) [kuangbin带你飞]刷题记录"/>

Mayor‘s posters(线段树+离散化) [kuangbin带你飞]刷题记录

Mayor’s posters

题意：

给出一面墙，给出n张海报贴在墙上，每张海报都覆盖一个范围，问最后可以看到多少张海报

思路:

既然这是线段树专题 , 那么我们就要线段树做吧 (其实还可以用优先队列 ), 首先L与R<=1e7 , n<=1e5,要建树,我们肯定得离散化才行 , 然后这颗树虽然不满足区间可加性但是这题,也没有区间查询只有单点查询,那就没事. 只用线段树维护区间的海报编号就行了

代码:

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<cmath>using namespace std;
typedef long long ll;
#define repi(x,y,z) for(int x = y; x<=z;++x)
#define deci(x,y,z) for(int x = y; x>=z;--x)
#define repl(x,y,z) for(ll x = y; x<=z;++x)
#define decl(x,y,z) for(ll x = y; x>=z;--x)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b / gcd(a, b))
#define INF 0x3f3f3f3f
#define ms(a,b) memset( a, b , sizeof (a) )
#define txt intxt()
#define CAS int casen;cin>>casen;for(int yl=1;yl<=casen;++yl)
#define py  puts("YES")
#define pn  puts("NO")
#define pcn  putchar('\n')
#define pcs  putchar(' ')
#define pc(a)  putchar(a)
#define pb(a)  push_back(a)
inline void intxt( ){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endif
}
inline ll read( ){ll f = 1,x = 0;char ch = getchar();while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}x *= f;return x;
}
const int maxn=2e5+5;ll tree[ 4*300000+5 ];//开4倍空间inline int ls(int p){ return p<<1; }//等价于rt*2
inline int rs(int p){ return (p<<1)|1; }//等价于rt*2+1inline void push_up( int p ){//向上更新tree[p]=tree[ls(p)]==tree[rs(p)]?tree[rs(p)]:0;//tree[p]=0表示这区间有多种海报//不为0就表示这段区间全为tree[p]的海报
}
inline void push_down( int p,int len ){//下压标记if( tree[p]==0 )return;tree[ls(p)]=tree[p];tree[rs(p)]=tree[p];tree[p]=0;
}void update(int L,int R,int p,int uL,int uR,ll val){//uL,uR为需要修改的区间if( L>=uL && R<=uR ){//在修改区间内tree[p]=val;return;}push_down(p,R-L+1);int M=( L+R )>>1;if( uL<=M ) update(L,M,ls(p),uL,uR,val);if( uR>=M+1 ) update(M+1,R,rs(p),uL,uR,val);push_up(p);
}ll query(int L,int R,int p,int qL,int qR){//qL,qR为需要查询的区间if(tree[p]!=0)//不为0就表示这段区间全为tree[p]海报了,就不用向下找了return tree[p];if( L>=qL && R<=qR ){//这是一定L==R==uL==uR,因为用的是单点查询return tree[p];//tree[p]一定不为0,可以直接返回}push_down(p,R-L+1);int M=(L+R)>>1;if( qL<=M ) return ( query(L,M,ls(p),qL,qR));//查询的点在M的左边if( qR>=M+1 ) return ( query(M+1,R,rs(p),qL,qR));//查询的点在M的右边return 0;
}int n;
struct cpp{int id,L,R,M;
}a[maxn];
int b[maxn];
map<int,int> fx;//离散化的映射
bool vis[300005];int main(){txt;CAS{ms(tree,0);//初始化,每一段初始化为0,表示没有海报scanf("%d",&n);repi(i,1,n){scanf("%d %d",&a[i].L,&a[i].R);a[i].id=i;if( a[i].R-a[i].L>1 )a[i].M=a[i].L+1;elsea[i].M=a[i].L;b[i*3-2]=a[i].L;b[i*3-1]=a[i].M;b[i*3]=a[i].R;}sort(b+1,b+1+3*n);//离散化int pre=-1e9;int jis=0;repi(i,1,n*3){//离散化if(pre!=b[i]){pre=b[i];fx[b[i]]=++jis;}}repi(i,1,n){//更新区间update(1,300000,1, fx[a[i].L] , fx[a[i].R] ,(ll)i );}ms(vis,0);int ans=0;ll tem;repi(i,1,3*n){tem=query(1,300000,1,fx[ b[i] ],fx[ b[i] ] );//单点查询if(vis[tem]==0){//统计答案ans++;vis[tem]=1;}}printf("%d\n",ans);}return 0;
}