Solution 算术天才⑨与等差数列

题目大意:给定一个长度为(n)的数列,每次询问([l,r])可否重排成一个公差为(k)的等差数列,强制在线

(hash)

分析:

前置芝士:P3792 由乃与大母神原型和偶像崇拜
~~虽然不用做这题也行~~

如果你做过上面一题,大概就会对用类似于(hash)的思想来解决数列重排问题有一定的了解,这题我们用类似的思路,维护区间平方和:

首先,我们设这个等差数列的首项为(x),项数为(n),公差为(k),那么:

[hash = sum_{i = 0}^{n - 1}{(x + ik) ^ 2} ]

平方差公式打开括号:

[hash = sum_{i = 0}^{n - 1}{(x ^ 2 + 2xik + i^2k^2)} ]

[= nx^2 + 2xksum_{i = 0}^{n - 1}{i} + k^2sum_{i = 0}^{n - 1}{i^2} ]

然后：

[sum_{i = 0}^{n - 1}i = frac{(0 + n - 1) imes n}{2} = frac{n(n-1)}{2} ]

[sum_{i = 0}^{n - 1}i^2 = frac{(n - 1) imes n imes[2(n - 1) + 1]}{6} = frac{n(n-1)(2n-1)}{6} ]

[ herefore hash = nx^2 + xkn(n-1) + frac{k ^ 2n(n-1)(2n-1)}{6} ]

然后我们来选择模数:~~您可以尝试选择某八位质数,感受东方神秘力量~~

(10^9 + 7)和(10^9 + 9)是一对孪生素数,就选择它们了,因为涉及到除法,所以在取模意义下我们只能乘它们的逆元

[6^{-1} equiv 166666668(mod;10^9+7) ]

[6^{-1} equiv 833333341(mod;10^9+9) ]

然后线段树维护一下区间(min)即可求出首项,上代码:

注意:代码中运用了C++新特性,请使用C++17编译

#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 100,mod1 = 1e9 + 7,mod2 = 1e9 + 9,INF = 0x7fffffff;
template <typename T>
inline T min(const T &a,const T &b){return a < b ? a : b;}
int val[maxn];
inline int read(){
	int x = 0;char c = getchar();
	while(c < '0' || c > '9')c = getchar();
	while(c >= '0' && c <= '9')x = x * 10 + c - '0',c = getchar();
	return x;
}
namespace ST{
	struct Node{
		int l,r,val1,val2,valm; 
	}tree[maxn << 2];
	#define lson (root << 1)
	#define rson (root << 1 | 1)
	#define mid ((tree[root].l + tree[root].r) >> 1)
	inline void maintain(int root){
		tree[root].valm = min(tree[lson].valm,tree[rson].valm);
		tree[root].val1 = (tree[lson].val1 + tree[rson].val1) % mod1;
		tree[root].val2 = (tree[lson].val2 + tree[rson].val2) % mod2;
	}
	void build(int a,int b,int root = 1){
		tree[root].l = a;
		tree[root].r = b;
		if(a == b){
			tree[root].valm = val[a];
			tree[root].val1 = (ll(val[a]) * val[a]) % mod1;
			tree[root].val2 = (ll(val[a]) * val[a]) % mod2;
			return;
		}
		build(a,mid,lson);
		build(mid + 1,b,rson);
		maintain(root);
	}
	int query_min(int a,int b,int root = 1){
		if(a <= tree[root].l && b >= tree[root].r)return tree[root].valm;
		int ret = 0x7fffffff;
		if(a <= mid)ret = min(ret,query_min(a,b,lson));
		if(b >= mid + 1)ret = min(ret,query_min(a,b,rson));
		return ret;
	}
	int query_val1(int a,int b,int root = 1){
		if(a <= tree[root].l && b >= tree[root].r)return tree[root].val1;
		int ret = 0;
		if(a <= mid)ret += query_val1(a,b,lson),ret %= mod1;
		if(b >= mid + 1)ret += query_val1(a,b,rson),ret %= mod1;
		return ret;
	}
	int query_val2(int a,int b,int root = 1){
		if(a <= tree[root].l && b >= tree[root].r)return tree[root].val2;
		int ret = 0;
		if(a <= mid)ret += query_val2(a,b,lson),ret %= mod2;
		if(b >= mid + 1)ret += query_val2(a,b,rson),ret %= mod2;
		return ret;
	}
	void modify(int pos,int val,int root = 1){
		if(tree[root].l == tree[root].r){
			tree[root].valm = val;
			tree[root].val1 = (ll(val) * val) % mod1;
			tree[root].val2 = (ll(val) * val) % mod2;
			return;
		}
		if(pos <= mid)modify(pos,val,lson);
		else modify(pos,val,rson);
		maintain(root);
	}
	#undef lson
	#undef rson
}
using namespace ST;
inline int solve(ll x,ll n,ll k,ll mod){
	x %= mod,n %= mod,k %= mod;
	ll ret = 0;
	ret += ((ll(n) * x % mod) * x) % mod,ret %= mod;
	ret += (((ll(n) * (n - 1)  % mod) * k % mod) * x) % mod,ret %= mod;
	ret += (((((ll(k) * k  % mod) * n % mod) * (n - 1) % mod) * (2 * n - 1) % mod) * ((mod == 1e9 + 7) ? 166666668 : 833333341)) % mod,ret %= mod;
	return ret % mod;
}
inline bool check(int l,int r,int k){
	int x = query_min(l,r),n = r - l + 1;
	return (query_val1(l,r) == solve(x,n,k,mod1)) && (query_val2(l,r) == solve(x,n,k,mod2));
}
int n,m,cnt;
int main(){
	n = read(),m = read();
	for(int i = 1;i <= n;i++)val[i] = read();
	build(1,n);
	while(m--){
		if(int x,y,l,r,k;read() == 1){//if语句和switch语句内定义变量,其在else语句内也有效,是C++17的新特性
			x = read(),y = read();
			modify(x ^ cnt,y ^ cnt);
		}else{
			l = read(),r = read(),k = read();
			check(l ^ cnt,r ^ cnt,k ^ cnt) ? cnt++,printf("Yes
") : printf("No
");
		}
	}
	return 0;
}