Mayor‘s posters (线段树+离散化)

线段树+离散化)"/>

Mayor‘s posters (线段树+离散化)

题目链接：Mayor’s posters

思路：由于看到l,r的值最大可达到1e7，这时候如果强行build，那么大概率会出错，看到n的值只有1e4，这时候我们应该想到用离散化去解决这个问题。
而且，这里还有一个坑点，假如所给区间为[1,4],[6,7],[1,7],那么离散化之后1,4,6,7分别对应1,2,3,4这时候如果求出海报的种类，那么就错误的求出了[1,2],[3,4]的海报种类为2。所以我们判断当两个结点的值的差大于1时，那么插入一个中间结点，就可以避免此情况。

代码：(还是y总的代码风格看起来舒服)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> p;
int idx=1;
struct node
{int l,r,col;
}tr[4*N];
int a[N];
vector<int> alls;
vector<p> sec;
int find(int x)
{int l=0,r=alls.size();while(l<r){int mid=l+r>>1;if(x<=alls[mid])r=mid;else l=mid+1;}return l+1;
}
void build(int u,int l,int r)
{tr[u]={l,r};if(l==r)return;int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void pushdown(int u)
{node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];if(root.col&&root.l!=root.r){left.col=root.col,right.col=root.col;root.col=0;}
}
void modify(int u,int l,int r,int k)
{if(l<=tr[u].l&&r>=tr[u].r){tr[u].col=k;}else{pushdown(u);int mid=tr[u].l+tr[u].r>>1;if(l<=mid)modify(u<<1,l,r,k);if(r>mid)modify(u<<1|1,l,r,k);}
}
int query(int u)
{pushdown(u);if(tr[u].col&&!a[tr[u].col]){a[tr[u].col]=1;return 1;}if(tr[u].l==tr[u].r)return 0;int sum=0;sum+=query(u<<1)+query(u<<1|1);return sum;
}
int main()
{int t;cin>>t;while(t--){int n,l,r;cin>>n;idx=1;while(n--){cin>>l>>r;alls.push_back(l),alls.push_back(r);sec.push_back({l,r});}sort(alls.begin(),alls.end());alls.erase(unique(alls.begin(),alls.end()),alls.end());int len=alls.size();for(int i=1;i<len;i++){if(alls[i]-alls[i-1]>1)alls.push_back(alls[i-1]+1);//这就是解决那个问题的重要代码}sort(alls.begin(),alls.end());//之后再进行一次离散化alls.erase(unique(alls.begin(),alls.end()),alls.end());build(1,1,alls.size());//根据alls数组的大小来Buildfor(int i=0;i<sec.size();i++){int ll=find(sec[i].first),rr=find(sec[i].second);//用二分查找离散化后对应的位置modify(1,ll,rr,idx);idx++;//不同数字代表不同海报}cout<<query(1)<<endl;memset(a,0,sizeof a);alls.clear(),sec.clear();}
}