E. Level Up - Educational Codeforces Round 168
Solutions Codeforces 数据结构 线段树 线段树二分 log
Lastmod: 2025-01-05 周日 13:03:26

https://codeforces.com/contest/1997/problem/E

题目大意

给定 n (≤2⋅105) 长的数组和 q (≤2⋅105) 个询问。数组中元素 ai (≤2⋅105)。对于参数 k，我们依次在数组中标记 k 个不小于 1 的数，之后从最后标记的下标开始，再标记 k 个不小于 2 的数，以此类推。

每个询问给出 i (1≤i≤n) 和 x (1≤x≤n)，问 i 位置在参数 k=x 时是否被标记。

简要题解

先考虑如何判断一个位置是否被标记。我们考虑每次标记的 k 个的一段，假设这段是第 p 段，则这一段中 ai≥p 的 i 会被标记，而其他的 i 不会。

因为 x 不超过 n，我们考虑枚举 x。（实际上超过了也没关系。x≥n 时所有位置都会被标记。）

注意到，每一段至少都有 x 长，也就是说最多会分 ⌊nx⌋ 段，而对于所有的 x 最多有 O(nlogn) 段。因此如果我们需要一个办法能够快速的处理段。

考虑我们已经有了参数为 x 第 p 段的末尾位置 pos（最后一个标记元素的下标），此时相当于我们要找 [pos+1,n] 中最小的位置 r 使得 ∑pos+1≤i≤r[ai≥(p+1)]==x。这个位置显然是可以二分的，那么现在问题就是有什么数据结构可以快速的完成这个求和操作。线段树可以维护所有 ≥p+1 的位置。

每次固定 x 让 p 变化那么线段树中的合法数字是不容易维护的（当然也可以可持久化）。 更简单的做法是固定 p，这样每次 p 变化再更新线段树即可。可以用一个集合维护所有还没有分完的 x。 对于这些 x 处理出段，然后处理段中的询问。

最后注意到线段树上可以直接做二分。至此我们得到了一个 O(nlog2n) 的优秀做法。

特别注意，这个题是多组数据，而每组数据 ai 的范围和 n 无关。（但实际上 >n 的数据是没有意义的，可以完全转化到 =n）

复杂度

T：O(nlog2n)

S：O(n)

代码实现

#include <bits/stdc++.h>
using namespace std;
 
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
 
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
 
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) { 
    return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) { 
    return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }
 
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
 
struct SegT {
  int n;
  vector<int> sum;
  SegT(int n) : n(n), sum(n << 2) {}
 
  int P, V;
  void update(int o, int l, int r) {
    sum[o] += V;
    if (l == r) return;
 
    int mid = (l + r) >> 1;
    if (P <= mid) update(o << 1, l, mid);
    else update(o << 1 | 1, mid + 1, r);
  }
 
  int L, S;
  pair<int, int> query(int o, int l, int r) {
    if (r < L) return {-1, 0};
    if (L <= l && sum[o] < S) return {-1, sum[o]};
    if (l == r) {
      return {l, 1};
    }
 
    int mid = (l + r) >> 1;
    PII ans = query(o << 1, l, mid);
    if (ans.first != -1) return ans;
    S -= ans.second;
    return query(o << 1 | 1, mid + 1, r);
  }
};
 
void solve() {
  int n, q; cin >> n >> q;
  vector<int> a(n);
  for (int& i : a) {
    cin >> i;
    if (i > n) i = n;
  }
 
  // map<int, vector<int>> pos;
  vector<vector<int>> pos(n + 1);
  for (int i = 0; i < n; i++) {
    pos[a[i]].push_back(i);
  }
 
  vector<vector<PII>> qs(n + 1);
  int j, x;
  for (int i = 0; i < q; i++) {
    cin >> j >> x;
    qs[x].push_back({j - 1, i});
  }
  for (int i = 1; i <= n; i++) {
    sort(qs[i].begin(), qs[i].end());
  }
  
  vector<int> nxt(n + 1);
  vector<int> valid, tmp;
  vector<int> qi(n + 1, 0);
 
  for (int i = 1; i <= n; i++) valid.push_back(i);
 
  SegT segt(n);
  for (int i = 0; i < n; i++) {
    segt.P = i;
    segt.V = 1;
    segt.update(1, 0, n - 1);
  }
 
  vector<int> ans(q);
  for (int p = 1; p <= n; p++) {
    for (int i : pos[p - 1]) {
      segt.P = i;
      segt.V = -1;
      segt.update(1, 0, n - 1);
    }
 
    tmp.clear();
    for (int x : valid) {
      segt.L = nxt[x];
      segt.S = x;
      
      auto [r, _] = segt.query(1, 0, n - 1);
 
      // cerr << x << ' ' << p << ' ' << nxt[x] << ' ' << r << endl;
      if (r == -1) r = n - 1;
 
      while (qi[x] < (int)qs[x].size() && qs[x][qi[x]].first <= r) {
        if (a[qs[x][qi[x]].first] >= p) ans[qs[x][qi[x]].second] = true;
        // cerr << "    " << qs[x][qi[x]].first << ' ' << qs[x][qi[x]].second << ' ' << (ans[qs[x][qi[x]].second]) << endl;
        qi[x]++;
      }
      
      if (r + 1 < n) {
        nxt[x] = r + 1;
        tmp.push_back(x);
      }
    }
 
    valid = tmp;
  }
 
  for (int i = 0; i < q; i++) {
    cout << (ans[i] ? "YES" : "NO") << '\n';
  }
}
 
int main() {
  int t = 1; 
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
Prev: D. Maximize the Root - Educational Codeforces Round 168
Next: D. Med-imize - Codeforces Round 963 (Div. 2)

Gitalking ...