P8543 「Wdoi-2」纯粹的复仇女神

· · 题解

P8543 「Wdoi-2」纯粹的复仇女神

对于每个 (a_i, c_i)，考虑 a_i 作为区间所有 c_j = c_i 的 a_j 的最小值时，合法左右端点的形态。可知若询问左端点落在 [L, i]，右端点落在 [i, R]，则本次询问答案至少不小于 a_i，其中 L 为颜色为 c_i 且 a_j < a_i，j < i 的 i 的前驱 j 加 1：左端点不能跨过 j，否则 \min 会变得更小；同理 R 为颜色为 c_i 且 a_j < a_i，j > i 的 i 的后继 j 减 1。若 L 不存在则为 1，R 不存在则为 n。

通过上述分析，可知每个 (a_i, c_i) 对询问的贡献是矩形 [L, i]\times [i, R] 取 \max。矩形可以通过对每个颜色按 a_i 从大到小扫描线 + set 维护求出。

问题转化为矩形取 \max，单点查询，且所有查询在加入所有矩形后。对 x 轴扫描线，在 x = L 处往 y\in [i, R] 加入 a_i，在 x = i + 1 处从 y\in [i, R] 删除 a_i。非常经典的标记永久化树套树。具体地，加入时往 [i, R] 的拆分区间维护的平衡树中加入 a_i，删除同理。查询时查询经过所有节点的平衡树最大值。用 multiset 会被卡常，需要用两个 priority_queue 模拟可删除堆。

时间复杂度 \mathcal{O}(n\log ^ 2n + q\log n)。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
inline ll read() {
  ll x = 0, sgn = 0;
  char s = getchar();
  while(!isdigit(s)) sgn |= s == '-', s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return sgn ? -x : x;
}
inline void print(int x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
constexpr int N = 2e5 + 5;
constexpr int Q = 1e6 + 5;
void cmin(int &x, int y) {x = x < y ? x : y;}
void cmax(int &x, int y) {x = x > y ? x : y;}
pii d[N];
int n, q, cnt, c[N], a[N], ans[Q];
set<int> s[N];
priority_queue<int> val[N << 2], era[N << 2];
vector<pair<pii, int>> add[N];
vector<pii> qu[N];
void modify(int l, int r, int ql, int qr, int x, int v) {
  if(ql <= l && r <= qr) {
    if(v > 0) val[x].push(v);
    else era[x].push(-v);
    return;
  }
  int m = l + r >> 1;
  if(ql <= m) modify(l, m, ql, qr, x << 1, v);
  if(m < qr) modify(m + 1, r, ql, qr, x << 1 | 1, v);
}
int query(int l, int r, int p, int x) {
  int ans = 0;
  while(!era[x].empty() && val[x].top() == era[x].top()) val[x].pop(), era[x].pop();
  if(!val[x].empty()) ans = val[x].top();
  if(l == r) return ans;
  int m = l + r >> 1;
  return max(ans, p <= m ? query(l, m, p, x << 1) : query(m + 1, r, p, x << 1 | 1));
}
bool Med;
signed main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  cin >> n >> q;
  for(int i = 1; i <= n; i++) c[i] = read(), s[c[i]].insert(i);
  for(int i = 1; i <= n; i++) a[i] = read(), d[i] = {a[i], i};
  sort(d + 1, d + n + 1);
  for(int i = n, pt = n; i; i--) {
    while(pt && d[pt].first == i) {
      int id = d[pt--].second, col = c[id];
      auto pt = s[col].find(id);
      int l = 1, r = n;
      if(pt != s[col].begin()) l = *--pt + 1, pt++;
      if(pt != --s[col].end()) r = *++pt - 1, pt--;
      s[col].erase(pt);
      add[l].push_back({{id, r}, i});
      add[id + 1].push_back({{id, r}, -i});
    }
  }
  for(int i = 1; i <= q; i++) {
    int l = read(), r = read();
    qu[l].push_back({r, i});
  }
  for(int i = 1; i <= n; i++) {
    for(auto it : add[i]) modify(1, n, it.fi.fi, it.fi.se, 1, it.se);
    for(auto it : qu[i]) ans[it.se] = query(1, n, it.fi, 1);
  }
  for(int i = 1; i <= q; i++) print(ans[i]), putchar('\n');
  cerr << TIME << " ms\n";
  return 0;
}