jzoj 5849.【NOIP提高组模拟2018.8.25】d 排序+权值线段树

Description

Input

Output

Data Constraint

分析：
所有矩阵的交集最大面积显然为min(xi)∗min(yi)$min(x_i)\ast min(y_i)$。
我们先按长度排序，枚举一个最小值，然后把长度小于当前值的全部删掉，再从剩下的里面把宽度最小的一些矩阵删掉。其实这个东西可以用一个堆维护。考场上打了一个权值线段树，感觉好显然啊。

代码：

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define LL long long

const int maxn=1e5+7;
const int maxp=1e5;

using namespace std;

int test,n,m;
int t[maxn*4];
LL ans;

struct node{
    int x,y;
}a[maxn];

bool cmp(node x,node y)
{
    return x.x<y.x;
}

void ins(int p,int l,int r,int x,int k)
{
    if (l==r)
    {
        t[p]+=k;
        return;
    }
    int mid=(l+r)/2;
    if (x<=mid) ins(p*2,l,mid,x,k);
           else ins(p*2+1,mid+1,r,x,k);
    t[p]=t[p*2]+t[p*2+1];
}

int getrank(int p,int l,int r,int k)
{
    if (l==r) return l;
    int mid=(l+r)/2;
    if (k<=t[p*2]) return getrank(p*2,l,mid,k);
              else return getrank(p*2+1,mid+1,r,k-t[p*2]);
}

int main()
{
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d",&test);
    while (test--)
    {       
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
        sort(a+1,a+n+1,cmp);
        ans=0;           
        for (int i=n;i>0;i--)
        {
            ins(1,1,maxp,a[i].y,1);
            if (i-1>m) continue;
            int d=getrank(1,1,maxp,m-(i-1)+1);
            ans=max(ans,(LL)a[i].x*(LL)d);
        }
        for (int i=1;i<=n;i++) ins(1,1,maxp,a[i].y,-1);
        printf("%lld\n",ans);
    }
}