题目概述

xay loves sequence

解题报告

先对数组差分，令 $c_i=a_i-a_{i-1}$ 。每次区间加或者区间减就是对 $c$ 的两个位置 $+1$ 和 $-1$ ，所以不难发现答案为 $\sum_{i=1}^{n+1}|c_i|\over 2$ 。

如果没有对 $K$ 取模，我们利用 $|c_i|$ 的前缀和就可以方便的得出答案。但是在取模意义下，$c_i$ 实际上可以进行 $+K$ 和 $-K$ 操作。

由于保证了所有 $a_i<K_{max}$​​ ，因此对每个 $a_i$​​ ，我们至多进行一次 $-K$ ，然后将问题转化为不在模意义下。我们考虑最终的情况，$-K$ 的 $a_i$ 会形成若干个不相交的区间，转换到 $c$ 上就等价于选 $2t$​​ 个位置，$t$ 个位置进行 $-K$ ，$t$ 个位置进行 $+K$ ，且 $+K$ 和 $-K$ 的位置不能重复。

根据贪心，我们不可能把 $c_i<0$ 的位置 $-K$ ，$c_i>0$ 的位置 $+K$ ，所以只需要分两种情况考虑：

• $c_i<0$​​ 进行 $+K$​​ ：$|c_i|\to|K+c_i|$​​ ，增加了 $K+c_i-|c_i|=K-2|c_i|$​​
• $c_i\ge 0$ 进行 $-K$ ：$|c_i|\to|c_i-K|$ ，增加了 $K-c_i-|c_i|=K-2|c_i|$

暴力做法就是枚举 $t$ ，然后在两种情况中分别选出最小的 $t$ 个 $K-2|c_i|$ 之后，加上最初的贡献就可以得出 $t$​ 的答案，转化一下就是最大的 $t$ 个 $|c_i|$ 。

不难发现随着 $t$ 增大，最小的 $t$ 个 $K-2|c_i|$ 之和是单谷的（ $K-2|c_i|$ 从负变为正），因此 $t$ 的答案是单峰的，可以二分找出最优 $t$ 。

为了快速查找最大的 $t$ 个 $|c_i|$ ，我们用权值主席树得出 $[L,R]$​ 中的权值情况即可。

注意每次查询 $[L,R]$ 时，$c_L$ 和 $c_{R+1}$ 会发生改变，可以新建两棵树来维护。

复杂度 $O(q\log_2n\log_210^9)$​ 。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=4e7;

int n,te,a[maxn+5],c[maxn+5],lim;LL tem[maxn+5];
int pl,ro[2][maxn+5],ls[maxt+5],rs[maxt+5],si[maxt+5];LL sum[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
#define abs(x) ((x)<0?-(x):(x))
inline int newnode(int a,int b,int c,LL d) {pl++;ls[pl]=a;rs[pl]=b;si[pl]=c;sum[pl]=d;return pl;}
int Insert(int p,int pos,int l=0,int r=lim){
    int now=newnode(ls[p],rs[p],si[p],sum[p]);
    if (l==r) {si[now]++;sum[now]+=l;return now;}
    int mid=l+(r-l>>1);
    pos<=mid?ls[now]=Insert(ls[p],pos,l,mid):rs[now]=Insert(rs[p],pos,mid+1,r);
    si[now]=si[ls[now]]+si[rs[now]];sum[now]=sum[ls[now]]+sum[rs[now]];
    return now;
}
LL Sum(int A,int B,int K,int l=0,int r=lim){
    if (!K) return 0;if (si[B]-si[A]==K) return sum[B]-sum[A];
    if (l==r) return (LL)K*l;
    int mid=l+(r-l>>1);
    if (si[rs[B]]-si[rs[A]]>=K) return Sum(rs[A],rs[B],K,mid+1,r);
    else return sum[rs[B]]-sum[rs[A]]+Sum(ls[A],ls[B],K-(si[rs[B]]-si[rs[A]]),l,mid);
}
int main(){
    readi(n);readi(te);
    for (int i=1;i<=n;i++){
        readi(a[i]);c[i]=a[i]-a[i-1];tem[i]=tem[i-1]+abs(c[i]);
        lim=max(lim,abs(c[i]));lim=max(lim,a[i]);
    }
    for (int i=1;i<=n;i++){
        ro[0][i]=ro[0][i-1];ro[1][i]=ro[1][i-1];
        ro[c[i]<0][i]=Insert(ro[c[i]<0][i],abs(c[i]));
    }
    for (int L,R,K;te;te--){
        readi(L);readi(R);readi(K);
        int A=Insert(ro[0][R],a[L]),B=Insert(ro[1][R],a[R]);
        int l=0,r=min(si[A]-si[ro[0][L]]-1,si[B]-si[ro[1][L]]-1);
        for (int mid=l+(r-l>>1);l<=r;mid=l+(r-l>>1)){
            LL resl=(LL)K*mid*2-Sum(ro[0][L],A,mid)*2-Sum(ro[1][L],B,mid)*2;
            LL resr=(LL)K*(mid+1)*2-Sum(ro[0][L],A,mid+1)*2-Sum(ro[1][L],B,mid+1)*2;
            resl<=resr?r=mid-1:l=mid+1;
        }
        LL ans=tem[R]-tem[L]+a[L]+a[R]+(LL)K*l*2-Sum(ro[0][L],A,l)*2-Sum(ro[1][L],B,l)*2;
        printf("%lld\n",ans>>1);
    }
    return 0;
}