题解：P12969 [CCO 2025] Restaurant Recommendation Rescue

· · 题解

现在两篇题解都不知道在说什么，而且做复杂了。真难蚌。

把输入的数 -1，等价于如下问题：

给定一个整数序列 a，满足 \sum\limits_{i=1}^n a_i=-1，若和不为 -1 全输出 0 0 即可。

定义 f(a)=\sum\limits_{x=1}^n g(a,x)。

将 a 右移 x 位，并且去掉最后一个数。

若 a 的所有前缀和非负，则 g(a,x)=w_x。否则 g(a,x)=0。

注意到循环位移前缀和有结论，设序列 a 的前缀和为 b，s=b_n。

循环位移 1 位的前缀和为：[b_2-b_1,b_3-b_1,\cdots,b_n-b_1,s]

循环位移 2 位的前缀和为：[b_3-b_2,b_4-b_2,\cdots,b_n-b_2,s+b_1-b_2,s]。

循环位移 3 位的前缀和为：[b_4-b_3,b_5-b_3,\cdots,b_n-b_3,s+b_1-b_3,s+b_2-b_3,s]。

循环位移 k 位的前缀和为：[b_{k+1\sim n}-b_k,s+b_{1\sim k-1}-b_k,s]。

对于这题，s=-1。

右移 x 位，前缀和非负相当于 \forall i\neq x,b_i-b_x-[i<x]\ge 0。

取 b 最靠左侧的最小值，位置为 p。则满足条件的 x 一定只能是 p。

若 x\neq p，取 i=p 矛盾。

若 x=p，无论 i 如何取值都能保证 \ge 0。

交换两个数 x\le y 相当于两次单点修改，对于前缀和的影响就是区间 [x,y-1] 加 a_{x}-a_{y}。

线段树维护区间加，最靠左侧的最小值。复杂度 \mathcal{O}(n\log n)。

::::info[\mathbf{code}]

#include<bits/stdc++.h>
#define LL long long
#define P pair<LL,LL>
#define fi first
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=5e5+5;
int n,m,a[N];LL s[N],lt[N<<2];P A[N<<2];
#define ls w<<1
#define rs ls|1
#define lw l,m,ls
#define rw m+1,r,rs
inline void upd(int w,LL x){A[w].fi+=x,lt[w]+=x;}
inline void pd(int w){LL &t=lt[w];if(t) upd(ls,t),upd(rs,t),t=0;}
void bd(int l=1,int r=n,int w=1)
{
    if(l==r) return A[w]={s[l],l},void();
    int m=(l+r)>>1;bd(lw);bd(rw);A[w]=min(A[ls],A[rs]);
}
void UPD(int L,int R,LL x,int l=1,int r=n,int w=1)
{
    if(L<=l&&r<=R) return upd(w,x);
    int m=(l+r)>>1;pd(w);
    if(L<=m) UPD(L,R,x,lw);
    if(m<R) UPD(L,R,x,rw);A[w]=min(A[ls],A[rs]);
}
inline void get(){int p=A[1].second;cout<<"1 "<<(p==n?0:p)<<"\n";}
int main()
{
    cin.tie(0)->sync_with_stdio(0);cout.tie(0);cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+(--a[i]);
    if(s[n]!=-1){
        for(m++;m--;) puts("0 0");return 0;
    }bd();get();
    for(int x,y;m--;)
    {
        cin>>x>>y;if(++x>++y) swap(x,y);
        if(x<y) UPD(x,y-1,a[y]-a[x]);
        swap(a[x],a[y]),get();
    }
    return 0;
}
::::