自动搬运

查看原文

来自洛谷，原作者为

	cwfxlh 会赢的！

搬运于2025-08-24 23:11:56，当前版本为作者最后更新于2025-06-12 21:56:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}