数据结构训练

树状数组

电子速度

题意：平面 \(n\) 个电子，初始速度分别为 \(\vec{v_i}\)，飙升系数 \(\sum_{1\le i\lt j\le n}|v_i\times v_j|^2\)，有两种操作:

• 1 p x y: 将 \(\vec{v_p}\) 改为 \((x, y)\)
• 2 l r: 询问 \([l,r]\) 这段区间内的电子的飘升系数

共 \(m\) 个，答案对 20170927 取模。

??利用叉积公式，不妨设 \(v_i=(x_i,y_i)\)，则飙升系数为

所以可以用树状数组维护 \(x_i,y_i,x_iy_i\) 的前缀和计算。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 1e6 + 5, MOD = 20170927;

int n, m;
int a[N], b[N], c[N];
int u[N], v[N];

void update(int k, int x, int y) {
	for (; k <= n; k += k & -k) {
		a[k] = (a[k] + 1ll * x * x % MOD) % MOD;
		b[k] = (b[k] + 1ll * y * y % MOD) % MOD;
		c[k] = (c[k] + 1ll * x * y % MOD) % MOD;
	}
}

void clear(int k, int x, int y) {
	for (; k <= n; k += k & -k) {
		a[k] = (a[k] - 1ll * x * x % MOD + MOD) % MOD;
		b[k] = (b[k] - 1ll * y * y % MOD + MOD) % MOD;
		c[k] = (c[k] - 1ll * x * y % MOD + MOD) % MOD;
	}
}

int sum(int k, int *arr) {
	int res = 0;
	for (; k; k -= k & -k) (res += arr[k]) %= MOD;
	return res;
}

int main() 
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d", &u[i], &v[i]);
		update(i, u[i], v[i]);
	}
	int op, p, x, y;
	while (m--) {
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d%d%d", &p, &x, &y);
			clear(p, u[p], v[p]);
			update(p, x, y);
			u[p] = x, v[p] = y;
		}
		else if (op == 2) {
			scanf("%d%d", &x, &y);
			int sa = (sum(y, a) - sum(x - 1, a) + MOD) % MOD;
			int sb = (sum(y, b) - sum(x - 1, b) + MOD) % MOD;
			int sc = (sum(y, c) - sum(x - 1, c) + MOD) % MOD;
			printf("%lld\n", (1ll * sa * sb % MOD - 1ll * sc * sc % MOD + MOD) % MOD);
		}
	}
    return 0;
}

RMQ 问题

矩阵最值

题意：给出一个 \(n\) 行 \(m\) 列的矩阵，有 \(k\) 个问题，询问以 \(x_1\) 行 \(y_1\) 列为左上角，以 \(x_2\) 行 \(y_2\) 列为右下角的子矩阵的最大值。

??考虑 \(f[i][j][p][q]\) 以 \((i,j)\) 为左上角，向下、向右延伸 \(2^p,2^q\) 的子矩阵的最大值，\(dp[i][j][0][0]\) 为本身。

• \(p\neq0,q=0\)，转化为一维 RMQ 有

• \(p=0,q\neq0\)，转化为一维 RMQ 有

• \(p\neq0,q\neq0\)，矩阵分成左右或上下两个部分，前面均处理过，直接取 \(\max\)

询问时从左上角、左下角、右上角、右下角转移过来，时间复杂度 \(O(nm\log(n)\log(m))\)。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 255;

int n, m, k;
int lg[N], f[N][N][8][8];

int query(int ax, int ay, int bx, int by) {
	int p = lg[bx-ax+1];
	int q = lg[by-ay+1];
	bx = bx - (1<<p) + 1;
	by = by - (1<<q) + 1;
	return max(max(f[ax][ay][p][q], f[ax][by][p][q]), max(f[bx][ay][p][q], f[bx][by][p][q]));
}

int main() 
{
	scanf("%d%d%d", &n, &m, &k);
	lg[0] = -1;
	for (int i = 1; i <= max(n, m); ++i) lg[i] = lg[i>>1] + 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &f[i][j][0][0]);
		}
	}
	for (int p = 0; p <= lg[n]; ++p) {
		for (int q = 0; q <= lg[m]; ++q) {
			if (!(p + q)) continue;
			for (int i = 1; i + (1<<p) - 1 <= n; ++i) {
				for (int j = 1; j + (1<<q) - 1 <= m; ++j) {
					if (p) f[i][j][p][q] = max(f[i][j][p-1][q], f[i+(1<<p-1)][j][p-1][q]);
					else f[i][j][p][q] = max(f[i][j][p][q-1], f[i][j+(1<<q-1)][p][q-1]);
				}
			}
		}
	}
	int ax, ay, bx, by;
	while (k--) {
		scanf("%d%d%d%d", &ax, &ay, &bx, &by);
		printf("%d\n", query(ax, ay, bx, by));
	}
    return 0;
}

线段树

数据结构训练

原文：https://www.cnblogs.com/2inf/p/14770373.html