P11989 题解

· · 题解

Problem Link

首先难度确定是就是朴素贪心，每个时刻弹出最大值可以做到 \mathcal O(n\log n)。

但另一种等价的做法就是按 p 从大到小考虑每个怪兽，尽可能向后一直打该怪兽，用并查集维护非空段，时间复杂度 \mathcal O(n)。

可以猜测难度在 1\sim L 的变化过程中有很多时刻变化量相同，我们生成答案关于难度的函数是 \mathcal O(n) 段的凸壳。

那么我们可以每次二分找到当前段的范围，可以做到 \mathcal O(n^2\log L)，回答可以双指针 \mathcal O(q+L)。

但是这无法通过，进一步观察，如果难度 k-1\to k,k\to k+1 变化量相同，那么可以猜测每种怪兽被攻击次数变化量相同，那么每个怪兽被打的次数是一次函数，我们检验的时候只要判断每个后缀中点数是否不超过后缀大小，可以直接计算出最大合法时刻，所以可以 \mathcal O(n) 求出斜率区间。

需要精细实现。

时间复杂度 \mathcal O(n^2+q+L)。

正解是把答案拆成对每个 k 把权值看成 [p_i\ge k] 求和，变成最大匹配后用 Hall 定理刻画。

代码：

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
namespace IO {
int ow,olim=(1<<21)-100;
char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<21];
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll read() {
    ll x=0; char c=gc();
    while(!isdigit(c)) c=gc();
    while(isdigit(c)) x=x*10+(c^48),c=gc();
    return x;
}
void flush() {
    fwrite(obuf,ow,1,stdout),ow=0;
}
void write(ll x) {
    if(!x) obuf[ow++]='0';
    else {
        int t=ow;
        for(;x;x/=10) obuf[ow++]=(x%10)^48;
        reverse(obuf+t,obuf+ow);
    }
    if(ow>=olim) flush();
}
void putc(char c) {
    obuf[ow++]=c;
    if(ow>=olim) flush();
}
#undef gc
}
const int MAXN=6005,MAXM=1e7+5;
const ll inf=2e18;
struct item {
    ll t,h,w;
}   a[MAXN];
int n,m,q,dsu[MAXN],id[MAXN];
ll f[MAXM],g[MAXN],t[MAXN],h[MAXN];
ull sg[MAXN];
int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
int qry(int x) {
    int y=x>>6,r=x&63;
    if(sg[y]>>r) return __builtin_ctzll(sg[y]>>r)+x;
    y=find(y+1);
    return y<<6|__builtin_ctzll(sg[y]);
}
void sol(ll k) {
    int b=(n>>6)+1;
    for(int i=0;i<=b;++i) dsu[i]=i,sg[i]=-1;
    for(int i=1;i<=n;++i) g[i]=a[i+1].t-a[i].t;
    for(int o=1,i;o<=n;++o) {
        ll c=a[i=id[o]].h*k;
        for(int x=qry(i),y;x<=n&&c;) {
            if(c>=g[x]) {
                c-=g[x],g[x]=0,sg[y=(x>>6)]^=1ll<<(x&63);
                if(!sg[y]) dsu[y]=y+1;
                x=qry(x);
            }
            else g[x]-=c,c=0;
        }
        h[i]=a[i].h*k-c;
    }
}
signed main() {
    n=IO::read(),m=IO::read(),a[n+1].t=IO::read();
    ll S=0;
    for(int i=1;i<=n;++i) a[i].t=IO::read(),a[i].h=IO::read(),a[i].w=IO::read(),S+=a[i].h*a[i].w,id[i]=i;
    sort(a+1,a+n+1,[&](auto x,auto y) { return x.t<y.t; });
    sort(id+1,id+n+1,[&](int x,int y){ return a[x].w>a[y].w; });
    for(int p=1;p<=m;) {
        sol(p),f[p]=0;
        for(int i=1;i<=n;++i) f[p]+=h[i]*a[i].w;
        ll k=0,b=0,x=m-p,y=1;
        auto upd=[&](ll u,ll v) { if((__int128)u*y<(__int128)x*v) x=u,y=v; };
        for(int i=n;i>=1;--i) {
            b+=a[i+1].t-a[i].t;
            k+=h[i]-t[i],b-=h[i];
            if(k>0) upd(b,k);
            if(h[i]-t[i]>a[i].h) upd(a[i].h*p-h[i],h[i]-t[i]-a[i].h);
            else if(h[i]-t[i]<0) upd(h[i],t[i]-h[i]);
            if(x<y) break;
        }
        ll d=x/y;
        for(int i=p+1;i<=p+d;++i) f[i]=f[i-1]+f[p]-f[p-1];
        for(int i=1;i<=n;++i) t[i]=h[i]+d*(h[i]-t[i]);
        p+=d+1;
    }
    f[m+1]=inf;
    for(int i=m;~i;--i) f[i]=min(f[i+1],S*i-f[i]);
    q=IO::read();
    for(int i=0;q--;) {
        ll z=IO::read();
        while(i<m&&f[i+1]<=z) ++i;
        IO::write(i),IO::putc('\n');
    }
    IO::flush();
    return 0;
}