自动搬运

查看原文

来自洛谷，原作者为

	HHZZLL ㄅㄆㄇㄈㄉㄊㄋㄌ

搬运于2025-08-24 22:22:13，当前版本为作者最后更新于2025-03-28 21:02:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

显然这题可以用线段树维护。

那么对于前 $3$ 个操作，即是单点修改，较为简单。

思考一下 $4,5$ 操作怎么做。也就是左右两儿子的信息怎么合并。

假设可以直接维护 $4,5$ 操作所要的答案，其实是可以维护的。

记为 $s_1,s_2$。

考虑现在左右儿子贡献为：

左区间对应 $[l,mid]$，右区间对应 $(mid,r]$。

操作 $4:$

$$ \text{LSON}:\sum_{i=l}^{mid-1}\sum_{j=i+1}^{mid}\overrightarrow{a_i}\cdot\overrightarrow{a_j}=[x_l(x_{l+1}+x_{l+2}+\cdots+x_{mid-1}+x_{mid})+x_{l+1}(x_{l+2}+x_{l+3}+\cdots+x_{mid-1}+x_{mid})+\cdots+x_{mid-1}\times x_{mid}+x_{mid}\times 0] + [y_l(y_{l+1}+y_{l+2}+\cdots+y_{mid-1}+y_{mid})+y_{l+1}(y_{l+2}+y_{l+3}+\cdots+y_{mid-1}+y_{mid})+\cdots+y_{mid-1}\times y_{mid}+y_{mid}\times 0] $$$$\text{RSON}:\sum_{i=mid+1}^{r-1}\sum_{j=i+1}^{r}\overrightarrow{a_i}\cdot\overrightarrow{a_j}=[x_{mid+1}(x_{mid+2}+x_{mid+3}+\cdots+x_{r-1}+x_r)+x_{mid+2}(x_{mid+3}+x_{mid+4}+\cdots+x_{r-1}+x_r)+\cdots+x_{r-1}\times x_{r}]+[y_{mid+1}(y_{mid+2}+y_{mid+3}+\cdots+y_{r-1}+y_r)+y_{mid+2}(y_{mid+3}+y_{mid+4}+\cdots+y_{r-1}+y_r)+\cdots+y_{r-1}\times y_{r}] $$

当你合并他们时，是 $x$ 加它所对应的部分，$y$ 也同理。

所以我们考虑清楚一个那另一个也会了。这里我们考虑 $x$。

左儿子区间的点 $i$ 需要加 $x_i(x_{mid+1}+x_{mid+2}+\cdots+x_{r-1}+x_r)(i\in[l,mid])$，再根据乘法结合律，所以就是 $s_1 = s_{1_{RS}}+s_{1_{LS}} + \sum_{i=l}^{mid}x_i \times \sum_{i=mid+1}^r x_i$。

发现还需要用到区间 $x,y$ 和，顺便维护。

操作 $5:$

$$ \text{LSON}:\sum\limits_{i=l}^{mid-1}\sum\limits_{j=i+1}^{mid}\overrightarrow{a_i}\oplus\overrightarrow{a_j}=[x_l(y_{l+1}+y_{l+2}+\cdots+y_{mid-1}+y_{mid})+x_{l+1}(y_{l+2}+y_{l+3}+\cdots+y_{mid-1}+y_{mid})+\cdots+x_{mid-1}\times y_{mid}+x_{mid}\times 0]+[-y_l(x_{l+1}+x_{l+2}+\cdots+x_{mid-1}+x_{mid})-y_{l+1}(x_{l+2}+x_{l+3}+\cdots+x_{mid-1}+x_{mid})-\cdots-y_{mid-1}\times x_{mid}-y_{mid}\times 0] $$$$ \text{RSON}:\sum\limits_{i=mid+1}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\oplus\overrightarrow{a_j}=[x_{mid+1}(y_{mid+2}+y_{mid+3}+\cdots+y_{r-1}+y_{r})+x_{mid+2}(y_{mid+3}+y_{mid+4}+\cdots+y_{r-1}+y_{r})+\cdots+x_{r-1}\times y_{r}]+[-y_{mid+1}(x_{mid+2}+x_{mid+3}+\cdots+x_{r-1}+x_{r})-y_{mid+2}(x_{mid+3}+x_{mid+4}+\cdots+x_{r-1}+x_{r})-\cdots-y_{r-1}\times x_{r}] $$

由于前面已经维护了 $x,y$ 和。

这里记作 $sX,sY$。

对于 $x$，那么 $i$ 加上 $x_i(y_{mid+1}+y_{mid+2}+\cdots+y_{r-1}+y_{r})(i\in[l,mid])$，$y$ 也同理，只不过前面有负号。

所以，$s_2=s_{2_{RS}}+s_{2_{LS}}+sX_{LS}\times sY_{RS}-sY_{LS}\times sX_{RS}$。

现在我们就完成了合并。

在求解答案时，应是找到完全相等区间，再用上述步骤合并。

AC CODE:

#include <bits/stdc++.h>
#define int long long
namespace My {
    #define X first
    #define Y second
    #define vec vector
    #define p_b push_back
    #define rep(i, a, b) for(int i = a; i <= b; i++)
    #define lop(i, b, a) for(int i = b; i >= a; i--)
} using namespace My;
const int N = 1e5 + 5;
int n, m;
struct Vector {
	int x, y;
	Vector operator * (int lambda) {
		return {lambda * x, lambda * y};
	}
	friend Vector operator + (const Vector &a, const Vector &b) {
		return {a.x + b.x, a.y + b.y};
	}
	friend Vector operator - (const Vector &a, const Vector &b) {
		return {a.x - b.x, a.y - b.y};
	}
	friend int operator * (const Vector &a, const Vector &b) {
		return a.x * b.x + a.y * b.y;
	}
	friend int operator ^ (const Vector &a, const Vector &b) {
		return a.x * b.y - b.x * a.y;
	}
} c[N];
namespace SegmentTree {
#define ls k << 1
#define rs k << 1 | 1
	struct State {
		int l, r;
		int sX, sY;
		int sum1, sum2;
		bool operator ! () const {
			return !l && !r && !sX && !sY && !sum1 && !sum2;
		}
		friend State operator + (const State &Ls, const State &Rs) { // 合并
			State up;
			up.l = Ls.l, up.r = Rs.r;
			up.sX = Ls.sX + Rs.sX;
			up.sY = Ls.sY + Rs.sY;
			up.sum1 = Ls.sum1 + Rs.sum1 + Rs.sX * Ls.sX + Rs.sY * Ls.sY;
			up.sum2 = Ls.sum2 + Rs.sum2 + Rs.sY * Ls.sX - Rs.sX * Ls.sY;
			return up;
		}
	} tr[N << 2], ans;
	void pushup(int k) {
		tr[k] = tr[ls] + tr[rs];
	}
	void build(int k, int l, int r) {
		tr[k].l = l, tr[k].r = r;
		if(l == r) {
			tr[k].sX = c[l].x, tr[k].sY = c[l].y; // 一个单点是一个向量
			return;
		}
		build(ls, l, (l + r) / 2), build(rs, (l + r) / 2 + 1, r);
		pushup(k);
	}
#define l tr[k].l
#define r tr[k].r
#define mid (l + r) / 2
	void alter(int k, int p, Vector v, int op) {
		if(l == r && l == r) {
			c[l] = (op == -1 ? c[l] - v : c[l] + v);
			tr[k].sX += op * v.x, tr[k].sY += op * v.y;
			return;
		}
		p <= mid ? alter(ls, p, v, op) : alter(rs, p, v, op);
		pushup(k);
	}
	void cover(int k, int p, int lambda) {
		if(l == r && l == p) {
			c[l] = c[l] * lambda;
			tr[k].sX *= lambda, tr[k].sY *= lambda;
			return;
		}
		p <= mid ? cover(ls, p, lambda) : cover(rs, p, lambda);
		pushup(k);
	}
	void query(int k, int x, int y) {
		if(x == l && r == y) { // 完全相等区间
			if(!ans) ans = tr[k];
			else ans = ans + tr[k];
			return;
		}
		if(y <= mid) query(ls, x, y);
		else if(x > mid) query(rs, x, y);
		else query(ls, x, mid), query(rs, mid + 1, y);
	}
#undef l
#undef r
} using namespace SegmentTree;
signed main() {
	rd(n, m);
	rep(i, 1, n) c[i] = {rd(), rd()};
	build(1, 1, n);
	for(int op, i, x, y; m--;) {
		rd(op);
		if(op <= 2) {
			rd(i, x, y);
			alter(1, i, (Vector){x, y}, op == 1 ? 1 : -1);
		}
		else if(op == 3) {
			rd(i, x);
			cover(1, i, x);
		}
		else {
			rd(x, y), ans = {0, 0, 0, 0, 0, 0};
			query(1, x, y);
			wr(op == 4 ? ans.sum1 : ans.sum2, '\n');
		}
	}
    return 0;
}