USACO2008JAN Haybale Guessing

在 BZOJ 是权限题,建议访问 D 站获得题目

在以下几种情况会出现不合法:1.多个最小值相同的区间无交集或交集不唯一,因为没有重复的数字。2.在几个最小值较大区间的并集中出现了一个最小值较小的子区间,很显然不行。二分答案第一个出现矛盾的位置,将其及其前面的区间按最小值降序排序,然后用一颗支持区间覆盖操作的线段树来维护错误情况 2。

#include <iostream>
#include <cstdio>
#include <algorithm>

const int MAXN = 1e6;
const int MAXQ = 25000;

int n, Q;

struct Range {
  int l, r, val;
  Range() : l(0), r(0), val(0) {}
  friend bool operator< (const Range &lhs, const Range &rhs) {
    return lhs.val > rhs.val;
  }
} a[MAXQ | 1], b[MAXQ | 1];

inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}

namespace SegTree {
  struct Node {
    int sumv, lazy;
    Node *ch[2];
    Node() : sumv(0), lazy(0) {
      ch[0] = ch[1] = NULL;
    }
  } *root;
  void push_down(Node *o, int l, int r) {
    if (o -> lazy) {
      int mid = (l + r) >> 1;
      o -> ch[0] -> sumv = (mid - l + 1);
      o -> ch[0] -> lazy = 1;
      o -> ch[1] -> sumv = (r - mid);
      o -> ch[1] -> lazy = 1;
      o -> lazy = 0;
    }
  }
  void push_up(Node *o) {
    o -> sumv = o -> ch[0] -> sumv + o -> ch[1] -> sumv;
  }
  void build(Node *&o, int l, int r) {
    if (o == NULL) o = new Node;
    else o -> sumv = o -> lazy = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(o -> ch[0], l, mid);
    build(o -> ch[1], mid + 1, r);
  }
  void modify(Node *&o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      o -> sumv = (r - l + 1);
      o -> lazy = 1;
      return;
    }
    push_down(o, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) modify(o -> ch[0], l, mid, ql, qr);
    if (mid < qr) modify(o -> ch[1], mid + 1, r, ql, qr);
    push_up(o);
  }
  int query(Node *&o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return o -> sumv;
    push_down(o, l, r);
    int mid = (l + r) >> 1, res = 0;
    if (ql <= mid) res = query(o -> ch[0], l, mid, ql, qr);
    if (mid < qr) res += query(o -> ch[1], mid + 1, r, ql, qr);
    return res;
  }
}

using namespace SegTree;

bool check(int lim) {
  build(root, 1, n);
  for (int i = 1; i <= lim; ++i) b[i] = a[i];
  std::sort(b + 1, b + 1 + lim);
  for (int i = 1, j; i <= lim; i = j) {
    for (j = i; j <= lim && b[j].val == b[i].val; ++j);
    int l1 = b[i].l, l2 = b[i].l, r1 = b[i].r, r2 = b[i].r;
    for (int k = i + 1; k < j; ++k) {
      l1 = std::min(l1, b[k].l);
      r1 = std::max(r1, b[k].r);
      l2 = std::max(l2, b[k].l);
      r2 = std::min(r2, b[k].r);
    }
    if (l2 > r2) return false;
    if (query(root, 1, n, l2, r2) == (r2 - l2 + 1)) return false;
    modify(root, 1, n, l1, r1);
  }
  return true;
}

int main() {
  n = read();
  Q = read();
  for (int i = 1; i <= Q; ++i) {
    a[i].l = read();
    a[i].r = read();
    a[i].val = read();
  }
  int l = 1, r = Q, mid, ans = 0;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (!check(mid)) {
      r = mid - 1;
      ans = mid;
    } else l = mid + 1;
  }
  printf("%d\n", ans);
  return 0;
}
最后修改:2019 年 09 月 15 日 10 : 28 AM

发表评论