好前一段时间因为一些神必原因……博客放到了https://yahyachan.github.io。然后因为我回学校了所以接下来很长时间可能会继续用这个博客？

我谔谔，还是说这题……

对于询问\([l, r]\)，考虑所有数在其中第一次出现的位置，如果说这个数在整个区间里只出现了一次，那么这个数下一次出现的位置一定大于\(r\)。

因此我们用扫描线搞一下就好啦……

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using pii = std::pair<int, int>;
const int maxn = 500005;
const int maxno = maxn << 2;
pii maxv[maxno];
void maintain(int o) {
  maxv[o] = std::max(maxv[o << 1], maxv[o << 1 | 1]);
}
void build_tree(int o, int L, int R) {
  if(L == R) {
    maxv[o] = std::make_pair(-1, -1);
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void modify(int o, int L, int R, const int &p, const pii &v) {
  if(L == R) {
    maxv[o] = v;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      modify(o << 1, L, M, p, v);
    } else {
      modify(o << 1 | 1, M + 1, R, p, v);
    }
    maintain(o);
  }
}
pii query(int o, int L, int R, const int &ql, const int &qr) {
  if(ql <= L && R <= qr) {
    return maxv[o];
  } else {
    int M = (L + R) / 2;
    pii ret = std::make_pair(-100, -100);
    if(ql <= M) ret = std::max(ret, query(o << 1, L, M, ql, qr));
    if(qr > M) ret = std::max(ret, query(o << 1 | 1, M + 1, R, ql, qr));
    return ret;
  }
}

int rec[maxn], next[maxn];
int A[maxn];
std::vector<pii> que[maxn]; int ans[maxn];
int main() {
  int n; scanf("%d", &n);
  std::fill(rec, rec + maxn, n + 1);
  for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
  for(int i = n; i >= 1; i --) {
    next[i] = rec[A[i]];
    rec[A[i]] = i;
  }
  int q; scanf("%d", &q);
  for(int i = 1; i <= q; i ++) {
    int l, r; scanf("%d%d", &l, &r);
    que[l].push_back({r, i});
  }
  build_tree(1, 1, n);
  for(int i = 1; i <= 500000; i ++) {
    if(rec[i] <= n) {
      modify(1, 1, n, rec[i], {next[rec[i]], i});
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(const pii &g : que[i]) {
      int r = g.first, id = g.second;
      pii tmp = query(1, 1, n, i, r);
      if(tmp.first <= r) {
        ans[id] = 0;
      } else {
        ans[id] = tmp.second;
      }
    }
    int nx = next[i];
    if(nx <= n) {
      modify(1, 1, n, nx, {next[nx], A[i]});
    }
  }
  for(int i = 1; i <= q; i ++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

• 相关文章
• 全局相关文章