怎么可以黑网站域名,网站后期维护费用多少,五种关键词优化工具,做网站的要多钱文章目录CF407 E. k-d-sequenceproblemsolutioncodeCF407 E. k-d-sequence
problem
solution special case#xff0c;d0d0d0#xff0c;相当于寻找最长的一段数字相同的区间 other case#xff0c;如果要满足公差为ddd等差序列 区间内每个数在模ddd意义下同余每个数互不…
文章目录CF407 E. k-d-sequenceproblemsolutioncodeCF407 E. k-d-sequence
problem
solution special cased0d0d0相当于寻找最长的一段数字相同的区间 other case如果要满足公差为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 );//取max维护不重复的条件last[a[r]] r;while( t l ) modify( 1, 1, n, t );//清除不属于[l,r]区间的所有线段树痕迹//Min:维护min{a[i]|lir}的递增栈//Max:维护max{a[i]|lir}的递减栈//栈内点管辖一个区间eg:s[top]管辖(s[top-1],s[top]] //w[l]max[L,R]-min[L,R]lwhile( 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 );//[L,R]中最小值变小 先把之前-min(L,R)的贡献抵消掉 所以是min_top --;}//把现在真正的min(L,R)贡献放进去 所以是- 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 --;}//取左端点max比较是保证单调栈中每个点管辖区间不重复且并集为整个大区间 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;
}
