先把所有数减去最小值，防止负数出现问题。

$d=0$，直接$O(n)$扫过去即可。

$d\neq 0$，首先通过双指针求出每个数作为右端点时往左可以延伸到哪里，中间任意两个数差值都是$d$的倍数且不重复。

然后从左往右枚举右端点$i$，那么左端点$j$需要满足：

$\lfloor\frac{\max(a[j]..a[i])}{d}\rfloor-\lfloor\frac{\min(a[j]..a[i])}{d}\rfloor+j\leq k+i$

用线段树+单调栈进行$\max$和$\min$的更新，并维护区间内这个式子的最小值，然后在线段树上二分即可。

时间复杂度$O(n\log n)$。

 

#include
     
      #include
      
       const int N=200010,M=524300;int n,k,d,i,j,mi=~0U>>1,a[N],b[N],c[N],l[N],ap[N],cnt,q0[N],t0,q1[N],t1,t,L=1,R;inline void read(int&a){  char c;bool f=0;a=0;  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));  if(c!='-')a=c-'0';else f=1;  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';  if(f)a=-a;}inline void uans(int l,int r){if(r-l>R-L||r-l==R-L&&l
       
        >1]<=x)l=(t=mid)+1;else r=mid-1;  return t;}inline int abs(int x){return x>0?x:-x;}int ma[M],mb[M],mc[M],mac[M],mbc[M],mabc[M],ta[M],tb[M];inline int min(int a,int b){return a
        
         >1;  build(x<<1,a,mid),build(x<<1|1,mid+1,b);}void changea(int x,int a,int b,int c,int d,int p){  if(c<=a&&b<=d){taga(x,p);return;}  pb(x);  int mid=(a+b)>>1;  if(c<=mid)changea(x<<1,a,mid,c,d,p);  if(d>mid)changea(x<<1|1,mid+1,b,c,d,p);  up(x);}void changeb(int x,int a,int b,int c,int d,int p){  if(c<=a&&b<=d){tagb(x,p);return;}  pb(x);  int mid=(a+b)>>1;  if(c<=mid)changeb(x<<1,a,mid,c,d,p);  if(d>mid)changeb(x<<1|1,mid+1,b,c,d,p);  up(x);}void dfs(int x,int a,int b,int p){  if(a==b){t=a;return;}  pb(x);  int mid=(a+b)>>1;  if(mabc[x<<1]<=p)dfs(x<<1,a,mid,p);else dfs(x<<1|1,mid+1,b,p);  up(x);}void ask(int x,int a,int b,int c,int d,int p){  if(t)return;  if(c<=a&&b<=d){    if(mabc[x]<=p)dfs(x,a,b,p);    return;  }  pb(x);  int mid=(a+b)>>1;  if(c<=mid)ask(x<<1,a,mid,c,d,p);  if(d>mid)ask(x<<1|1,mid+1,b,c,d,p);  up(x);}int main(){  read(n),read(k),read(d);  for(i=1;i<=n;i++){    read(a[i]);    if(a[i]
         
          a[i])t1--;    changeb(1,1,n,q1[t1]+1,i,-a[i]/d);    q1[++t1]=i;    t=0,ask(1,1,n,l[i],i,k+i);    uans(t,i);  }  return printf("%d %d",L,R),0;}