[APIO2018] New Home 新家 [线段树，multiset]

线段树的每个点表示当前点的前驱，即这个颜色上一次出现的位置，这个玩意multiset随便写写就完了。

重要的是怎么查询答案，无解显然先判掉。

线段树上二分就可以了

#include <bits/stdc++.h>

using namespace std;

int read() {

  int x = 0;

  char c = getchar();

  while (c < 48) c = getchar();

  while (c > 47) x = x * 10 + (c - 48), c = getchar();

  return x;

}

int min(int x, int y) { return x < y ? x : y; }

int max(int x, int y) { return x > y ? x : y; }

int n, k, q;

const int maxn = 3e5 + 53;

const int maxm = 1e7;

multiset<int> st[maxn];

int ans[maxn];

struct node {

  int x, t, id, type;

  bool operator<(const node& other) const {

    if (t != other.t) return t < other.t;

    return type < other.type;

  }

} t[maxn << 2];

int R;

int rt, cnt = 0;

int ls[maxm], rs[maxm], mn[maxm];

multiset<int> ms[maxm];

void build(int& p, int l, int r) {

  p = ++cnt;

  if (l == r) {

    for (int i = 1; i <= k; i++) ms[p].insert(0);

    return;

  }

  int mid = l + r >> 1;

  build(rs[p], mid + 1, r);

}

void modify(int& p, int l, int r, const int& x, const int& inc, const int& del) {

  if (!p) p = ++cnt;

  if (l == r) {

    if (inc >= 0) ms[p].insert(inc);

    if (del >= 0) ms[p].erase(ms[p].find(del));

    mn[p] = ((ms[p].size()) ? *ms[p].begin() : R);

    return;

  }

  int mid = l + r >> 1;

  if (x <= mid)

    modify(ls[p], l, mid, x, inc, del);

  else

    modify(rs[p], mid + 1, r, x, inc, del);

  mn[p] = min(mn[ls[p]], mn[rs[p]]);

}

int qry(int x) {

  int l = 1, r = R;

  int p = rt, chk = x << 1, tmn = R;

  while (l < r) {

    int mid = l + r >> 1, d = min(tmn, mn[rs[p]]);

    if (mid < x || d + mid < chk || d < 1)

      l = mid + 1, p = rs[p];

    else

      tmn = d, r = mid, p = ls[p];

  }

  return l - x;

}

int main() {

  // freopen("testdata.in", "r", stdin);

  n = read(), k = read(), q = read();

  int cnt = 0;

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

    int x = read(), id = read(), a = read(), b = read();

    R = max(R, x);

    t[++cnt] = { x, a, id, 0 }, t[++cnt] = { x, b + 1, id, 1 };

  }

  for (int i = 1; i <= q; i++) {

    int x = read(), time = read();

    t[++cnt] = { x, time, i, 2 };

  }

  R = R << 1 | 1, build(rt, 1, R), mn[0] = R;

  for (int i = 1; i <= k; i++) st[i].insert(0), st[i].insert(R);

  sort(t + 1, t + cnt + 1);

  int tot = 0;

  for (int i = 1; i <= cnt; i++) {

    int x = t[i].x, id = t[i].id;

    if (t[i].type == 0) {

      auto it = st[id].lower_bound(x);

      auto it2 = it;

      it2--;

      modify(rt, 1, R, x, *it2, -1);

      modify(rt, 1, R, *it, x, *it2);

      if (st[id].size() == 2) ++tot;

      st[id].insert(x);

    }

    if (t[i].type == 1) {

      st[id].erase(st[id].find(x));

      auto it = st[id].lower_bound(x);

      auto it2 = it;

      it2--;

      modify(rt, 1, R, x, -1, *it2);

      modify(rt, 1, R, *it, *it2, x);

      if (st[id].size() == 2) --tot;

    }

    if (t[i].type == 2) {

      if (tot == k)

        ans[id] = qry(x);

      else

        ans[id] = -1;

    }

  }

  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);

  return 0;

}

巴特西

[APIO2018] New Home 新家 [线段树，multiset]

最新文章

热门文章