愈发感到我的人生太草率了，全心准备高考的时候，突然收到 SM2 的 offer，一月份就远渡南洋去南洋理工读书了。C'est la vie，仔细回想，几乎所有会影响到老子生命进程的决定，都没有经过深思熟虑。不过这的确是一次不错的机会，倘若削尖脑袋钻高考，我的水平差不离就是华五的样子，且没有稳定上线的信心，清北大抵就需要爆种了。SM2 让我可以在不参加高考的情况下上一个几乎同等水平的大学（应该吧），不能不说的确很诱人。

命运总是在暗中标价的道理我自然知道，事实上 SM2 为我带来的是更多的不确定性。在中国学生的硕博情结与竞赛学生的科研情结的双重加持下，SM2 仅到本科的支持对我来讲就显得并不完全让人放心。不过正是充满未知才让未来显得如此迷人，若生为巨鲸，便去左右洋流，我坚信船到桥门自会直，只要能持续专注付出，纵有沟壑我飞跃。

我不是电子越共，而且这个东西也不小众。

Mistakes That I Don't Want to Make Once Again.

// Caution //

1. 差分 / 前缀和后注意询问区间端点有变化……
2. 不要考虑了右边界就不考虑左边界

// Caution //

1. 只减不加莫队如果维护了数据结构, 换块的时候要将前缀块 (处理过的) 的影响消除. 一个高庙的写法是开个 stack 记录修改, 然后将换块的左指针挪动的 stack 清了. at - rrads
2. 只加不减应该也有类似的问题.

// Caution //

李超树动态开点时，当前结点为空应该直接赋值后退出，即：

int upd(int id, int u, int l = -vinf, int r = vinf) {
    if (!u) return tr[u = ++tid] = id, u;

// Caution //

决策单调性的题目，如果贡献与之前的 dp 值有关，就不能写整体二分了，不然会出现「第一个求的是 dp[mid]」这样转移顺序的问题，比如诗人小狗。

区间加法可以差分的原因是 $\Delta_i = \Delta_{i-1}$，所以令 $\textit{d}_i = \Delta_i-\Delta_{i-1}$，对于一个一般点的 $\Delta_i = f(\{\Delta_1, \dots, \Delta_{i-1}\})$，我们可以令 $\textit{d}_i = \Delta_i-f(\{\Delta_1, \dots, \Delta_{i-1}\})$。

这得出了广义一点的差分。那么前缀和的方式即 $\textit{d}_i \gets d_i+f(\{d, \dots, d_{i-1}\})$（其实这里的 $f$ 改为下标的函数可能更准确一点）。

举个例子，对区间 $[l, r]$ 中的 $i \in [l, r]$ 操作 $a_i \gets a_i+f_{i-l+1}$，其中 $f$ 是 Fibonacci 数列，也就是说 $f_i = f_{i-1}+f_{i-2}$，差分数组即 $d_i = a_i-a_{i-1}-a_{i-2}$，操作即 $d_l \gets d_l+1$，$d_{r+1} \gets d_{r+1}+f_{r-l+2}$，$d_{r+2} \gets d_{r+2}+f_{r-l+1}$，前缀和方法即 $d_i \gets d_i+d_{i-1}+d_{i-2}$。

差分是导函数的一个演绎，即令研究范围中的 $\epsilon = 1$ 而得来的（在实数中令 $\epsilon = \lim\limits_{\frac{1}{x} \rightarrow +\infty}x$ 做差分即可得到导函数）。

link.

感觉好久没写过题解了, 这就是永远在骚动的得不到吧.

星尘 infinity 真的非常行, 就算是 ja voicebase 都不知道吊打那群日 v 多少圈. 我推荐你们都去听一听.

chin voicebase 更是重量级, 乱杀 vs 那堆. 不得不说个体技术力质的进步才是社会发展的关键, 什么大家进步了总体就进步了就是扯淡.

当然也不能像赫鲁晓夫那群天才一样鼓吹唯生产力论, 但是用 $+\infty$ 的 p 们确实交出了优秀的答卷, 时至今日的格局只能说是原本基础决定的.

首先如果没有删除操作的话, 这题可以 parallel search 随便做做了. 加上删除操作再套个 segment tree beats 就行.

题解大概就是这样, 我主要来说下这个 segment tree beats. 首先这里没有必要真的写一个出来, 因为注意到是单点询问. 但是这里的线段树有一些不同于传统的线段树, 尽管传统线段树也是一棵 leafy tree, 但是这里树的非叶结点上是没有信息需要维护的. 可以把 lazy propagation 和你维护的幺半群放到一个数组来写.

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;

const i64 inf = 1e9;
int N, M, Q, sz, h, ans[250100];
i64 dat[250100];
struct rec {
  i64 p, q;
} lz[524388];
struct req {
  i64 a, b, c, d;
} q[250100];
void add(int x, i64 v) {
  for (; x <= N + 1; x += x & -x) dat[x] += v;
}
void add(int l, int r, i64 v) { add(l, v), add(r + 1, -v); }
i64 sum(i64 x) {
  i64 res = 0;
  for (; x; x -= x & -x) res += dat[x];
  return res;
}
rec composition(rec f, rec v) { return {v.p + f.p, max(v.q + f.p, f.q)}; }
void propagate(int x, rec f) { lz[x] = composition(f, lz[x]); }
void push(int x) {
  propagate(x * 2, lz[x]), propagate(x * 2 + 1, lz[x]), lz[x] = {0, -inf};
}
void add(int l, int r, rec f) {
  assert(0 <= l && l <= r && r <= N);
  if (l == r) return;
  l += sz, r += sz;
  for (int i = h; i >= 1; --i) {
    if (((l >> i) << i) != l) push(l >> i);
    if (((r >> i) << i) != r) push((r - 1) >> i);
  }
  for (; l < r; l >>= 1, r >>= 1) {
    if (l & 1) propagate(l++, f);
    if (r & 1) propagate(--r, f);
  }
}
i64 get(i64 x) {
  assert(0 <= x && x < N);
  for (i64 i = h; i >= 1; --i) push((x + sz) >> i);
  return max(lz[x + sz].p, lz[x + sz].q);
}

void dac(int l, int r, const vector<int>& id) {
  if (id.empty()) return;
  if (l == r) {
    for (auto&& it : id) ans[it] = l;
    return;
  }
  int mid = (l + r) / 2;
  for (int i = l; i <= mid; ++i)
    if (q[i].c && q[i].d) add(q[i].a, q[i].b, q[i].d);
  vector<int> ql, qr;
  for (auto&& it : id) (sum(q[it].a) >= q[it].b ? ql : qr).emplace_back(it);
  dac(mid + 1, r, qr);
  for (int i = l; i <= mid; ++i)
    if (q[i].c && q[i].d) add(q[i].a, q[i].b, -q[i].d);
  dac(l, mid, ql);
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> N >> M >> Q;
  h = ceil(log2(N)), sz = 1 << h;
  for (int i = 0; i <= N; ++i) lz[i + sz] = {0, -inf};
  vector<int> is;
  for (i64 o, l, r, c, k, i = 1; i <= Q; ++i) {
    cin >> o >> l >> r, c = k = 0;
    if (o == 1)
      cin >> c >> k, add(l, r, k), add(l - 1, r, {k, 0});
    else if (o == 2)
      cin >> k, add(l - 1, r, {-k, 0});
    else
      r += sum(l) - get(l - 1), is.emplace_back(i);
    q[i] = {l, r, c, k};
  }
  memset(dat, 0, sizeof(dat)), dac(1, Q + 1, is);
  for (int i = 1; i <= Q; ++i)
    if (q[i].c == 0 && q[i].d == 0)
      cout << q[ans[i] > i ? 0 : ans[i]].c << "\n";
  return 0;
}