P14462 【MX-S10-T3】『FeOI-4』寻宝游戏
P14462 【MX-S10-T3】『FeOI-4』寻宝游戏 - 洛谷 (luogu.com.cn)
分类讨论。
-
\(len\ge 3\)。
找到一个目标桶 \(x\)，把剩下的都扔进去。
设剩下的桶之中，个数和为 \(sum\)，最大的有 \(mx\) 个。
-
\(sum\) 为偶数。
可以直接向 \(x\) 里扔。一个下界为 \(\max(sum/2,mx)\)，考虑构造出这个下界：
- 若 \(sum/2\ge mx\)，每次拿出最大和次大的向 \(x\) 扔，一定可行。
- 否则，先不断地拿 \(mx\) 和其他一个桶向一个空桶扔，直到 \(sum/2\ge mx\)，需要 \(mx\) 次操作。
-
\(sum\) 为奇数。
-
\(x\) 不是空桶。
先拿出 \(x\) 和 \(mx\) 向空桶扔，然后变为上面的问题。
设 \(x\) 剩下的桶中次大值为 \(se\)。
- 若 \(mx=se\)，答案为 \(\max((sum+1)/2,mx,2)+1\)；
- 否则，答案为 \(\max((sum+1)/2,mx-1,2)+1\)。
-
\(x\) 是空桶
讨论起来就麻烦很多，但答案只会是 \(\max((sum-1)/2,mx-d,2)+2\)，其中 \(d\in \{0,1,2\}\)。
无论 \(d\) 取何值，都不比选一个非空桶优，所以不需要考虑。
-
-
-
\(len=1\)，平凡。
-
\(len=2\)。
设两个桶里有 \(x,y\) 个，不妨设 \(x\le y\)。
首先只有两个桶是没办法做的，需要一个空桶转换为 \(len\ge 3\) 的情况。
- \(x=1,y=1\)，答案为 \(1\)。
- \(x=1,y=2\)，无解。
- \(x>1\)，用一步操作变为 \(x-1,y-1,2\)。
- \(x=1\)，用两步操作变为 \(2,y-2,1\)。
- 若 \(x+y\) 为偶数，答案还要考虑 \(\max((x+y)/2,x,y)\)。
对于 \(len\ge 3\) 的情况，只有区间最大值和严格次大值有可能成为目标。st 表或线段树均可。
int n,m,a[N];
ll s[N];struct Info{int f,pf,g,pg,h; //最大值，出现位置，严格次大值，出现位置，非严格次大值friend Info operator + (Info x,Info y){Info z;if(x.f==y.f){z.f=x.f,z.pf=x.pf;if(x.g>=y.g) z.g=x.g,z.pg=x.pg;else z.g=y.g,z.pg=y.pg;z.h=y.f;}else if(x.f>y.f){z.f=x.f,z.pf=x.pf;if(x.g>=y.f) z.g=x.g,z.pg=x.pg;else z.g=y.f,z.pg=y.pf;z.h=max(x.h,y.f);}else{z.f=y.f,z.pf=y.pf;if(y.g>=x.f) z.g=y.g,z.pg=y.pg;else z.g=x.f,z.pg=x.pf;z.h=max(y.h,x.f);}return z;}
}tr[N<<2];void Buildtr(int p,int l,int r){if(l==r){tr[p].f=a[l],tr[p].h=-IINF;tr[p].pf=l,tr[p].g=-IINF,tr[p].pg=-1;return;}int mid=(l+r)>>1;Buildtr(p<<1,l,mid),Buildtr(p<<1|1,mid+1,r);tr[p]=tr[p<<1]+tr[p<<1|1];
}Info Ask(int p,int l,int r,int L,int R){if(L>R) return Info{-IINF,-1,-IINF,-1,-IINF};if(L<=l&&r<=R) return tr[p];int mid=(l+r)>>1;if(L<=mid&&mid<R)return Ask(p<<1,l,mid,L,R)+Ask(p<<1|1,mid+1,r,L,R);else if(L<=mid) return Ask(p<<1,l,mid,L,R);else return Ask(p<<1|1,mid+1,r,L,R);
} ll Calc(int x,int y){if((x+y)%2==0) return max((x+y)>>1,max(x,y));else{int mx=max(x,y),se=min(x,y);if(mx==se) return max((x+y+1)>>1,max(mx,2))+1;else return max((x+y+1)>>1,max(mx-1,2))+1;}
}ll Work0(int l,int r){if(a[l]==1&&a[r]==1) return 1;else if(a[l]==1&&a[r]==2) return -1;else if(a[l]==2&&a[r]==1) return -1;ll A=a[l],B=a[r],C=0,ans=0,res=LINF;if(A>B) swap(A,B);if(A==1) A=2,B-=2,C=1,ans=2;else --A,--B,C=2,ans=1;if((A+B+C)%2==0)Ckmin(res,max((A+B+C)>>1,max({A,B,C})));Ckmin(res,Calc(A,B));Ckmin(res,Calc(A,C));Ckmin(res,Calc(B,C));ans+=res; return ans;
}ll Work1(int l,int r){ll mx,se,sum,ans=LINF;Info all=Ask(1,1,n,l,r),res;int P=all.pf,Q=all.pg;if((s[r]-s[l-1])%2==0) Ckmin(ans,max((s[r]-s[l-1])>>1,(ll)all.f));res=Ask(1,1,n,l,P-1)+Ask(1,1,n,P+1,r);mx=res.f,se=res.h,sum=s[r]-s[l-1]-a[P];if(sum%2==0) Ckmin(ans,max(sum>>1,mx));else if(mx==se) Ckmin(ans,max((sum+1)>>1,max(mx,2ll))+1);else Ckmin(ans,max((sum+1)>>1,max(mx-1,2ll))+1);if(Q==-1) return ans;res=Ask(1,1,n,l,Q-1)+Ask(1,1,n,Q+1,r);mx=res.f,se=res.h,sum=s[r]-s[l-1]-a[Q];if(sum%2==0) Ckmin(ans,max(sum>>1,mx));else if(mx==se) Ckmin(ans,max((sum+1)>>1,max(mx,2ll))+1);else Ckmin(ans,max((sum+1)>>1,max(mx-1,2ll))+1);return ans;
}void Solve(){read(n),read(m);for(int i=1;i<=n;i++){read(a[i]);s[i]=s[i-1]+a[i];}Buildtr(1,1,n);while(m--){int l,r; read(l),read(r);if(l==r) puts("0");else if(l+1==r) printf("%lld\n",Work0(l,r));else printf("%lld\n",Work1(l,r));}
}signed main(){int T; read(T);while(T--) Solve();return 0;
}