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

线段树+离散化）"/>

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

题目：The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:

• Every candidate can place exactly one poster on the wall.
• All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
• The wall is divided into segments and the width of each segment is one byte.
• Each poster must completely cover a contiguous number of wall segments.

They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
Your task is to find the number of visible posters when all the posters are placed given the information about posters' size, their place and order of placement on the electoral wall.

大意：有t组数据，每组有n张区间[l,r]的海报张贴，海报会根据粘贴顺序相互覆盖，求最终有多少种海报（类似于涂色覆盖）

思路：看到区间操作，首先想到线段树，但是这题的区间长度有1e7那么大，如果直接开就要4*1e7的数组大小，显然开不了。。。可以注意到n最大为1e5，那我们可以把每个区间长度缩小，即只存l和r（也就是离散化，把区间变成点储存），这样我们只用开4*1e5大小的数组。然后这里有点小坑（离散化后，会遗漏区间），比如[1,8],[1,4][6,8]，离散化后[1,4]、[1,2]、[3,4],这样发现最终只得到2种海报覆盖（答案应该是3种），那么问题来了，为啥？因为[4,6]之间的海报没数到，所以我们在间隔大于1的两个端点之间都增加一个点。

本题用到了unique函数，包含在#include<algorithm>中，它的作用是：去掉容器中相邻元素的重复元素（这里的去掉指的是把“去掉的元素”接在数组的后面），并返回去重后的尾地址。（所以使用前应该排序）

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=2e5+5;
struct node{int l,r;int cover;
}tr[N<<2];
int sum;
int rec[N],x[N],y[N],ls[N];
void bt(int u,int l,int r)
{if(l==r){tr[u].r=tr[u].l=l;tr[u].cover=0;}else{tr[u].r=r;tr[u].l=l;tr[u].cover=0;int mid=l+r >> 1;bt(u<<1,l,mid);bt(u<<1|1,mid+1,r); }
}
void pushdown(int u)
{if(tr[u].cover==0) return;tr[u<<1].cover=tr[u].cover;tr[u<<1|1].cover=tr[u].cover;tr[u].cover=0;
}
void update(int u,int l,int r,int d)
{if(l<=tr[u].l&&tr[u].r<=r){tr[u].cover=d;}else{pushdown(u);int mid=tr[u].l+tr[u].r >>1;if(l<=mid) update(u<<1,l,r,d);if(r>mid) update(u<<1|1,l,r,d);}
}
void query(int u,int l,int r)
{if(tr[u].cover!=0&&!rec[tr[u].cover]){sum++;rec[tr[u].cover]=1;//标记此种颜色return;}if(l==r) return;pushdown(u);int mid=l+r>> 1;query(u<<1,l,mid);query(u<<1|1,mid+1,r);
}
int main()
{int t;cin >> t;while(t--){int n,cnt=0;sum=0;memset(rec,0,sizeof(rec));//初始化cin >> n;for(int i=0;i<n;i++){cin >> x[i] >> y[i];ls[cnt++]=x[i];ls[cnt++]=y[i];}sort(ls,ls+cnt);//先排序int len=unique(ls,ls+cnt)-ls;//去重cnt=len;for(int i=1;i<len;i++){if(ls[i]-ls[i-1]>1){ls[cnt++]=ls[i-1]+1;//两端点增加一个点}}sort(ls,ls+cnt);//因为增加了点，所以又要排序bt(1,1,cnt);for(int i=0;i<n;i++){int l=lower_bound(ls,ls+cnt,x[i])-ls+1;//二分查找左端点int r=lower_bound(ls,ls+cnt,y[i])-ls+1;//二分查找右端点update(1,l,r,i+1);//更新}query(1,1,cnt);cout << sum << endl;}
}