[Blog] [Docs] [Code] [Slides] [About]

KickStart 2020 Round D-D Locked Doors

二分RMQ

2020-07-15 20:32 CST

题目 题解和总结:/blog/2020-07-15-ks-2020-d/

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

class Node {
 public:
  int l, r;
  int val;
};

int n = 0, q = 0;
int d[100005] = {};
Node t[400020] = {};

void build(int cur, int l, int r) {
  t[cur].l = l;
  t[cur].r = r;
  if (l == r) {
    t[cur].val = d[l];
    return;
  }
  int m = (l + r) / 2;
  build(cur << 1, l, m);
  build(cur << 1 | 1, m + 1, r);
  t[cur].val = max(t[cur << 1].val, t[cur << 1 | 1].val);
}

int query(int cur, int l, int r) {
  if (t[cur].l == l && t[cur].r == r) {
    return t[cur].val;
  }
  if (t[cur << 1].r >= r) {
    return query(cur << 1, l, r);
  } else if (t[cur << 1 | 1].l <= l) {
    return query(cur << 1 | 1, l, r);
  } else {
    return max(query(cur << 1, l, t[cur << 1].r),
               query(cur << 1 | 1, t[cur << 1 | 1].l, r));
  }
}

bool check(int s, int k, int step) {
  // go left 'step' steps ok?
  int farL = s - step, farR = s + (k - step);
  int maxL = query(1, farL, s - 1);
  int maxR = query(1, s, farR);
  return maxL < maxR;
}

int solve(int s, int k) {
  int step = 0, l = max(1, k - (n - s)), r = min(s - 1, k);
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(s, k, mid)) {
      step = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  int ansL = s - step - 1;
  int ansR = s + (k - step) + 1;
  return d[ansL] < d[ansR - 1] ? ansL : ansR;
}

int main() {
  int T = 0;
  scanf("%d", &T);
  for (int t = 1; t <= T; ++t) {
    scanf("%d %d", &n, &q);
    d[0] = d[n] = 0x3f3f3f3f;
    for (int i = 1; i < n; ++i) {
      scanf("%d", d + i);
    }
    build(1, 0, n);
    printf("Case #%d: ", t);
    for (int i = 1; i <= q; ++i) {
      int s = 0, k = 0;
      scanf("%d %d", &s, &k);
      printf("%d ", k == 1 ? s : solve(s, k - 2));
    }
    printf("\n");
  }
  return 0;
}
<EOF>