BZOJ 2501 SodaMachine苏打贩卖机

题目大意

给你一些区间，请求一个点使得这个点所在的区间数量最多。区间数量50000，区间L，R大小$\le 10^9$.

这道题首先我们发现LR只需要维护相对关系（并查集？）所以1e9完全可以离散化到区间数量1e5

之后我们发现查分完全可以满足我们的需求——大量更改每个只需要O(1)，只有一次查询O(1e5)可以接受。

关键是离散化写法。

这里我们使用一个结构体存储每个元素（L,R一视同仁），VAL表示这个值，NUM表示他在第几个区间里，FLG记录他是左端点还是右端点。之后我们按照VAL进行第一次排序，进行离散化（具体看代码），之后进行第二次Sort（注：在这道题中第二次排序可以省略，因为可以直接打标记，但是为了使得代码更加规范自己忘记考虑还是写上吧）

之后我们设立ans数组记录个数。对于每一个左端点将值+1，（右端点+1）的位置-1（否则会出错，因为你需要此时删掉这个区间），之后从头加到尾，每加上一个数就进行一次判断更新最终的答案，之后输出答案就可以了。

//Code Migration
#include <cstdio>
#include <algorithm>
using namespace std;
struct query
{
    int val,num,flg;
}q[100010];
int ans,n,f[100010];
bool cmpa(query tx,query ty){return tx.val<ty.val;}
bool cmpb(query tx,query ty){if(tx.flg==ty.flg)return tx.num<ty.num;return tx.flg<ty.flg;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&q[i].val,&q[i+n].val);
    for(int i=1;i<=n;++i) q[i+n].val++,q[i].flg=1,q[n+i].flg=2,q[i].num=q[n+i].num=i;
    n<<=1;
    sort(q+1,q+n+1,cmpa);
    int tmpa=0,tmpb=0;
    for(int i=1;i<=n;++i)
    {
        if(tmpa!=q[i].val) ++tmpb,tmpa=q[i].val;
        q[i].val=tmpb;
    }
    sort(q+1,q+n+1,cmpb);
    n>>=1;
    for(int i=1;i<=n;++i) f[q[i].val]++,f[q[n+i].val]--;
    tmpa=0;
    for(int i=1;i<=tmpb+5;++i)
    {
        //printf("%d %d %d\n",ans,f[i],tmpa);
        tmpa+=f[i];
        ans=max(ans,tmpa);
    }
    //for(int i=1;i<=n;++i) printf("%d %d %d %d\n",q[i].val,q[i].num,q[n+i].val,q[n+i].num);
    printf("%d",ans);
    return 0;
}