网站找谁备案,xampp wordpress 花生壳,Net网站开发多少钱,东莞电商建站文章目录problemsolutioncodeproblem
solution 特判d0d0d0#xff0c;相当于寻找最长的一段数字相同的区间 如果要满足公差为ddd等差序列 区间内每个数在模ddd意义下同余每个数互不相同 算法流程 先将序列分成若干个同余mmm的子区间 从左往右扫一遍 对于同余的子区间…
文章目录problemsolutioncodeproblem
solution 特判d0d0d0相当于寻找最长的一段数字相同的区间 如果要满足公差为ddd等差序列 区间内每个数在模ddd意义下同余每个数互不相同 算法流程 先将序列分成若干个同余mmm的子区间 从左往右扫一遍 对于同余的子区间把所有数进行x−rd\frac{x-r}{d}dx−r的操作 转化为求公差为111的等差数列 对于区间[l,r][l,r][l,r]需要增加的个数max{xi∣l≤i≤r}−min{xi∣l≤i≤r}1−(r−l1)\max\{x_i|l\le i\le r\}-\min\{x_i|l\le i\le r\}1-(r-l1)max{xi∣l≤i≤r}−min{xi∣l≤i≤r}1−(r−l1) 满足增加个数≤k\le k≤k 从小到大顺次枚举rrr那么就是要最小化lll [l,r][l,r][l,r]区间不重复 可以通过map快速查到与xrx_rxr值相同的点的位置假设为pospospos 则需满足poslposlposl 加的数个数不能超过kkk max{xi∣l≤i≤r}−min{xi∣l≤i≤r}1−(r−l1)≤k\max\{x_i|l\le i\le r\}-\min\{x_i|l\le i\le r\}1-(r-l1)\le kmax{xi∣l≤i≤r}−min{xi∣l≤i≤r}1−(r−l1)≤k ⇕\Updownarrow⇕ max{xi∣l≤i≤r}−min{xi∣l≤i≤r}l≤kr\max\{x_i|l\le i\le r\}-\min\{x_i|l\le i\le r\}l\le krmax{xi∣l≤i≤r}−min{xi∣l≤i≤r}l≤kr 用线段数维护wlmax{xi∣l≤i≤r}−min{xi∣l≤i≤r}lw_l\max\{x_i|l\le i\le r\}-\min\{x_i|l\le i\le r\}lwlmax{xi∣l≤i≤r}−min{xi∣l≤i≤r}l 设lll的下界为pospospos则要在[pos,r][pos,r][pos,r]找最左边的lll满足wl≤krw_l\le krwl≤kr 最后只剩下如何维护www 单调栈维护一个递增单调栈和一个递减单调栈。以递减为例 递减单调栈当一个大于栈顶的元素加入时会不断弹出栈顶因此单调栈可以将max(L,R)max(L,R)max(L,R)分成递减的若干段 单调栈中的一个点其实代表的是一个区间弹栈顶相当于最大值变化 被弹出的元素的线段树的最大值变化即是线段树上区间加
code
#include map
#include cstdio
#include iostream
using namespace std;
#define int long long
#define maxn 200005
map int, int last;
int n, k, d, pos, flag, ans_l 1, ans_r 1;
int a[maxn], Min[maxn], Max[maxn];
int t[maxn 4], tag[maxn 4];void build( int num, int l, int r ) {t[num] l, tag[num] 0;if( l r ) return;int mid ( l r ) 1;build( num 1, l, mid );build( num 1 | 1, mid 1, r );
}void pushdown( int num ) {t[num 1] tag[num];tag[num 1] tag[num];t[num 1 | 1] tag[num];tag[num 1 | 1] tag[num];tag[num] 0;
}void modify( int num, int l, int r, int pos ) {pushdown( num );if( l r ) {t[num] 0;return;}int mid ( l r ) 1;if( pos mid ) modify( num 1, l, mid, pos );else modify( num 1 | 1, mid 1, r, pos );t[num] min( t[num 1], t[num 1 | 1] );
}void modify( int num, int l, int r, int L, int R, int w ) {if( R l || r L ) return; if( L l r R ) {t[num] w, tag[num] w;return;}pushdown( num );int mid ( l r ) 1;modify( num 1, l, mid, L, R, w );modify( num 1 | 1, mid 1, r, L, R, w );t[num] min( t[num 1], t[num 1 | 1] );
}void find( int num, int l, int r, int k ) {if( l r ) {pos l, flag 1;return;}pushdown( num );int mid ( l r ) 1;if( t[num 1] k ) find( num 1, l, mid, k );else find( num 1 | 1, mid 1, r, k );
}void query( int num, int l, int r, int L, int R, int k ) {if( flag || r L || R l ) return;if( L l r R ) {if( t[num] k ) find( num, l, r, k );return;}pushdown( num );int mid ( l r ) 1;query( num 1, l, mid, L, R, k );query( num 1 | 1, mid 1, r, L, R, k );
}signed main() {scanf( %lld %lld %lld, n, k, d ); for( int i 1;i n;i )scanf( %lld, a[i] );if( ! d ) {int l 0, r 0;for( int i 1;i n;i ) {if( a[i] ! a[i - 1] ) l r i;else r;if( r - l ans_r - ans_l ) ans_r r, ans_l l;}return ! printf( %lld %lld\n, ans_l, ans_r );}build( 1, 1, n );int min_top 0, max_top 0;for( int r 1, l 1;r n;r ) {int t l;if( ( a[r] - a[r - 1] ) % d ) l r;else l max( l, last[a[r]] 1 );last[a[r]] r;while( t l ) modify( 1, 1, n, t );//Min:维护min{a[i]|lir}的递增栈//Max:维护max{a[i]|lir}的递减栈while( min_top Min[min_top] l a[Min[min_top]] a[r] ) {modify( 1, 1, n, Min[min_top - 1] 1, Min[min_top], a[Min[min_top]] / d );min_top --;}//取max是保证单调栈中每个点管辖区间不重复且并集为整个大区间 modify( 1, 1, n, max( l, Min[min_top] 1 ), r, -a[r] / d );Min[ min_top] r;while( max_top Max[max_top] l a[Max[max_top]] a[r] ) {modify( 1, 1, n, Max[max_top - 1] 1, Max[max_top], -a[Max[max_top]] / d );max_top --;}modify( 1, 1, n, max( l, Max[max_top] 1 ), r, a[r] / d );Max[ max_top] r;flag 0, pos 0;query( 1, 1, n, l, r, k r );if( r - pos ans_r - ans_l ) ans_l pos, ans_r r;}printf( %lld %lld\n, ans_l, ans_r );return 0;
}
