10.21

没时间写题了，写点题解。一道题写了一晚上，效率有点低。。。

多校A层冲刺NOIP2024模拟赛09 区间

给定一个长度为 \(N\) 的数列 \(A_1,A_2,\dots,A_N\) 和一个长度为 \(N−1\) 的数列 \(B_2,B_3,\dots,B_N\)。

有 \(Q\) 个询问，每次询问是一个区间 \([L_i,R_i]\)。请你求出有多少二元组 \((l,r)\) 满足：

• \(L_i \leq l < r \leq R_i\) ​

• \(\forall i\in\{l+1,l+2,\dots,r-1\}, A_l>A_i\)（如果 \(l+1=r\) 则忽略这一条件，认为符合）

• \(\forall i\in\{l,l+1,\dots,r-1\}, B_r>A_i\)

把询问离线下来，扫描线，把询问挂在右端点。

对于第一次个限制可以用单调栈维护​，栈内元素严格递减。

对于 \(B_i\) 在单调栈中二分看有哪些 \(A_i\) 符合条件，对于这些元素记录一次版本。

用历史和线段树可以轻松做。

#include <bits/stdc++.h>

using namespace std;

using ubt = long long;

int read() {
  int x;
  cin >> x;
  return x;
}

const int maxN = 3e5 + 7;

int n, m, a[maxN], b[maxN];

vector<pair<int, int>> q[maxN];

int top, stk[maxN];

int tg[maxN * 4];
struct dat {
  ubt v, h;
  friend dat operator + (dat A, dat B) {
    dat res;
    res.v = A.v + B.v;
    res.h = A.h + B.h;
    return res;
  }
} t[maxN * 4];
#define ls (p << 1)
#define rs (p << 1 | 1)
void make(int p, int v) {
  tg[p] += v;
  t[p].h += t[p].v * v;
}
void down(int p) {
  if (!tg[p]) return;
  make(ls, tg[p]);
  make(rs, tg[p]);
  tg[p] = 0;
}
void change(int K, int v, int l, int r, int p) {
  if (l == r) {
    t[p].v += v;
    return;
  }
  down(p);
  int mid = (l + r) >> 1;
  K <= mid ? change(K, v, l, mid, ls) : change(K, v, mid + 1, r, rs);
  t[p] = t[ls] + t[rs];
}
void add(int L, int R, int l, int r, int p) {
  if (L <= l && r <= R) {
    make(p, 1);
    return;
  }
  down(p);
  int mid = (l + r) >> 1;
  if (L <= mid)
    add(L, R, l, mid, ls);
  if (R > mid)
    add(L, R, mid + 1, r, rs);
  t[p] = t[ls] + t[rs];
}

ubt ask(int L, int R, int l, int r, int p) {
  if (L <= l && r <= R)
    return t[p].h;
  down(p);
  int mid = (l + r) >> 1;
  ubt res = 0;
  if (L <= mid)
    res = ask(L, R, l, mid, ls);
  if (R > mid)
    res += ask(L, R, mid + 1, r, rs);
  return res;
}

ubt ans[maxN];

int main() {
  freopen("interval.in", "r", stdin);
  ofstream cout("interval.out");

  n = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  for (int i = 2; i <= n; i++) b[i] = read();
  m = read();
  for (int i = 1; i <= m; i++) {
    int l = read(), r = read();
    q[r].emplace_back(l, i);
  }

  stk[top = 1] = 1;
  change(1, 1, 1, n, 1);
  for (int i = 2; i <= n; i++) {
    auto erfen = [](int l, int r, int x) {
      int pos = 1e9;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (a[stk[mid]] >= x)
          l = mid + 1;
        else
          r = mid - 1, pos = mid;
      }
      return pos;
    };

    int pos = erfen(1, top, b[i]);

    if (pos != 1e9)
      add(stk[pos], i, 1, n, 1);

    for (auto [l, id] : q[i])
      ans[id] = ask(l, i, 1, n, 1);

    while (top && a[stk[top]] <= a[i])
      change(stk[top], -1, 1, n, 1), top--;
    stk[++top] = i;
    change(i, 1, 1, n, 1);
  }

  for (int i = 1; i <= m; i++)
    cout << ans[i] << '\n';
}

多校A层冲刺NOIP2024模拟赛10
不让走最短路中最后一条边的最短路

我没脑子，只会暴力数据结构。

考场上直接秒了，但有细节问题，但数据水直接过了，但后来加强了。

最短路唯一，那可以建出最短路树。

对于每个节点的答案就是不能经过与父亲的连边。

那每个点的答案就是子树内的点与子树外的点的连边贡献的。

考虑数据结构暴力维护。

把每个边塞到平衡树里。

没写完。
明天补。