POJ 2528 Mayor‘s posters（線段樹+思維）

題目傳送門

題目大意

思路

這個不是什麼闆子題要不然也不可能會挂那麼多人www，這個題的大緻思路就是張貼報紙的話，最後一次張貼的報紙一定能看見，是以應該倒序周遊，如果目前周遊到的報紙在之前被完全覆寫住，那麼說明不能被看到，是以我們用線段樹來維護這個區間是否全部被覆寫到（也就是最後傳回的是一個bool值），注意pushup的部分，如果兩個區間都傳回的是true，那麼這個大區間合并也應該是true。

#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
const int N=4e7;
bool tr[N];
int l[N];
int r[N];
bool query(int p,int l,int r,int ll,int rr){
	if(tr[p])return 0;
	if(l==ll&&r==rr){tr[p]=true;
		return 	true;
	}
	int mid=l+r>>1;
	bool k=0;
	if(rr<=mid){
		k=query(p<<1,l,mid,ll,rr);
	}else if(ll>mid)k=query(p<<1|1,mid+1,r,ll,rr);
	else {
		bool k1=query(p<<1,l,mid,ll,mid);
		bool k2=query(p<<1|1,mid+1,r,mid+1,rr);
		if(k1||k2)k=true;
	}
	if(tr[p<<1]&&tr[p<<1|1])tr[p]=true;
	return k;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		memset(tr,0,sizeof tr);
		int n;
		scanf("%d",&n);
		int maxx=0;
		for(int i=1;i<=n;i++){
			scanf("%d %d",l+i,r+i);
			maxx=max(maxx,r[i]);
		}
		int ans=0;
		for(int i=n;i;i--){
			if(query(1,1,maxx,l[i],r[i]))ans+=1;//cout<<ans<<endl;
		}
		cout<<ans<<endl;
	}
}