文章目錄

• CF407 E. k-d-sequence
• • problem
  • solution
  • code

CF407 E. k-d-sequence

problem

solution

• special case，$d=0$，相當于尋找最長的一段數字相同的區間

• other case，如果要滿足公差為$d$等差序列

  • 區間內每個數在模$d$意義下同余
  • 每個數互不相同

• 算法流程

  • 先將序列分成若干個同余$m$的子區間，從左往右掃一遍，即可得到

  • 對于同余的子區間，把所有數進行$\frac{x?r}{d}$的操作，轉化為求公差為$1$的等差數列

  • 對于區間$[l,r]$，需要增加的個數$\max \{x_i|l\le i\le r\}?\min \{x_i|l\le i\le r\}+1?(r?l+1)$

    滿足增加個數$\le k$

  • 從小到大順次枚舉$r$，那么就是要最小化$l$

    • $[l,r]$區間不重復

      可以通過map快速查到與$x_r$值相同的點的位置，假設為$pos$

      則需滿足$pos<l$

    • 加的數個數不能超過$k$

      $\max \{x_i|l\le i\le r\}?\min \{x_i|l\le i\le r\}+1?(r?l+1)\le k$

      $?$

      $\max \{x_i|l\le i\le r\}?\min \{x_i|l\le i\le r\}+l\le k+r$

      用線段數維護$w_l=\max \{x_i|l\le i\le r\}?\min \{x_i|l\le i\le r\}+l$

      設$l$的下界為$pos$，則要在$[pos,r]$找最左邊的$l$，滿足$w_l\le k+r$

• 最后只剩下如何維護$w$

  單調棧，維護一個遞增單調棧和一個遞減單調棧。以遞減為例

  遞減單調棧當一個大于棧頂的元素加入時，會不斷彈出棧頂，因此單調棧可以將$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]|l<=i<=r}的遞增棧//Max:維護max{a[i]|l<=i<=r}的遞減棧//棧內點管轄一個區間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; }

總結

以上是生活随笔為你收集整理的CF407 E. k-d-sequence（线段树+单调栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。