题目链接: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数组的大小来Build
for(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();
}
}