题解：P11512 [ROIR 2017 Day 2] 力场
w_u_q_i_a_n
·
·
题解
外话
比赛时思考许久，赛后一看，求的是面积交，不是面积并，同时一百分。
正题
1.性质
### 2.思路
$\ \ \ \ \ \ $根据这个性质，我们可以将$x$从大到小排序，以此枚举$min(x_i)$。这时，只有$x\ge min(x_i)$的矩形才能选，然后在这些矩形中选前$k$大的$y$（此时的$min(y_i)$就是第$k$大的$y$）。这时问题已经转化为动态维护第$k$大。
### 3.维护方法
$\ \ \ \ \ \ $用一个小根堆，先将前$k$个数插进去，插入一个数时直接$push$进小根堆，再把此时的最小值删去，这时的堆顶就是第$k$小。
### 4.代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
struct node{
int x,y;
} a[N];
bool cmp(node a,node b){
return a.x>b.x;
}
priority_queue<int,vector<int>,greater<int> > q;
signed main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=k;i++) q.push(a[i].y);//前k个数入堆
int ans=a[k].x*q.top();
for(int i=k+1;i<=n;i++){//枚举min(xi)
q.push(a[i].y);
q.pop();
ans=max(ans,a[i].x*q.top());//累计答案
}
cout<<ans;
return 0;
}