自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:40:00，当前版本为作者最后更新于2022-09-11 00:49:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}