Description

Given a length of n n sequence of n A A A. Find the longest subinterval such that the subinterval joins at most k k After k numbers, after sorting is a tolerance of d d Arithmetic sequence of d.

Multiple solution outputs l l l the smallest.

1 ≤ n ≤ 2 × 1 0 5 1 \le n \le 2 \times 10^5 1≤n≤2×105

Solution

title conversion

First, we judge d = 0 d=0 d=0 case.

Consider what is the equivalent condition for an interval to satisfy the requirement.

① All numbers in this interval are different from each other;
②All numbers in this interval are modulo d d d is congruent in the sense;
③Add in no more than k k k numbers can turn it into a tolerance of d d Arithmetic sequence of d.

This ③ seems a bit abstract, we try to express it formally.

Make this interval meet the requirements [ l , r ] [l,r] The maximum value of [l,r] is m a x v maxv maxv , the minimum value is m i n v minv minv , then ③ can be written as
m a x v − m i n v d + 1 − ( r − l + 1 ) ≤ k \frac {maxv-minv} {d}+1-(r-l+1) \le k dmaxv−minv​+1−(r−l+1)≤k

here m a x v − m i n v d + 1 \frac {maxv-minv} {d}+1 dmaxv−minv​+1 indicates how long this interval should be after the supplement is complete, r − l + 1 r-l+1 r−l+1 represents the existing length of the interval; obviously, the subtraction of the two is the number of numbers that should be added. At the same time, this value must not exceed k k k .

property analysis

We consider how to deal with these limitations.

For ①, we need for each r r r , find the smallest l = x r l=x_r l=xr​ so that [ l , r ] [l,r] The numbers in [l,r] are different from each other. This can be obtained by recursion.

For ②, we need for each r r r , find a minimum l = y r l=y_r l=yr​ so that [ l , r ] [l,r] [l,r] All numbers are identical in the modular sense. This can be obtained by linear scanning.

Let under the conditions ① and ②, the right endpoint r r The farthest left endpoint to which r can be extended is l i m i t r limit_r limitr​ . Easy to find, l i m i t r = m a x ( x r , y r ) limit_r=max(x_r,y_r) limitr​=max(xr​,yr​) , and for all satisfying l i m i t r ≤ l ≤ r limit_r \le l \le r limitr​≤l≤r l l l ， [ l , r ] [l,r] [l,r] both conform to ①②.

Now that ① and ② are solved, I think about how to solve ③. We enumerate the right endpoint r r r , and simplify the formula:

m a x v − m i n v d + l ≤ k + r \frac {maxv-minv} {d}+l \le k+r dmaxv−minv​+l≤k+r

Since a section conforms to ①② [ l , r ] [l,r] The numbers in [l,r] are congruent in the modulo sense, so we can write a a Divide all the numbers in a by d d d (rounded down). So the formula becomes:

m a x v − m i n v + l ≤ k + r maxv-minv+l \le k+r maxv−minv+l≤k+r

So, the key now is how to quickly maintain ⌊ \lfloor ⌊ Dynamically query the minimum satisfaction max ⁡ l ≤ i ≤ r { a i } − min ⁡ l ≤ i ≤ r { a i } + l ≤ k + r \max_{l \le i \le r}\{a_i \}-\min_{l \le i \le r}\{a_i \}+l \le k+r maxl≤i≤r​{ai​}−minl≤i≤r​{ai​}+l≤k+r l l l ⌉ \rceil ⌉ .

We consider maintaining two monotonic stacks, corresponding to the maximum and minimum values, respectively. The following takes the maximum value as an example.

In a monotonic stack, we maintain a p a i r pair pair , that is, weight and position. As shown below.

Obviously, in a monotonic stack representing the maximum value, the weights decrease and the positions increase. Let these positions from left to right be p 1 , p 2 , p 3 ⋯ p_1,p_2,p_3 \cdots p1​,p2​,p3​⋯ , the weights are v 1 , v 2 , v 3 ⋯ v_1,v_2,v_3 \cdots v1​,v2​,v3​⋯ . At the same time, we maintain a line segment tree in real time. j j The j positions represent the interval [ j , r ] [j,r] Maximum value of [j,r]. make it s j s_j sj​ .

consider joining r r After r, how the monotonic stack should be maintained. Obviously, we need to pop some top elements to maintain decrement. We keep popping the top element of the stack ( p t o p , v t o p ) (p_{top},v_{top}) (ptop​,vtop​). because of the satisfied ∀ j ∈ [ p t o p , r ] max ⁡ j ≤ k ≤ r { a k } = v t o p \forall j \in [p_{top},r] \max_{j \le k \le r} \{a_k\}=v_{top} ∀j∈[ptop​,r]maxj≤k≤r​{ak​}=vtop​ is no longer satisfied, so we perform an interval modification, changing the s s All s values ​​are cleared 0 0 0 . satisfying all v t o p ≤ a r v_{top} \le a_r After all the elements of vtop​≤ar​ are popped up, we need to add a 2-tuple ( r , a r ) (r,a_r) (r,ar​) ; at the same time, we perform another single-point modification, which will s r s_r sr​ is updated to a r a_r ar​ . The maintenance of the minimum value is the same.

After the monotonic stack is maintained, we need to find the l i m i t r ≤ i ≤ r limit_r \le i \le r limitr​≤i≤r and max ⁡ l ≤ i ≤ r { a i } − min ⁡ l ≤ i ≤ r { a i } + l ≤ k + r \max_{l \le i \le r}\{a_i \}-\min_{l \le i \le r}\{a_i \}+l \le k+r The smallest of maxl≤i≤r​{ai​}−minl≤i≤r​{ai​}+l≤k+r l l l. This can be obtained by bisection on the line segment tree. Finally, we use the interval [ l , r ] [l,r] [l,r] update answer, and continue enumeration r r r .

In terms of details, we need to build the line segment tree before enumerating the right endpoint; l l The initial value of the l positions is l l l (because the formula of ③ contains l l l). At the same time, when dividing negative numbers by d d d (round down), the computer will − 10 3 \frac {-10} 3 3−10​ counts as − 3 -3 −3 instead of correct − 4 -4 −4 , so we can just write down the rounding function by hand. At the same time, pay attention to the correct way of taking the modulo:

(a[i]%d+d)%d;

total time complexity O ( n log ⁡ n ) O(n \log n) O(nlogn) .

Code

#include <bits/stdc++.h>
#define inf 1000000007
using namespace std;
const int maxl=200005;

int read(){
	int s=0,w=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-')  w=-w;ch=getchar();}
	while (ch>='0'&&ch<='9'){s=s*10+(ch^'0');ch=getchar();}
	return s*w;
}
int n,k,d,pos1,pos2,maxv,ansl,ansr;
int a[maxl],lim[maxl],tree[maxl<<2],tag[maxl<<2];
int mint[maxl],maxt[maxl],minval[maxl],maxval[maxl];
map<int,int> la;

void pushup(int rt){tree[rt]=min(tree[2*rt],tree[2*rt+1]);}
void f(int l,int r,int rt,int num){tree[rt]+=num,tag[rt]+=num;}
void pushdown(int l,int r,int rt){
	if (l==r)  return;
	if (tag[rt]){
		int mid=(l+r)>>1;
		f(l,mid,rt<<1,tag[rt]);
		f(mid+1,r,rt<<1|1,tag[rt]);
		tag[rt]=0;
	}
}
void build_tree(int l,int r,int rt){
	if (l==r){
		tree[rt]=l;
		return;
	}
	int mid=(l+r)>>1;
	build_tree(l,mid,rt<<1),build_tree(mid+1,r,rt<<1|1);
	pushup(rt);
}

void change(int nl,int nr,int l,int r,int rt,int k){
	if (nl<=l&&r<=nr){
		f(l,r,rt,k);
		return;
	}
	pushdown(l,r,rt);
	
	int mid=(l+r)>>1;
	if (nl<=mid)  change(nl,nr,l,mid,rt<<1,k);
	if (nr>mid)  change(nl,nr,mid+1,r,rt<<1|1,k);
	pushup(rt);
}

int tree_query(int nl,int nr,int l,int r,int rt,int k){
	pushdown(l,r,rt);
	if (tree[rt]>k)  return inf;
	if (nl<=l&&r<=nr){
		if (l==r)  return l;
		else{
			int mid=(l+r)>>1;
			if (tree[rt<<1]<=k)  return tree_query(nl,nr,l,mid,rt<<1,k);
			else return tree_query(nl,nr,mid+1,r,rt<<1|1,k);
		}
	}
	int mid=(l+r)>>1,res=inf;
	if (nl<=mid)  res=tree_query(nl,nr,l,mid,rt<<1,k);
	if (nr>mid)  res=min(res,tree_query(nl,nr,mid+1,r,rt<<1|1,k));
	
	return res;
} 

signed main(){
	n=read(),k=read(),d=read();
	for (int i=1;i<=n;i++)  a[i]=read();
	
	if (d==0){
		int len=0,res=0;a[n+1]=inf;
		for (int i=1;i<=n+1;i++){
			if (a[i]!=a[i-1]){
				if (len>res){
					res=len,ansl=i-len,ansr=i-1;
				}
				len=1;
			}
			else len++;
		}
		cout<<ansl<<' '<<ansr<<endl;
		return 0;
	}
	lim[1]=1;
	for (int i=2;i<=n;i++){
		if ((a[i]%d+d)%d==(a[i-1]%d+d)%d)  lim[i]=lim[i-1];
		else lim[i]=i;
	}
	for (int i=1;i<=n;i++)  lim[i]=max(lim[i],max(lim[i-1],la[a[i]]+1)),la[a[i]]=i;

	build_tree(1,n,1);
	for (int i=1;i<=n;i++){
		if (a[i]>=0)  a[i]/=d;
		else{
			if (a[i]%d==0)  a[i]/=d;
			else a[i]=(a[i]/d)-1;
		}
	}
	for (int i=1;i<=n;i++){
		while (pos1>0&&maxval[pos1]<=a[i]){
			change(maxt[pos1-1]+1,maxt[pos1],1,n,1,-maxval[pos1]);
			pos1--;
		}
		while (pos2>0&&minval[pos2]>=a[i]){
			change(mint[pos2-1]+1,mint[pos2],1,n,1,minval[pos2]);
			pos2--;
		}
		change(maxt[pos1]+1,i,1,n,1,a[i]);
		change(mint[pos2]+1,i,1,n,1,-a[i]);
		maxt[++pos1]=i,maxval[pos1]=a[i];
		mint[++pos2]=i,minval[pos2]=a[i];
		
		int le=tree_query(lim[i],i,1,n,1,k+i);
		if (i-le+1>maxv)  ansl=le,ansr=i,maxv=i-le+1;
	}
	cout<<ansl<<' '<<ansr<<endl;
	
	return 0;
}