Mayor‘s posters（离散化+线段树）

线段树）"/>

Mayor‘s posters（离散化+线段树）

题目传送门

Mayor’s posters

题目大意

n（n<=10000) 个人依次贴海报,给出每张海报所贴的范围 l i ， r i （ 1 < = l i < = r i < = 10000000 ) l_i，r_i（1<=l_i<=r_i<=10000000) li​，ri​（1<=li​<=ri​<=10000000) 。求出最后还能看见多少张海报。（海报只露出部分也算）

思路

首先注意到数据范围 l i ， r i （ 1 < = l i < = r i < = 10000000 ) l_i，r_i（1<=l_i<=r_i<=10000000) li​，ri​（1<=li​<=ri​<=10000000)，显然直接开数组存会TLE或者MLE
所以需要离散化处理一下数据，处理的时候记得非相邻区间查一个值进去
离散化之后就是线段树处理了，每次更新数据时（即为贴上新海报的时候）值为 i i i，可以在懒惰标记下沉的时候将颜色传进去，最后查询整个线段树记录叶节点的颜色即可
具体操作可以参考大佬的解释：线段树懒惰标记操作

AC Code

#include<vector>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
const int N=2e5+9;
int flag[N];
struct node{int x, y;
}a[N];
struct segtree{int v, colour;
}tr[N<<2];
inline int read()
{int ans=0;char last=' ',ch=getchar();while(ch<'0'||ch>'9') last=ch,ch=getchar();while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();if(last=='-') ans=-ans;return ans;
}
inline int lc(int p)   {return p<<1;}
inline int rc(int p)   {return p<<1|1;}
inline void build(int k, int l, int r){tr[k].colour=0;if(l==r)    return ;int mid=(l+r)>>1;build(lc(k), l, mid);build(rc(k), mid+1, r);
}
inline void f(int p, int k){tr[p].colour=k;
}
inline void push_down(int p){f(lc(p), tr[p].colour);f(rc(p), tr[p].colour);tr[p].colour=0;
}
// inline void push_up(int p)  {tr[p].v=max(tr[lc(p)].v, tr[rc(p)].v);}
inline void updata(int p, int l, int r, int x, int y, int k){if(x>r || y<l)  return ;if(l<=x && y<=r){tr[p].colour=k;return ;}  int mid=(x+y)>>1;if(tr[p].colour) push_down(p);updata(lc(p), l, r, x, mid, k);updata(rc(p), l, r, mid+1, y, k);// push_up(p);
}
inline void query(int p, int l, int r, int x, int y){if(x==y && tr[p].colour==0) return ;if(tr[p].colour)  {flag[tr[p].colour]=1; return ;}int mid=(x+y)>>1;// if(tr[p].tag) push_down(p);query(lc(p), l, r, x, mid);query(rc(p), l, r, mid+1, y);
}
int T, n;
vector<int>v;
int val[N]; 
int main(){cin>>T;while(T--){// 离散化memset(flag, 0, sizeof(flag));v.clear();n=read();for(int i=1; i<=n; i++){a[i].x=read(); a[i].y=read();v.push_back(a[i].x);v.push_back(a[i].y);}sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());val[0]=1;int k=1;for(int i=1; i<v.size(); i++){if(v[i]-v[i-1]==1)   k++;else                 k+=2;val[i]=k;}build(1,1,N);for(int i=1; i<=n; i++){a[i].x=val[(lower_bound(v.begin(), v.end(), a[i].x)-v.begin())];a[i].y=val[(lower_bound(v.begin(), v.end(), a[i].y)-v.begin())];updata(1,a[i].x,a[i].y,1,N,i);}query(1,1,N,1,N);int ans=0;for(int i=1; i<=n; i++) if(flag[i]) ans++;cout<<ans<<endl;}return 0;
}