传送门

试图用$kdt$强上凸包の翻车现场。

以下记$a_i$为$t[i]$,$b_i$为$p[i]$,$S$为去掉得分比前$d$小后的$\sum a_i$,$T$为去掉前$d$小后的$\sum b_i$。

如果存在一种更优的方案,一定可以在前$d$小里选$1$场替换掉已有的$1$场,使得分更大。

即$\dfrac{S-a_i+a_j}{T-b_i+b_j}>\dfrac{S}{T}(j\le d <i)$

化简一波这个式子就成了$Ta_j-Sb_j>Ta_i-Sb_i$

于是选出最大的$Ta_j-Sb_j$和最小的$Ta_i-Sb_i$判断一下即可。

怎么搞呢?


第一想法:我们发现这个式子长得很$kdt$(参见巧克力王国)。

直接上$kdt$瞎搞一搞就行了,计算矩形端点的取值剪枝。复杂度没有保证,反正$kdt$是暴力

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <time.h>

#define maxn 50005

const long long inf = 1e18;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
#define son(x,y) son[x][y]
#define ls(x) son(x,0)
#define rs(x) son(x,1)
#define up(f,a,b) a[node][c[node]]=f(f(a[ls(node)][c[node]],a[rs(node)][c[node]]),p[node][b])
#define dup(f,a) a[node][c[node]^1]=f(a[ls(node)][c[node]^1],a[rs(node)][c[node]^1])
long long s,t,res;
int ans[maxn],id[maxn],fa[maxn],son[maxn][2],xl[maxn][2],xr[maxn][2],yl[maxn][2],yr[maxn][2],p[maxn][2],root,cnt,D;
bool c[maxn];
struct grade{
    int a,b;
    bool operator < (const grade &x)const{return a*x.b<b*x.a;}
}g[maxn];
struct point{
    int pos[2],id;
    bool operator < (const point &x)const{return pos[D]<x.pos[D];}
}po[maxn];
inline void update(int node){
    up(min,xl,0),up(max,xr,0),up(min,yl,1),up(max,yr,1);
    dup(min,xl),dup(max,xr),dup(min,yl),dup(max,yr);
}
void build(int l,int r,int &node){
    if(l>r)return;
    int mid=l+r>>1;
    node=++cnt,D=rand()&1;
    nth_element(po+l,po+mid,po+r+1);
    memcpy(p[node],po[mid].pos,sizeof p[node]),id[po[mid].id]=node;
    build(l,mid-1,ls(node)),build(mid+1,r,rs(node));
    fa[ls(node)]=fa[rs(node)]=node;
    update(node);
}
inline void toggle(int node){
    c[node]=1;
    while(node)update(node),node=fa[node];
}
inline long long calc_max(int node){return node?t*xr[node][1]-s*yl[node][1]:-inf;}
inline long long calc_min(int node){return node?t*xl[node][0]-s*yr[node][0]:inf;}
void Max(int node){
    if(c[node])res=max(res,t*p[node][0]-s*p[node][1]);
    long long d[2]={calc_max(ls(node)),calc_max(rs(node))};
    int t=d[1]>d[0];
    if(d[t]>res)Max(son(node,t));
    if(d[t^1]>res)Max(son(node,t^1));
}
void Min(int node){
    if(!c[node])res=min(res,t*p[node][0]-s*p[node][1]);
    long long d[2]={calc_min(ls(node)),calc_min(rs(node))};
    int t=d[1]<d[0];
    if(d[t]<res)Min(son(node,t));
    if(d[t^1]<res)Min(son(node,t^1));
}
inline long long ma(){res=-inf,Max(root);return res;}
inline long long mi(){res=inf,Min(root);return res;}
int main(){
    srand(time(0));
    int n=read(),cnt=0;
    for(register int i=1;i<=n;++i)s+=(g[i].a=read()),t+=(g[i].b=read());
    sort(g+1,g+1+n);
    for(register int i=1;i<=n;++i)po[i].id=i,po[i].pos[0]=g[i].a,po[i].pos[1]=g[i].b;
    build(1,n,root);
    for(register int i=1;i<n;++i){
        s-=g[i].a,t-=g[i].b,toggle(id[i]);
        if(ma()>mi())ans[++cnt]=i;
    }
    printf("%d\n",cnt);
    for(register int i=1;i<=cnt;++i)printf("%d\n",ans[i]);
}

$kdt$丰硕的战果:

  • 复杂度没有保证:最后一个点跑了$29s$
  • 反正$kdt$是暴力:喜提和暴力一个分


重新考察这个式子$Ta_j-Sb_j>Ta_i-Sb_i$:

令$Ta_i-Sb_i=C$,变形一波又成了$\frac{T}{S}a_i-\frac{C}{S}=b_i$。

把$\frac{T}{S}$看作斜率,$\frac{C}{S}$为截距。目的是最小/最大化$C$。

问题就很斜率优化了。维护若干个点,支持:

  • 插入一个点
  • 给定一条直线的斜率,使它过一个点,最大/小化截距

显然斜率是单调的。没什么高论,两遍$cdq$分治+单调队列维护凸包解决。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 50005

const long long inf = 1e18;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
inline double calc(int x1,int y1,int x2,int y2){if(x1==x2)return 1e18;return double(y2-y1)/(x2-x1);}
int ans[maxn];
long long mi[maxn],ma[maxn];
struct grade{
    int a,b;
    bool operator < (const grade &x)const{return a*x.b<b*x.a;}
}g[maxn];
struct operation{
    bool t;//0 insert  1 ask
    int id;
    long long x,y;//x:T   y:S
}A[maxn<<1],B[maxn<<1];
struct Monoqueue{
    int xx[maxn],yy[maxn],pos[maxn],head,tail;
    void clear(){head=1,tail=0;}
    void push1(int x,int y,int p){
        while(head<tail&&calc(xx[tail],yy[tail],xx[tail-1],yy[tail-1])>calc(xx[tail],yy[tail],x,y))--tail;
        xx[++tail]=x,yy[tail]=y,pos[tail]=p;
    }
    int front1(double k){
        while(head<tail&&calc(xx[head],yy[head],xx[head+1],yy[head+1])<k)++head;
        if(head<=tail)return pos[head];
        return -1;
    }
    void push2(int x,int y,int p){
        while(head<tail&&calc(xx[tail],yy[tail],xx[tail-1],yy[tail-1])<calc(xx[tail],yy[tail],x,y))--tail;
        xx[++tail]=x,yy[tail]=y,pos[tail]=p;
    }
    int front2(double k){
        while(head<tail&&calc(xx[head],yy[head],xx[head+1],yy[head+1])>k)++head;
        return pos[head];
    }
    Monoqueue(){clear();}
}q;
void cdq1(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,pl=l,pr=mid+1,p=l;
    cdq1(l,mid),q.clear();
    for(register int i=l;i<=mid;++i)if(!A[i].t)q.push1(A[i].x,A[i].y,A[i].id);
    for(register int i=mid+1;i<=r;++i){
        if(!A[i].t)continue;
        int j=q.front1((double)A[i].x/A[i].y);
        if(~j)mi[A[i].id]=min(mi[A[i].id],A[i].x*g[j].a-A[i].y*g[j].b);
    }
    cdq1(mid+1,r),q.clear();
    while(pl<=mid&&pr<=r){
        if(A[pl].x>A[pr].x||(A[pl].x==A[pr].y&&A[pl].y<A[pr].y))B[p++]=A[pl++];
        else B[p++]=A[pr++];
    }
    while(pl<=mid)B[p++]=A[pl++];
    while(pr<=r)B[p++]=A[pr++];
    for(register int i=l;i<=r;++i)A[i]=B[i];
}
void cdq2(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,pl=l,pr=mid+1,p=l;
    cdq2(l,mid),q.clear();
    for(register int i=l;i<=mid;++i)if(!A[i].t)q.push2(A[i].x,A[i].y,A[i].id);
    for(register int i=mid+1;i<=r;++i){
        if(!A[i].t)continue;
        int j=q.front2((double)A[i].x/A[i].y);
        if(~j)ma[A[i].id]=max(ma[A[i].id],A[i].x*g[j].a-A[i].y*g[j].b);
    }
    cdq2(mid+1,r),q.clear();
    while(pl<=mid&&pr<=r){
        if(A[pl].x>A[pr].x||(A[pl].x==A[pr].x&&A[pl].y>A[pr].y))B[p++]=A[pl++];
        else B[p++]=A[pr++];
    }
    while(pl<=mid)B[p++]=A[pl++];
    while(pr<=r)B[p++]=A[pr++];
    for(register int i=l;i<=r;++i)A[i]=B[i];
}
int main(){
    memset(mi,0x3f,sizeof mi),memset(ma,~0x3f,sizeof ma);
    long long s=0,t=0;
    int n=read(),cnt=0,len=0;
    for(register int i=1;i<=n;++i)g[i].a=read(),g[i].b=read();
    sort(g+1,g+1+n);
    for(register int i=n;i;--i){
        A[++len]=(operation){1,i,t,s};
        A[++len]=(operation){0,i,g[i].a,g[i].b};
        s+=g[i].a,t+=g[i].b;
    }
    cdq1(1,len);
    len=0;
    for(register int i=1;i<=n;++i){
        s-=g[i].a,t-=g[i].b;
        A[++len]=(operation){0,i,g[i].a,g[i].b};
        A[++len]=(operation){1,i,t,s};
    }
    cdq2(1,len);
    for(register int i=1;i<n;++i)if(ma[i]>mi[i])ans[++cnt]=i;
    printf("%d\n",cnt);
    for(register int i=1;i<=cnt;++i)printf("%d\n",ans[i]);
}