BZOJ4373: 算术天才⑨与等差数列(线段树 hash?)

题意

题目链接

Sol

正经做法不会，听lxl讲了一种很神奇的方法

我们考虑如果满足条件，那么需要具备什么条件

设mx为询问区间最大值，mn为询问区间最小值

mx - mn = (r - l) * k
区间和 = mn * len + \(\frac{n * (n - 1)}{2} k\)
\(\text{立方和} = \sum_{i = 1}^{len} (mn + (i - 1)k) ^2\)

第三条后面的可以直接推式子推出来(\(\sum_{i = 1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\))

最后的/6可以直接乘一下然后ull自然溢出。

#include<bits/stdc++.h>

#define ull unsigned long long

#define LL long long

#define Fin(x) {freopen(#x".in","r",stdin);}

#define Fout(x) {freopen(#x".out","w",stdout);}

using namespace std;

const int MAXN = 4e6 + 10;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, M;

#define ls k << 1

#define rs k << 1 | 1

struct {

	int l, r, mn, mx;

	ull s, s2;

}T[MAXN];

void update(int k) {

	T[k].mn = min(T[ls].mn, T[rs].mn);

	T[k].mx = max(T[ls].mx, T[rs].mx);

	T[k].s  = T[ls].s + T[rs].s;

	T[k].s2 = T[ls].s2 + T[rs].s2;

}

void Build(int k, int ll, int rr) {

	T[k].l = ll; T[k].r = rr;

	if(ll == rr) {T[k].mn = T[k].mx = T[k].s = read(); T[k].s2 = T[k].s * T[k].s ; return ;}

	int mid = ll + rr >> 1;

	Build(ls, ll, mid); Build(rs, mid + 1, rr);

	update(k);

}

void Modify(int k, int p, int v) {

	if(T[k].l == T[k].r) {T[k].mn = T[k].mx = T[k].s = v; T[k].s2 = T[k].s * T[k].s; return ;}

	int mid = T[k].l + T[k].r >> 1;

	if(p <= mid) Modify(ls, p, v);

	if(p  > mid) Modify(rs, p, v);

	update(k);

}

int QueryMn(int k, int ql, int qr) {

	if(ql <= T[k].l && T[k].r <= qr) return T[k].mn;

	int mid = T[k].l + T[k].r >> 1;

	if(ql > mid) return QueryMn(rs, ql, qr);

	else if(qr <= mid) return QueryMn(ls, ql, qr);

	else return min(QueryMn(ls, ql, qr), QueryMn(rs, ql, qr));

}

int QueryMx(int k, int ql, int qr) {

	if(ql <= T[k].l && T[k].r <= qr) return T[k].mx;

	int mid = T[k].l + T[k].r >> 1;

	if(ql > mid) return QueryMx(rs, ql, qr);

	else if(qr <= mid) return QueryMx(ls, ql, qr);

	else return max(QueryMx(ls, ql, qr), QueryMx(rs, ql, qr));

}

ull QuerySum(int k, int ql, int qr) {

	if(ql <= T[k].l && T[k].r <= qr) return T[k].s;

	int mid = T[k].l + T[k].r >> 1;

	if(ql > mid) return QuerySum(rs, ql, qr);

	else if(qr <= mid) return QuerySum(ls, ql, qr);

	else return QuerySum(ls, ql, qr) + QuerySum(rs, ql, qr);

}

ull QuerySum2(int k, int ql, int qr) {

	if(ql <= T[k].l && T[k].r <= qr) return T[k].s2;

	int mid = T[k].l + T[k].r >> 1;

	if(ql > mid) return QuerySum2(rs, ql, qr);

	else if(qr <= mid) return QuerySum2(ls, ql, qr);

	else return QuerySum2(ls, ql, qr) + QuerySum2(rs, ql, qr);

}

signed main() {

	N = read(); M = read();

	Build(1, 1, N);

	int GG = 0;

	while(M--) {

		int opt = read();

		if(opt == 1) {

			int x = read() ^ GG, y = read() ^ GG;

			Modify(1, x, y);

		} else {

			int l = read() ^ GG, r = read() ^ GG; ull k = read() ^ GG;

			ull n = r - l + 1, mn = QueryMn(1, l, r), mx = QueryMx(1, l, r);

			ull s = QuerySum(1, l, r), s2 = QuerySum2(1, l, r), ns = mn * n + n * (n - 1) * k / 2;

			ull gg = (6 * mn * mn * n) + (6 * mn * k * n * (n - 1))  + (k * k * (n - 1) * n * (2 * (n - 1) + 1)),

				gg2 = 6 * s2;

			if((mx - mn == (r - l) * k) &&

			   (mn * n + n * (n - 1) / 2 * k == s) &&

			   (gg  == gg2)) puts("Yes"), GG++;

			else puts("No");

		}

	}

	return 0;

}

/*

5 3

1 3 2 5 6

2 2 2 23333

1 5 4

2 1 5 1

*/

巴特西

BZOJ4373: 算术天才⑨与等差数列(线段树 hash?)

题意

Sol

最新文章

热门文章