CF1195E OpenStreetMap

请不要在意为什么我写二维线段树 qwq

我用了点奇淫巧计，不用动态开点实现两倍空间存储，来源 https://www.luogu.com/discuss/531072?page=2

然后本地过了 Test #8

input
3000 10 1 6
709202316 281605678 503016091 999999937
 
output
2163727770023

结果交上去莫名 wa 了https://codeforces.com/problemset/submission/1195/286010430

求解释。

#include <bits/stdc++.h>
#define re register int 
#define lp mid << 1
#define rp mid << 1 | 1

using namespace std;
typedef long long LL;
const int N = 3e3 + 10, inf = 1e9 + 10;

int n, m, a, b, c[N][N];
LL g[N];
int t[N << 1][N << 1], mn;

inline void init()
{
	int x, y, z;
	cin >> n >> m >> a >> b;
	cin >> g[0] >> x >> y >> z;
	for (re i = 1; i <= n * m; i ++) g[i] = (g[i - 1] * x + y) % z;
	for (re i = 1; i <= n; i ++)
		for (re j = 1; j <= m; j ++) c[i][j] = g[(i - 1) * m + j - 1];

	memset(t, 0x3f, sizeof(t));
}

inline void update_y(int layer, int p, int l, int r, int y, int k)
{
	t[layer][p] = min(t[layer][p], k);
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (y <= mid) update_y(layer, lp, l, mid, y, k);
	if (y > mid) update_y(layer, rp, mid + 1, r, y, k);
}

inline void update_x(int p, int l, int r, int x, int y, int k)
{
	update_y(p, 1, 1, m, y, k);
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (x <= mid) update_x(lp, l, mid, x, y, k);
	if (x > mid) update_x(rp, mid + 1, r, x, y, k);
}

inline void ask_y(int layer, int p, int l, int r, int yu, int yd)
{
	if (yu <= l && r <= yd)
	{
		mn = min(mn, t[layer][p]);
		return;
	}
	int mid = (l + r) >> 1;
	if (yu <= mid) ask_y(layer, lp, l, mid, yu, yd);
	if (yd > mid) ask_y(layer, rp, mid + 1, r, yu, yd);
}

inline void ask_x(int p, int l, int r, int xp, int yp, int xq, int yq)
{
	if (xp <= l && r <= xq)
	{
		ask_y(p, 1, 1, m, yp, yq);
		return;
	}
	int mid = (l + r) >> 1;
	if (xp <= mid) ask_x(lp, l, mid, xp, yp, xq, yq);
	if (xq > mid) ask_x(rp, mid + 1, r, xp, yp, xq, yq);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	init();
	for (re i = 1; i <= n; i ++)
		for (re j = 1; j <= m; j ++)
			update_x(1, 1, n, i, j, c[i][j]);
	LL sum = 0;
	for (re i = 1; i + a - 1 <= n; i ++)
		for (re j = 1; j + b - 1 <= m; j ++)
		{
			int xlu = i, ylu = j;
			int xrd = i + a - 1, yrd = j + b - 1;
			mn = inf;
			ask_x(1, 1, n, xlu, ylu, xrd, yrd);	
			sum += mn;
		}	
	cout << sum << '\n';
	
	return 0;	
}