【做题】CF239E. k-d-sequence—

首先，容易得到判断一个子串为“good k-d sequence”的方法：

子串中没有重复元素，且所有元素模d相等。

记mx为除以d的最大值，mn为除以d的最小值，则\(mx-mn<=r-l+k\)。

然后，我们对于每一段极大的元素同模的子串，处理\(d=1\)的情况。

显然，我们需要枚举一个端点。这里，我们从大到小枚举左端点。（当然，从小到大枚举右端点也是可行的）

我们使用单调栈和线段树，可以维护每个位置\(mx-mn\)的值。然后，因为对于每一个位置，\(r\)是固定的，所以我们把\(r\)移到左边。即有不等式\(mx-mn-r<=k-l\)。

然后，我们需要确定最右边的\(mx-mn-r<=k-l\)的元素位置，这个线段树上二分就可以了。

最后还有两个细节：

为避免出现重复元素，线段树上二分时有限制。

特判\(d=0\)的情况。

时间复杂度\(O(nlogn)\)。

#include <bits/stdc++.h>

using namespace std;

const int BAS = 1e9, N = 200010;

struct node {

  int mn,tag;

  inline void operator += (int x) {

    mn += x;

    tag += x;

  }

  inline void reset() {

    mn = tag = 0;

  }

} t[N << 2];

void push_down(int x) {

  t[x<<1] += t[x].tag;

  t[x<<1|1] += t[x].tag;

  t[x].tag = 0;

}

void push_up(int x) {

  if (t[x].tag) push_down(x);

  t[x].mn = min(t[x<<1].mn,t[x<<1|1].mn);

}

void modify(int x,int l,int r,int v,int lp,int rp) {

  if (lp > r || rp < l) return;

  if (lp >= l && rp <= r)

    return (void)(t[x] += v);

  int mid = (lp + rp) >> 1;

  modify(x<<1,l,r,v,lp,mid);

  modify(x<<1|1,l,r,v,mid+1,rp);

  push_up(x);

}

int dfs(int x,int lim,int v,int lp,int rp) {

  if (t[x].mn > v) return -1;

  if (lp == rp) return lp;

  push_down(x);

  int mid = (lp + rp) >> 1;

  if (t[x<<1|1].mn <= v && mid + 1 <= lim) {

    int res = dfs(x<<1|1,lim,v,mid+1,rp);

    if (~res) return res;

  }

  return dfs(x<<1,lim,v,lp,mid);

}

int n,k,d,arr[N],len;

map<int,int> mp;

int tmp[N];

struct data_sta {

  int l,r,val;

  inline bool operator < (const data_sta& x) const {

    return val < x.val;

  }

} st[2][N];

int top[2];

struct data_ans {

  int l,r;

  inline bool operator < (const data_ans& x) const {

    return r - l + 1 != x.r - x.l + 1 ? \

      r - l + 1 > x.r - x.l + 1 : l < x.l;

  }

};

data_ans solve() {

  mp.clear();

  data_sta tp;

  data_ans res = (data_ans) {len,-1};

  int cur = len, rec;

  top[0] = top[1] = 0;

  for (int i = len ; i >= 1 ; -- i) {

    if (mp[tmp[i]]) cur = min(cur,mp[tmp[i]] - 1);

    mp[tmp[i]] = i;

    tp = (data_sta) {i,i,tmp[i]};

    while (top[0] && st[0][top[0]].val < tp.val) {

      modify(1,st[0][top[0]].l,st[0][top[0]].r,-st[0][top[0]].val,1,len);

      tp.r = st[0][top[0]--].r;

    }

    st[0][++top[0]] = tp;

    modify(1,tp.l,tp.r,tp.val,1,len);

    tp = (data_sta) {i,i,tmp[i]};

    while (top[1] && st[1][top[1]].val > tp.val) {

      modify(1,st[1][top[1]].l,st[1][top[1]].r,st[1][top[1]].val,1,len);

      tp.r = st[1][top[1]--].r;

    }

    st[1][++top[1]] = tp;

    modify(1,tp.l,tp.r,-tp.val,1,len);

    modify(1,i,i,-i,1,len);

    rec = dfs(1,cur,k - i,1,len);

    if (~rec) res = min(res,(data_ans) {i,rec});

  }

  for (int i = 1 ; i <= (len << 2) ; ++ i)

    t[i].reset();

  return res;

}

int special_solve() {

  int res = 0, p = -1;

  for (int i = 1, j; i <= n ; i += j) {

    j = 1;

    while (arr[i+j] == arr[i] && i + j <= n) ++ j;

    if (res < j) res = j, p = i;

  }

  printf("%d %d\n",p,p + res - 1);

  return 0;

}

int main() {

  scanf("%d%d%d",&n,&k,&d);

  for (int i = 1 ; i <= n ; ++ i)

    scanf("%d",&arr[i]), arr[i] += BAS ;

  if (d == 0) return special_solve();

  data_ans res = (data_ans) {1,1}, tp;

  for (int i = 1, j ; i <= n ; i += j) {

    j = 1;

    while (arr[i+j] % d == arr[i] % d && i + j <= n)

      ++ j;

    len = j;

    for (int s = 0 ; s < j ; ++ s)

      tmp[s+1] = arr[i+s] / d;

    tp = solve();

    tp.l += i-1, tp.r += i-1;

    res = min(res,tp);

  }

  printf("%d %d\n",res.l,res.r);

  return 0;

}

小结：这样一类题目大概就是要怼着式子简化问题。

巴特西

【做题】CF239E. k-d-sequence——线段树

最新文章

热门文章