先特判d=0的情况 然后对于d≠0： 若a[i]和a[i+1]的差不是d的倍数，即a[i]和a[i+1]在模d下不等，那么他们肯定不会在同一个kd串中，将中间断开 于是得到了若干个原串的子串
数列中不能有相同的数（还是挺好处理的吧），下文的叙述省略了数列中有相同的数的处理
因为每个串内的数在模d下相同，所以先将他们全部/d（这样方便处理） 因为l~r中没有相同的数，那么这个数列若要成为kd数列，需要插入的值的个数是(max-min-r+l) 于是每个串内维护2个单调栈，一个单调升一个单调降 开一个线段树维护每个位置到当前的i，需要插入的值的个数，在序列右边插入一个数的时候，在两个单调栈上找他会影响到的区间，线段树上修改，然后将这个值插入单调栈，每个位置找到最左的l使得需要插入的值个数<=k，每个串都这样处理找最长的子串
话说大视野的数据真的挺弱的，cf上有一道一样的题，我在大视野过了在cf上没过（数列中相同的数那里没处理好），在bzoj上过了可以去那边试一下 （我知道我代码有错懒得改了…求不hack…）
code：
#include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<cmath> #include<ctime> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<climits> #include<complex> #include<iostream> #include<algorithm> #define ll long long #define inf 1e9 using namespace std; inline void read(int &x) { char c; int f=1; while(!((c=getchar())>='0'&&c<='9')) if(c=='-') f=-f; x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0'; x*=f; } const int maxn = 210000; int n,K,D; int ansx,ansl; int a[maxn],d[maxn]; struct segment { int lc,rc,c,f; }seg[maxn<<2]; int tot,root; void clear(int &x) { if(seg[x].lc) clear(seg[x].lc); if(seg[x].rc) clear(seg[x].rc); seg[x].f=seg[x].c=0; x=0; } void pushdown(const int x) { if(!seg[x].f) return; if(!seg[x].lc) seg[x].lc=++tot; if(!seg[x].rc) seg[x].rc=++tot; seg[seg[x].lc].f+=seg[x].f; seg[seg[x].lc].c+=seg[x].f; seg[seg[x].rc].f+=seg[x].f; seg[seg[x].rc].c+=seg[x].f; seg[x].f=0; } int lx,rx,c; void upd(int &x,const int l,const int r) { if(rx<l||r<lx) return; if(!x) x=++tot; if(lx<=l&&r<=rx) { seg[x].f+=c; seg[x].c+=c; return; } pushdown(x); int mid=l+r>>1; upd(seg[x].lc,l,mid); upd(seg[x].rc,mid+1,r); seg[x].c=min(seg[seg[x].lc].c,seg[seg[x].rc].c); } int query(const int x,const int l,const int r) { if(seg[x].c>c) return 0; if(l==r) return l; pushdown(x); int mid=l+r>>1; if(seg[seg[x].lc].c<=c) return query(seg[x].lc,l,mid); else return query(seg[x].rc,mid+1,r); } map<int,int>h; int u[maxn],ul,dn[maxn],dl; void solve(int l,int r) { if(l>=r) return; clear(root); tot=0; seg[0].c=inf; dn[0]=l-1; u[0]=l-1; dl=ul=0; for(int i=l;i<=r;i++) { lx=rx=i; c=i; upd(root,l,r); int la=i; while(dl&&a[dn[dl]]<a[i]) { c=a[i]-a[dn[dl]]; lx=dn[dl-1]+1,rx=la-1; la=lx; if(lx<=rx) upd(root,l,r); dl--; } dn[++dl]=i; la=i; while(ul&&a[u[ul]]>a[i]) { c=a[u[ul]]-a[i]; lx=u[ul-1]+1,rx=la-1; la=lx; if(lx<=rx) upd(root,l,r); ul--; } u[++ul]=i; c=i+K; int tmp=query(root,l,r); if(tmp&&i-tmp+1>ansl) ansl=i-tmp+1,ansx=tmp; } } int main() { read(n); read(K); read(D); for(int i=1;i<=n;i++) { read(a[i]),a[i]+=1e9; if(D) d[i]=a[i]%D,a[i]/=D; } ansx=1; ansl=1; if(!D) { int l=1,r=0; for(r=1;r<=n;r++) { if(l!=r&&a[r]!=a[r-1]) l=r; if(r-l+1>ansl) ansl=r-l+1,ansx=l; } } else { d[0]=d[1]; d[n+1]=d[n]+1; int la=1; for(int i=1;i<=n+1;i++) { if(d[i]!=d[i-1]) { h.clear(); solve(la,i-1); la=i; } else if(h.count(a[i])>0) { solve(la,i-1); la=max(la,h[a[i]]+1); } h[a[i]]=i; } } printf("%d %d\n",ansx,ansx+ansl-1); return 0; }