2023-10-16

· · 个人记录

T389709 体育课2（number）

思路

我们可以考虑每一个人是在什么时候被出局的，我们现在考虑一下当前点，那么可以将它出局的点肯定是往左走第一个比它大的点，不过有可能那个点会被先删掉，但是肯定还会有一个来代替它，那么我们就只要考虑这个区间内的，对于这个区间内的结果做出转移的话，显然当前点被删掉的时间将会是这个区间内答案最大的点的答案 +1，那么我们可以设计状态：dp_i 表示考虑到 i 的答案，然后对于这区间，我们不能枚举，我们考虑到这个区间是什么，是左边比右边要大的第一个的那个数，所以我们可以先用单调栈来预处理左边界，然后用 ST 表来维护区间答案，然后取所有答案的最大值即可。

时空复杂度

时间：O(nlogn) 空间：O(nlogn)

T389710 零件加工（balloc）

考虑贪心，可以将左端点排序，能加就加，否则然后寻找比当前右端点大的最大的右端点的区间删掉，那么这个时候会有区间修改，所以用线段树即可。

那么为什么可以这么做呢？

首先能加就加肯定是最好的，那么如果不能加的话，如果说有一个位置的右端点比当前的右段点右的话，那么那个区间一定比当前区间大，因为左端点已经排序好了，这个时候如果把那个区间删掉的话接下来可以使用的区间肯定会更多，而答案肯定不会更劣，所以贪心是没有问题的。

code

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
using ll = long long;

const int MaxN = 1e5 + 10;

struct S {
  int l, r;

  bool operator<(const S &j) const {
    return l < j.l;
  }
} a[MaxN];

ll d[MaxN << 2], t[MaxN << 2], ans;
int n, m;
priority_queue<pair<int, int>> q;

void pd(int p) {
  t[p * 2] += t[p], d[p * 2] += t[p];
  t[p * 2 + 1] += t[p], d[p * 2 + 1] += t[p];
  t[p] = 0;
}

void G(int pl, int pr, int l, int r, int p, ll x) {
  if (pl <= l && r <= pr) {
    d[p] += x, t[p] += x;
    return;
  }
  if (l > pr || r < pl) {
    return;
  }
  pd(p);
  int mid = (l + r) >> 1;
  G(pl, pr, l, mid, p * 2, x), G(pl, pr, mid + 1, r, p * 2 + 1, x);
  d[p] = min(d[p * 2], d[p * 2 + 1]);
}

ll A(int pl, int pr, int l, int r, int p) {
  if (pl <= l && r <= pr) {
    return d[p];
  }
  if (l > pr || r < pl) {
    return 1e9;
  }
  pd(p);
  int mid = (l + r) >> 1, res = min(A(pl, pr, l, mid, p * 2), A(pl, pr, mid + 1, r, p * 2 + 1));
  d[p] = min(d[p * 2], d[p * 2 + 1]);
  return res;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1, x; i <= n; i++) {
    cin >> x;
    G(i, i, 1, n, 1, x);
  }
  for (int i = 1; i <= m; i++) {
    cin >> a[i].l >> a[i].r;
  }
  sort(a + 1, a + m + 1);
  for (int i = 1; i <= m; i++) {
    G(a[i].l, a[i].r, 1, n, 1, -1);
    if (A(1, n, 1, n, 1) < 0) {
      if (!q.empty() && (q.top()).first > a[i].r) {
        G((q.top()).second, (q.top()).first, 1, n, 1, 1);
        q.pop();
        q.push({a[i].r, a[i].l});
      } else {
        G(a[i].l, a[i].r, 1, n, 1, 1);
      }
     } else {
      ans++;
      q.push({a[i].r, a[i].l});
     }
  }
  cout << ans << endl;
  return 0;
}

时空复杂度

时间：O(nlogn) 空间：O(4n)