题解：P11994 [JOIST 2025] 外郎糕 / Uiro

· · 题解

P11994 [JOIST 2025] 外郎糕 / Uiro

考虑怎么解决一次询问。

有一个显然的 O(n\log n) 的做法，大致是先全部选成负的，然后从前往后扫，如果和小于 0 了就选最大的转正，用优先队列维护。

上面那个做法不好改进。观察部分分和数据范围发现，题目引导我们对 A_i 的值域进行思考。

考虑对于某个值 x，被选为负号的等于 x 的位置一定是所有等于 x 的位置里的一段后缀，否则改为同长度的后缀一定不劣。另外，考虑区间内最后一个没被选的 x-1，其位置一定小于第一个被选的 x，否则将这个 x 换成那个 x-1 一定不劣。

观察上面的性质，我们感性地猜测一个做法，从小到大枚举 x，对于 A_i=x 的位置，贪心选能选的最长后缀。

这是正确的，不妨考虑如果某一层 x 没有选满，那么找到 [x+1,100] 这几层中最靠前的选中位置 A_j，将其舍掉，替换成第一个没被选中的 A_i=x。那么前缀和在 [i,j-1] 部分是减少的，在 [j,n] 部分是增加的，后者显然不劣，前者不会造成任何其他影响（因为是一层一层往上贪心，所以这里的位置不会影响后面了）。

于是经过上面的调整可以证明，最优解一定能通过这种贪心得到。直接做，枚举 A 的值，枚举询问，二分。具体的实现是简单的，每一次需要处理前缀和，另外二分 check 的时候需要用到一个 ST 表查询区间最小值。复杂度是 O((n+q)\max A_i\log n) 的。这个复杂度在 loj 上能过，洛谷不太能过。我最后改了一版 O(q\max A_i\log n +n\log n) 的才通过，优化了建 ST 表时的复杂度，跑的快了很多，loj 上最慢跑了 800ms，洛谷最慢跑了 1.5s。

代码： 

#include<bits/stdc++.h>
using namespace std;
int n,Q,a[200003],q[200003][3],num[200003],pre[200003],lmt[200003],plsv[200003],lft,rgt,mid,f[200003];
int stk[200003],tots,k1,k2,k3,k4,k5,k6,k7,k8,k9,lg[200003],ST[200003][19],ST2[200003][19];
int Query(int ql,int qr){if(ql>qr)return 1000000000;return min(ST[ql][lg[qr-ql+1]],ST[qr-(1<<lg[qr-ql+1])+1][lg[qr-ql+1]]);}
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read(){
    int xx=0,ff=1;
    char ch=nc();
    while(ch<48||ch>57)ch=nc();
    while(ch>=48&&ch<=57)xx=xx*10+ch-48,ch=nc();
    return xx*ff;
}
void write(int x){
    if(x>9)write(x/10);
    putchar(x%10+'0');
    return;
}
int main(){
    for(int i=2;i<=200000;i++)lg[i]=lg[i>>1]+1;
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    Q=read();
    for(int i=1;i<=Q;i++){q[i][0]=read();q[i][1]=read();}
    for(int i=1;i<=Q;i++)lmt[i]=q[i][0];
    for(int nowv=1;nowv<=100;nowv++){
        tots=0;
        for(int i=1;i<=n;i++){
            num[i]=num[i-1]+(a[i]==nowv);
            if(a[i]==nowv)stk[++tots]=i;
            pre[i]=pre[i-1]+a[i];
            if(a[i]<nowv)pre[i]-=a[i]*2;
        }
        if(tots==0)continue;
        for(int i=1;i<=n;i++){
            f[i]=pre[i]-2*nowv*num[i];
            if(a[i]!=nowv)f[i]=min(f[i],f[i-1]);
        }
        for(int i=1;i<=tots;i++)ST[i][0]=f[stk[i+1]-1];
        for(int i=1;(1<<i)<=tots;i++){
            for(int j=1;j+(1<<i)-1<=tots;j++)ST[j][i]=min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
        }
        stk[tots+1]=n+1;
        for(int i=1;i<=Q;i++){
            lft=num[lmt[i]-1]+1;rgt=num[q[i][1]]+1;
            while(lft<rgt){
                mid=((lft+rgt)/2);
                if(Query(mid,num[q[i][1]]-1)>=pre[q[i][0]-1]-plsv[i]-2*nowv*(mid-1)&&f[q[i][1]]>=pre[q[i][0]-1]-plsv[i]-2*nowv*(mid-1))rgt=mid;
                else lft=mid+1;
            }
            q[i][2]+=(num[q[i][1]]-lft+1);
            lmt[i]=max(lmt[i],stk[lft-1]+1);
            plsv[i]+=((lft-1)-num[q[i][0]-1])*nowv*2;

        }
    }
    for(int i=1;i<=Q;i++){write(q[i][2]);putchar('\n');}
    return 0;
}