题解：P14507 缺零分治 mexdnc

· · 题解

TLDR：考虑逐一按照所有的值，从下往上往每一个集合里面去填，然后优化此过程即可。细节很多。

正文

考虑构造出一种 \operatorname{mex} \ge m 的方案，然后将其调整变成一种 \operatorname{mex} = m 的方案。

我们先丢弃所有不可能对 \operatorname{mex} 造成贡献的 a_i。对于剩下的 a_i，发现可以从小到大将其“涂抹”在所有的可重集合上，所以在 k 个桶上最大的 \sum \operatorname{mex} 为 \sum_{i = 0}^{mx} \min(\min_{i \le j \le i}(cnt_j), k)。

对于 k \ge 2 的状况，显然可以逐渐丢弃元素直到 \sum \operatorname{mex} = 1。所以，我们对 m 分类讨论：

Talk is cheap, show me the code

::::info[Code（有点长因为我要理清思路）]

//#define DEBUG
#include <bits/stdc++.h>
#ifdef DEBUG
#include <windows.h>
#endif
#define int ll
#define ctz __builtin_ctzll
#define popc __builtin_popcountll
#define lowbit(x) ((x) & -(x))
#define ct1(x) ctz((x) + 1)
using namespace std;
using ll = long long;
const int kMod = int(1e9) + 7, kInf = 0x3f3f3f3f3f3f3f3f;
template<class T>T read(istream &is = cin) {
  T x;
  is >> x;
  return x;
}
int readInt(istream &is = cin) {return read<int>(is);}
int qpow(int x, int y) {
  x %= kMod;
  if(x == 0) return 0;
  int res = 1;
  for(; y; y >>= 1) {
    if(y & 1) res = res * x % kMod;
    x = x * x % kMod;
  }
  return res;
}
int qinv(int x) {return qpow(x, kMod - 2);}
random_device rd;
mt19937_64 mt(rd());

struct node {
  int a, b;
}arr[100010];

int t, n, q, m, cb[100010], sf[100010];

int get(int x) {
  int l = 1, r = n, ans = 0;
  for(; l <= r; ) {
    int mid = (l + r) >> 1;
    if(cb[mid] >= x) ans = mid, l = mid + 1;
    else r = mid - 1;
  }
  return ans;
}

int gen(int mid) {
  int tmp = get(mid);
  return tmp * mid + sf[tmp + 1];
}

bool check(int mid) {return gen(mid) >= m;}

int lrmid() {
  if(gen(1) == m) return 1;
  int l = 2, r = cb[1] + 2, ans = -1;
  for(; l <= r; ) {
    int mid = (l + r) >> 1;
    if(check(mid)) ans = mid, r = mid - 1;
    else l = mid + 1;
  }
  return ans;
}

signed main() {
  //freopen("mexdnc.in", "r", stdin);
  //freopen("mexdnc.out", "w", stdout);
#ifndef DEBUG
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
#endif
  for(cin >> t; t--; ) {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> arr[i].a >> arr[i].b;
    if(arr[1].a != 0) n = 0;
    for(int i = 1; i <= n; i++) {
      if(arr[i + 1].a > arr[i].a + 1) {
        n = i;
        break;
      }
    }
    for(int i = 2; i <= n; i++) arr[i].b = min(arr[i].b, arr[i - 1].b);
    for(int i = n; i >= 1; i--) sf[i] = sf[i + 1] + (cb[i] = arr[i].b);
    for(; q--; ) {
      cin >> m;
      //cout << get(2) << ' ' << gen(2) << '\n';
      if(m == 0) cout << (n == 0? 1 : -1) << '\n';
      else cout << lrmid() << '\n';
    }
    fill(sf + 1, sf + n + 1, 0);
  }
  return 0;
}

::::