4373: 算术天才⑨与等差数列
Time Limit: 10
Sec Memory Limit: 128 MB
Description
算术天才⑨非常喜欢和等差数列玩耍。
有一天，他给了你一个长度为n的序列，其中第i个数为a[i]。
他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。
有一天，他给了你一个长度为n的序列，其中第i个数为a[i]。
他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。
Input
第一行包含两个正整数n,m(1<=n,m<=300000)，分别表示序列的长度和操作的次数。
第二行包含n个整数，依次表示序列中的每个数a[i](0<=a[i]<=10^9)。
接下来m行，每行一开始为一个数op，
若op=1，则接下来两个整数x,y(1<=x<=n，0<=y<=10^9)，表示把a[x]修改为y。
若op=2，则接下来三个整数l,r,k(1<=l<=r<=n，0<=k<=10^9)，表示一个询问。
在本题中，x,y,l,r,k都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。
第二行包含n个整数，依次表示序列中的每个数a[i](0<=a[i]<=10^9)。
接下来m行，每行一开始为一个数op，
若op=1，则接下来两个整数x,y(1<=x<=n，0<=y<=10^9)，表示把a[x]修改为y。
若op=2，则接下来三个整数l,r,k(1<=l<=r<=n，0<=k<=10^9)，表示一个询问。
在本题中，x,y,l,r,k都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。
Output
输出若干行，对于每个询问，如果可以形成等差数列，那么输出Yes，否则输出No。
Sample Input
5 3
1 3 2 5
6
2 1 5 1
1 5 4
2 1 5 1
Sample Output
No
Yes
Solution
为了判断一个区间的数字排序后是否是等差数列，我们需要知道等差数列的特征。设数列$\{a_n\}$排序后为公差为k的等差数列，有：
$$max\{a_n\}-min\{a_n\}=\left(n-1\right)k$$
$$\sum_{i=1}^na_i=\frac{\displaystyle
n\cdot(max\{a_n\}+min\{a_n\})}{\displaystyle2}$$
以上都是等差数列的基本性质，容易想到但也容易被卡，如数列$\{1,1,4,4,5\}$满足以上两点性质，排序后却不是等差数列。
线性的关系容易被卡，我们考虑非线性的关系，比如平方和。
设$\{a_n\}$为等差数列，$qsum=\sum_{i=1}^na_i^2$
则：
$$qsum=a_1^2+\left(a_1+k\right)^2+\left(a_1+2k\right)^2+...+\lbrack
a_1+\left(n-1\right)k\rbrack^2$$
展开：
$$qsum=a_1^2+a_1^2+2a_1k+k^2+a_1^2+4a_1k+4k^2+...+a_1^2+2(n-1)k+(n-1)^2k^2$$
整理得：
$$qsum=na_1^2+\lbrack1+2+...+(n-1)\rbrack\times2a_1k+\lbrack1^2+2^2+...+(n-1)^2\rbrack
k^2$$
根据公式$\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}6$得：
$$qsum=na_1^2+\frac{\lbrack1+(n-1)\rbrack(n-1)}2\times2a_1k+\frac{(n-1)\cdot
n\cdot\lbrack2(n-1)+1\rbrack}6k^2$$
化简得：
$$qsum=na_1^2+n(n-1)a_1k+\frac{n(n-1)(2n-1)}6k^2$$
这样我们就可以用平方和校验等差数列了。虽然充要性无法证明，但不容易被卡掉。如果读者担心，还可以添加立方和所为校验。由于平方和可能造成long long溢出，所以改用unsigned long long，利用自然溢出即可，由于除法在模p域下无法直接计算，所以要在unsigned long
long未溢出前除6。
Code
//区间和+区间最大值+区间最小值+区间平方和
//由于强制在线，WA可能变成RE（异或解密时出错，导致访问越界）
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
inline void read(int &x)
{
x = 0; char ch = getchar(); bool f = 0;
while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
while (ch >= '0'&&ch
<= '9') { x = x * 10 + ch - 48; ch = getchar();
}
if (f)x = -x;
}
inline void read(long long &x)
{
x = 0; char ch = getchar(); bool f = 0;
while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
while (ch >= '0'&&ch
<= '9') { x = x * 10 + ch - 48; ch = getchar();
}
if (f)x = -x;
}
inline void read(unsigned long long &x)
{
x = 0; char ch = getchar();
while (ch>'9' || ch<'0') { ch = getchar(); }
while (ch >= '0'&&ch
<= '9') { x = x * 10 + ch - 48; ch = getchar();
}
}
struct queryresult
{
queryresult operator+(const queryresult &b)const
{
queryresult tmp;
tmp.maxn = max(maxn, b.maxn);
tmp.minn = min(minn, b.minn);
tmp.sum =
sum + b.sum;
tmp.sqrsum =
sqrsum + b.sqrsum;
return tmp;
}
unsigned long long maxn, minn;
unsigned long long sum, sqrsum;
};
struct
{
int l, r;
queryresult data;
}tree[1200001];
void build(int l, int r, int now = 1)
{
tree[now].l = l, tree[now].r = r;
if (l == r)
{
read(tree[now].data.maxn);
tree[now].data.minn =
tree[now].data.maxn;
tree[now].data.sum =
tree[now].data.maxn;
tree[now].data.sqrsum =
tree[now].data.maxn*tree[now].data.maxn;
return;
}
int mid = l + r >> 1;
build(l, mid, now << 1);
build(mid + 1, r, now << 1 |
1);
tree[now].data = tree[now <<
1].data + tree[now << 1 | 1].data;
}
void updata(int p, unsigned long long x, int now = 1)
{
if (tree[now].l == tree[now].r)
{
tree[now].data.maxn = x;
tree[now].data.minn = x;
tree[now].data.sum = x;
tree[now].data.sqrsum = x*x;
return;
}
int mid = tree[now].l + tree[now].r >> 1;
if (p <= mid)updata(p, x, now << 1);
else updata(p, x, now << 1 |
1);
tree[now].data = tree[now <<
1].data + tree[now << 1 | 1].data;
}
queryresult query(int l, int r, int now = 1)
{
if (tree[now].l == l&&tree[now].r == r)
{
return tree[now].data;
}
int mid = tree[now].l + tree[now].r >> 1;
if (r <= mid)
{
return query(l, r, now << 1);
}
else if (mid<l)
{
return query(l, r, now << 1 |
1);
}
else
{
return query(l, mid, now << 1) + query(mid + 1, r, now << 1 |
1);
}
}
int main()
{
int n, q;
read(n); read(q);
build(1, n);
unsigned long long cntyes = 0;
while (q--)
{
int op;
read(op);
if (op == 1)
{
unsigned long long x;
unsigned long long y;
read(x); read(y);
x ^=
cntyes; y ^= cntyes;
updata(x, y);
}
else
{
unsigned long long from, to;
unsigned long long k;
read(from); read(to); read(k);
from ^=
cntyes; to ^= cntyes; k ^= cntyes;
if (from == to)
{
puts("Yes");
cntyes++;
continue;
}
queryresult re = query(from, to);
unsigned long long n = to - from +
1;
unsigned long long a1 = re.minn;
if (re.maxn - a1
!= (n - 1)*k)
{
puts("No");
continue;
}
if (re.sum != ((a1
+ re.maxn)*n >> 1))
{
puts("No");
continue;
}
//先除，防止自然溢出后再除
//由于除法在modp域下无法直接计算，导致出错 ！
if (re.sqrsum !=
n*a1*a1 + n*(n - 1)*a1*k + n*(n - 1)*(2 * n - 1) / 6 * k*k)
{
puts("No");
continue;
}
puts("Yes");
cntyes++;
}
}
return 0;
}