题目概述

有 $n$ 个数，求最长的子区间使得添加 $K$ 个数，排序之后得到一个公差为 $D$ 的等差数列。

解题报告

我太斯波了，式子都没仔细看就写了个二分，显然不满足单调性……

一个区间 $[L,R]$ 要满足需要：1.同余 $D$ 。2.没有相同的数。3. ${Max-Min\over D}-(R-L)\le K$ 。

前两个条件我们可以two-pointer一下得到 $L$ 能够达到的最右边 $r_L$ ，然后就是后面的式子，我们变形一下就是：$Max-Min-DR\le D(K-L)$ 。

枚举左端点，然后用线段树维护 $Max-Min-DR$ 的最小值，在线段树上二分就可以得到最远的 $R(R\le r_L)$ 。如何维护 $Max$ 和 $Min$ ？用一个单调栈就行了。

ps：特判 $D=0$ ……

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000;

int n,K,D,a[maxn+5],b[maxn+5],tem[maxn+5],r[maxn+5],ans,AL,AR;bool vis[maxn+5];
int top[2],stk[2][maxn+5],R[2][maxn+5];LL MIN[(maxn<<2)+5],tag[(maxn<<2)+5];

inline int Find(int x,int L=1,int R=tem[0]){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        if (x==tem[mid]) return mid; else x<tem[mid]?R=mid-1:L=mid+1;
}
inline void OrzZH(){
    int ans=1,L=1,R=1,lst=1;
    for (int i=2;i<=n;i++) if (a[i-1]!=a[i]) {if (i-lst>ans) ans=i-lst,L=lst,R=i-1;lst=i;}
    if (n-lst+1>ans) L=lst,R=n;printf("%d %d\n",L,R);
}
inline void Addtag(int p,LL k) {MIN[p]+=k;tag[p]+=k;}
inline void Pushdown(int p) {if (tag[p]) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),tag[p]=0;}
#define Pushup(p) (MIN[p]=min(MIN[(p)<<1],MIN[(p)<<1|1]))
void Insert(int L,int R,LL k,int l=1,int r=n,int p=1){
    if (L==l&&r==R) return Addtag(p,k);int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Insert(L,R,k,l,mid,p<<1); else if (L>mid) Insert(L,R,k,mid+1,r,p<<1|1);
    else Insert(L,mid,k,l,mid,p<<1),Insert(mid+1,R,k,mid+1,r,p<<1|1);Pushup(p);
}
inline void Push(int x,int lst=0){
    lst=x;while (top[0]&&stk[0][top[0]]>a[x]) Insert(lst+1,R[0][top[0]],stk[0][top[0]]-a[x]),lst=R[0][top[0]--];
    stk[0][++top[0]]=a[x];R[0][top[0]]=lst;
    lst=x;while (top[1]&&stk[1][top[1]]<a[x]) Insert(lst+1,R[1][top[1]],a[x]-stk[1][top[1]]),lst=R[1][top[1]--];
    stk[1][++top[1]]=a[x];R[1][top[1]]=lst;
}
int Ask(int L,int R,LL k,int l=1,int r=n,int p=1){
    if (R<l||r<L) return -1;if (l==r) return l;int mid=l+(r-l>>1);Pushdown(p);
    int pos=-1;if (MIN[p<<1|1]<=k) pos=Ask(L,R,k,mid+1,r,p<<1|1);
    if (pos<0&&MIN[p<<1]<=k) pos=Ask(L,R,k,l,mid,p<<1);return pos;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&K,&D);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    if (!D) return OrzZH(),0;for (int i=1;i<=n;i++) b[i]=(a[i]%D+D)%D;
    tem[0]=0;for (int i=1;i<=n;i++) tem[++tem[0]]=a[i];sort(tem+1,tem+1+tem[0]);
    tem[0]=unique(tem+1,tem+1+tem[0])-tem-1;for (int i=1;i<=n;i++) a[i]=Find(a[i]);
    for (int i=1,j=0;i<=n;vis[a[i]]=false,r[i++]=j) while (j<n&&b[i]==b[j+1]&&!vis[a[j+1]]) vis[a[++j]]=true;
    for (int i=1;i<=n;i++) a[i]=tem[a[i]];ans=1;AL=n;AR=n;Insert(n,n,(LL)-D*n);Push(n);
    for (int i=n-1;i;i--){
        Insert(i,i,(LL)-D*i);Push(i);if (MIN[1]>(LL)D*(K-i)) continue;
        int pos=Ask(i,r[i],(LL)D*(K-i));if (pos-i+1>=ans) ans=pos-i+1,AL=i,AR=pos;
    }return printf("%d %d\n",AL,AR),0;
}