题目大意
(n)个东西，每个东西有两个属性(s_i,v_i)。
给出(ds,dv)，定义从(n)个东西中选一些东西的价值是((这些东西的v的和)^{dv}-(这些东西的s的极差)^{ds})。
问从(n)个东西中选不超过(m)个东西的最大价值是多少。
(nleq 2 imes 10^5;mleq min(n,50);s,vleq 10^7;ds,dvleq 2;)时限2s。
一行题解
拿堆维护当前区间选的东西=>剪枝=>总入堆的东西的个数不超过2mn=>二分下一个入堆的点
题解
定下了选的东西中(s)的最大值(s_r)和最小值(s_l)后，当(s)在区间([s_l,s_r])的东西的个数少于(m)个时，最优方案是选所有(s)在区间([s_l,s_r])的东西；当(s)在区间([s_l,s_r])的东西的个数不少于(m)个时，一定是选择(s)在区间([s_l,s_r])中的(v)最大的(m)个东西。
这个方法的具体实现是：将所有东西按(s)排序，固定选择的区间的右（或左）端点，先选考虑它为右（或左）端点的长度为1~m的区间，再左（或右）移区间的左（或右）端点，同时维护一个大小为(m)的、初始堆里有右端点左侧的(m)个东西的、以(v)为关键字的小根堆表示当前情况下选的东西。
在当前区间的右端点对应的东西弹出堆后，会发现此时堆中的东西对应的区间的右端点在当前右端点左侧，也就是说这个情况已经被考虑过了(1)。这时候就可以去考虑下一个右端点了。
入堆的东西中，(v)大于等于右端点的(v)的东西不会超过(m)个，因为当出现了(m)个时，右端点会成为(s)最小的东西，当第(m+1)个出现时，就会发生(1)的情况。
对于每个东西，“它入堆时，当前右端点的(v)大于它的”这种情况只会出现(m)次。假设这种情况发生了(p(p>m))次，那么它和第(p)次右端点之间会有不少于(m)个(v)大于它的东西（也就是前(m)次的右端点），使它不是它和右端点之间(v)前(m)大的东西，这与假设不符。
所以“有东西入堆”总共发生不超过2mn次，可以枚举右端点、二分下一个入堆的东西。
总时间复杂度(Theta(n imes m imes log_2 n))
代码
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define LL long long
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define maxn 200007
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;
}
void write(LL x)
{
char ch[20];int f=0;
if(!x){putchar('0'),putchar('
');return;}
if(x<0)putchar('-'),x=-x;
while(x)ch[++f]=x%10+'0',x/=10;
while(f)putchar(ch[f--]);
putchar('
');
}
priority_queue<int >q;
pii a[maxn];
LL ans;
int n,m,ds,dv,st[20][maxn],lg[maxn];
inline LL sqs(LL x){if(ds==1)return x;return x*x;}
inline LL sqv(LL x){if(dv==1)return x;return x*x;}
inline int getmx(int L,int R)
{
int len=R-L+1;
return max(st[lg[len]][L],st[lg[len]][R-(1<<lg[len])+1]);
}
int main()
{
n=read(),m=read(),ds=read(),dv=read();lg[0]=-1;
rep(i,1,n)a[i].fi=read(),a[i].se=read(),lg[i]=lg[i>>1]+1;
sort(a+1,a+n+1);
rep(i,1,n)st[0][i]=a[i].se;
rep(i,1,lg[n])for(int j=1;j+(1<<i)-1<=n;j++)
st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
rep(p,1,n)
{
while(!q.empty())q.pop();
LL tmpv=0;int lim=max(1,p-m+1),nowR=p-m;
dwn(i,p,lim)q.push(-a[i].se),tmpv+=a[i].se,ans=max(ans,sqv(tmpv)-sqs(a[p].fi-a[i].fi));
while(nowR>=1)
{
if(-q.top()>=a[p].se){break;}
int L=1,R=nowR,pos=0,tmp=-q.top();
while(L<=R)
{
int mid=(L+R)>>1,mx=getmx(mid,nowR);
if(mx>tmp)pos=max(pos,mid),L=mid+1;
else R=mid-1;
}
if(!pos)break;
tmpv+=q.top(),q.pop(),q.push(-a[pos].se),tmpv+=a[pos].se;
ans=max(ans,sqv(tmpv)-sqs(a[p].fi-a[pos].fi));
nowR=pos-1;
}
}
write(ans);
return (~(0-0)+1);
}
一些感想
有必要练一练卡常技巧了。
日更失败！！！