题解
堆+贪心
题意就是给你(n)个物品,让你最多选(m)个
每个物品有两个属性(a_i,b_i)
最大化((sum_{a_i})^{dv}+(max(b_i)-min(b_i))^{ds})
首先后面的那个东西看着不是很舒服
但是按照(b)为关键字排个序就可以消除(b)的影响了
那么我们只考虑(a)即可
以后我们可以发现答案所选择的物品一定是一个区间内最大的(k)个物品
所以我们可以固定一个右端点
然后不断向左扫去找前(k)大的值
这个东西可以用一个小根堆来实现
一旦右端点被弹出就结束寻找
这个复杂度是(O(n^2))
可以在找最大值时用(ST)表+二分做到(O(nlognlogm))
这个复杂度应该就可以卡着过了
当然我们可以对于每个位置处理出ta前面离ta最近的比ta大的值的位置
这样就省去了(ST)表+二分
复杂度变成了(O(nlogn))
但是由于两个(log)直接跑过去了我就懒得写一个(log)的了
代码
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
# define LL long long
const int M = 200005 ;
const int N = 20 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int n , m , ds , dv ;
int lg[M] , sz[M] , val[M] , st[M][N] ;
LL ans , sum ;
struct Node { int sz , val ; } p[M] ;
struct Pion { int idx , val ; } ;
inline bool operator < (Pion a , Pion b) {
return a.val > b.val ;
}
inline bool operator < (Node a , Node b) {
return a.sz < b.sz ;
}
priority_queue < Pion > q ;
inline int query(int l , int r) {
int j = lg[r - l + 1] ;
return max( st[l][j] , st[r - (1 << j) + 1][j] ) ;
}
inline LL dc(LL sum , int x) {
if(x == 1) return sum ;
return 1LL * sum * sum ;
}
inline int Getpos(int rp) {
int l = 1 , r = rp , ret = -1 , mid ;
while(l <= r) {
mid = (l + r) >> 1 ;
if(query(rp - mid + 1 , rp) > q.top().val) ret = rp - mid + 1 , r = mid - 1 ;
else l = mid + 1 ;
}
return ret ;
}
int main() {
n = read() ; m = read() ; ds = read() ; dv = read() ;
for(int i = 2 ; i <= n ; i ++) lg[i] = lg[i >> 1] + 1 ;
for(int i = 1 ; i <= n ; i ++) p[i].sz = read() , p[i].val = read() ;
sort(p + 1 , p + n + 1) ;
for(int i = 1 ; i <= n ; i ++) {
sz[i] = p[i].sz , val[i] = p[i].val ;
st[i][0] = val[i] ;
}
for(int j = 1 ; j <= lg[n] ; j ++)
for(int i = 1 ; i + (1 << j) - 1 <= n ; i ++)
st[i][j] = max( st[i][j - 1] , st[i + (1 << (j - 1))][j - 1] ) ;
for(int i = 1 , pos ; i <= n ; i ++) {
sum = 0 ;
while(!q.empty()) q.pop() ;
for(int j = i ; j >= i - m + 1 && j >= 1 ; j --) {
q.push((Pion) { j , val[j] }) ;
sum += val[j] ;
ans = max( ans , dc(sum , dv) - dc(sz[i] - sz[j] , ds) ) ;
}
pos = i - m + 1 ; if(pos <= 1) continue ;
bool exist = true ;
while(exist) {
if(q.top().idx == i) break ;
pos = Getpos(pos - 1) ; if(pos < 0) break ;
sum += val[pos] - q.top().val ;
ans = max( ans , dc(sum , dv) - dc(sz[i] - sz[pos] , ds) ) ;
q.pop() ; q.push((Pion) { pos , val[pos] }) ;
}
}
printf("%lld
",ans) ;
return 0 ;
}