1.OJ 30277 nand
不难发现 \(nand\) 运算是有结合律的，考虑线段树。
以元素的编号作为下标建一颗线段树
难点在于线段树节点信息 \(Push\_Up\) 操作。
记操作 \(2, l, r\) 为 \(Q (l, r)\)，\(bak[0/1]\) 分别记录 \(a_{l} nand a_{i} = 0/1(l \leq i \leq r)\)的 \(i\) 的个数，\(res\) 记录 \(nand (l, r)\)
\[\begin{aligned}
Q (l, r) &= nand (l, l) \ xor \ ... \ xor \ [nand (l,mid - 1)\ nand \ nand (mid, mid)] \ xor \ ... \ xor \ [nand(l,mid - 1) \ nand \ nand (mid, r)]
\\
&= Q (l, mid - 1) \ xor \ [(nand (l, mid - 1) \ nand \ 1 =1?bak_{mid \sim r}[1]:bak_{mid \sim r}[0]) and \ 1]
\\
bak_{l \sim r}[0] &= bak_{l \sim mid - 1}[0] + bak_{mid \sim r}[nand (l,mid - 1) \ nand \ 0 = 0 ? 0:1]
\\
bak_{l \sim r}[1] &= bak_{l \sim mid - 1}[1] + bak_{mid \sim r}[nand (l,mid - 1) \ nand \ 0 = 1 ? 0:1]
\\
res_{l \sim r} &= res_{l \sim mid - 1} \ nand \ res_{mid \sim r}
\end{aligned}
\]
2.BZOJ4311 向量
\((x_1,y_1) \cdot (x,y) = x_1x+y_1y\)
两种思路
1. 斜率优化
\[\begin{aligned}
ans &= x_1x+y_1y
\\
y_1y&=ans - x_1x
\\
y_1&=-\frac{x}{y}x_1+\frac{ans}{y}
\end{aligned}
\]
令 \(y = y_1,k = -\frac{x}{y},x = x_1,b = \frac{ans}{y}\)
那么将 \((x_1,y_1)\) 当做一个坐标系上的点，维护一个下凸包，面对 \((x,y)\) 的询问就找到使 \(y = -\frac{x}{y} + ans\) 与下凸包相切的 \(ans\) 值，此为答案，维护凸包，树套树，将时间作为下标，有一个向量从 \(s\) 时刻被加入集合 \(t\)
时刻被删除，那么在 \([s, t]\) 中加入一个点 \((x,y)\)，这样就解决了动态维护凸包只能加点不能删点的问题了。
2. 线性规划
\[\begin{aligned}
(x_1,y_1) \times (x,y) &= x_1 x + y_1 y
\\
&= (\frac{x}{y} x_1 + y_1) y
\end{aligned}
\]
令 \(y = answer, k = \frac{x}{y}，x = x_1，b = y_1\)，那么相当于要维护分段函数 \(y \max (\frac{x}{y} x_i + y_i)((x_i, y_i) \in \mathcal{S})\)