线段树 3 的代码库存和势能分析的笔记。

势能分析法

利用物理来分析均摊时间复杂度的一种方法。总的来说，定义一个势能函数 $E_p(t)$ 来评价某个状态的复杂度，接着类似物理题，对于每刻状态由能量守恒定理得：

$$W(t)=F(t)+\Delta E_p(t)\quad\left(\text{其中 }\Delta E_p(t)=E_p(t)-E_p(t-1)\right) $$

此时 $W(t)$ 表示这次操作消耗复杂度， $F(t)$ 表示常量做功。

那么对于整个程序，有

$$W_\Sigma=F_\Sigma+\Delta {E_p} $$

要确定时间复杂度，即确定 $\mathcal{O}(W_\Sigma)$ ，那么就要确定 $\mathcal{O}(F_\Sigma),\mathcal{O}(E_p)$ 。

例子 - 单调队列复杂度分析

对于单调队列每一项的入队和出队：

$$W(t)=F(t)+E_p(t-1)+F(t)-E_p(t) $$

则总功（暂且这么说罢） $W_\Sigma = 2\sum F(t) + \Delta E_p = 2n + \Delta E_p$ ，考虑到 $E_p(0)=0,E_p(n)=\mathcal{O}(n)$ ，则 $\mathcal{O}(W_\Sigma)=\mathcal{O}(n)$ 。

线段树 3

开始在线段树里用 define 了，很舒服 😊！

const int N = 5e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	struct SegmentTree {
		struct Tree {
			int l, r;
			int mxa, mxb, sec, cnt;
			int add1, add2, add3, add4;
			ll sum;
		} t[N << 2];
#define lson (p << 1)
#define rson (p << 1 | 1)
#define inf (1 << 30)
		void pushup(int p) {
			t[p].sum = t[lson].sum + t[rson].sum;
			t[p].mxa = max(t[lson].mxa, t[rson].mxa);
			t[p].mxb = max(t[lson].mxb, t[rson].mxb);
			if (t[lson].mxa == t[rson].mxa) {
				t[p].sec = max(t[lson].sec, t[rson].sec);
				t[p].cnt = t[lson].cnt + t[rson].cnt;
			} else if (t[lson].mxa > t[rson].mxa) {
				t[p].sec = max(t[lson].sec, t[rson].mxa);
				t[p].cnt = t[lson].cnt;
			} else {
				t[p].sec = max(t[lson].mxa, t[rson].sec);
				t[p].cnt = t[rson].cnt;
			}
		}
		void change(int p, int k1, int k2, int k3, int k4) {
			t[p].sum += 1ll * k1 * t[p].cnt + 1ll * k2 * (t[p].r - t[p].l + 1 - t[p].cnt);
			t[p].mxb = max(t[p].mxb, t[p].mxa + k3);
			t[p].mxa += k1;
			if (t[p].sec != -inf) t[p].sec += k2;
			t[p].add3 = max(t[p].add3, t[p].add1 + k3);
			t[p].add4 = max(t[p].add4, t[p].add2 + k4);
			t[p].add1 += k1, t[p].add2 += k2;
		}
		void pushdown(int p) {
			int maxn = max (t[lson].mxa, t[rson].mxa);
			if (t[lson].mxa == maxn) change(lson, t[p].add1, t[p].add2, t[p].add3, t[p].add4);
			else change (lson, t[p].add2, t[p].add2, t[p].add4, t[p].add4);
			if (t[rson].mxa == maxn) change(rson, t[p].add1, t[p].add2, t[p].add3, t[p].add4);
			else change (rson, t[p].add2, t[p].add2, t[p].add4, t[p].add4);
			t[p].add1 = t[p].add2 = t[p].add3 = t[p].add4 = 0;
		}
		void Build (int p, int l, int r) {
			t[p].l = l, t[p].r = r;
			if (t[p].l == t[p].r) {
				t[p].sum = t[p].mxa = t[p].mxb = Read();
				t[p].cnt = 1, t[p].sec = -inf;
				return;
			}
			int mid = (t[p].l + t[p].r) >> 1;
			Build (lson, l, mid);
			Build (rson, mid + 1, r);
			pushup(p);
		}
		void UpdateAdd(int p, int l, int r, int k) {
			if (l > t[p].r || r < t[p].l) return;
			if (l <= t[p].l && t[p].r <= r) {
				t[p].sum += 1ll * k * t[p].cnt + 1ll * k * (t[p].r - t[p].l + 1 - t[p].cnt);
				t[p].mxa += k;
				t[p].mxb = max (t[p].mxb, t[p].mxa);
				if (t[p].sec != -inf) t[p].sec += k;
				t[p].add1 += k, t[p].add2 += k;
				t[p].add3 = max(t[p].add3, t[p].add1);
				t[p].add4 = max(t[p].add4, t[p].add2);
				return;
			}
			pushdown(p);
			UpdateAdd(lson, l, r, k);
			UpdateAdd(rson, l, r, k);
			pushup(p);
		}
		void UpdateMin(int p, int l, int r, int val) {
			if (l > t[p].r || r < t[p].l || val >= t[p].mxa) return;
			if (l <= t[p].l && t[p].r <= r && t[p].sec < val) {
				int k = t[p].mxa - val;
				t[p].sum -= 1ll * t[p].cnt * k;
				t[p].mxa = val, t[p].add1 -= k;
				return;
			}
			pushdown(p);
			UpdateMin(lson, l, r, val);
			UpdateMin(rson, l, r, val);
			pushup(p);
		}
		ll QuerySum(int p, int l, int r) {
			if (l > t[p].r || r < t[p].l) return 0;
			if (l <= t[p].l && t[p].r <= r) return t[p].sum;
			pushdown(p);
			return QuerySum(lson, l, r) + QuerySum(rson, l, r);
		}
		int QueryMaxA(int p, int l, int r) {
			if (l > t[p].r || r < t[p].l) return -inf;
			if (l <= t[p].l && t[p].r <= r) return t[p].mxa;
			pushdown(p);
			return max(QueryMaxA(lson, l, r), QueryMaxA(rson, l, r));
		}
		int QueryMaxB(int p, int l, int r) {
			if (l > t[p].r || r < t[p].l) return -inf;
			if (l <= t[p].l && t[p].r <= r) return t[p].mxb;
			pushdown(p);
			return max(QueryMaxB(lson, l, r), QueryMaxB(rson, l, r));
		}
	}t;
	int main () {
		n = Read(), m = Read();
		t.Build(1, 1, n);
		while (m--) {
			int op = Read(), l = Read(), r = Read(), val;
			if (op == 1) val = Read(), t.UpdateAdd(1, l, r, val);
			else if (op == 2) val = Read(), t.UpdateMin(1, l, r, val);
			else if (op == 3) printf ("%lld\n", t.QuerySum(1, l, r));
			else if (op == 4) printf ("%d\n", t.QueryMaxA(1, l, r));
			else printf ("%d\n", t.QueryMaxB(1, l, r));
		}
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}