算术天才⑨与等差数列
Time Limit: 10 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]
Description
算术天才⑨非常喜欢和等差数列玩耍。
有一天，他给了你一个长度为n的序列，其中第i个数为a[i]。
他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。
Input
第一行包含两个正整数n,m，分别表示序列的长度和操作的次数。
第二行包含n个整数，依次表示序列中的每个数a[i]。
接下来m行，每行一开始为一个数op，
若op=1，则接下来两个整数x,y，表示把a[x]修改为y。
若op=2，则接下来三个整数l,r,k，表示一个询问。
在本题中，x,y,l,r,k都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。
Output
输出若干行，对于每个询问，如果可以形成等差数列，那么输出Yes，否则输出No。
Sample Input
1 3 2 5 6
2 1 5 1
1 5 4
2 1 5 1
Sample Output
Yes
HINT
1<=n,m<=300000, 0<=a[i]<=10^9, 1<=x<=n，0<=y<=10^9, 1<=l<=r<=n, 0<=k<=10^9
Solution
显然，如果可以组成等差数列，首项必定是区间最小值。这样我们就知道了要求的等差数列的首项和公差。
一个首先的想法就是：我们判断一下区间和是否等于所要求的等差数列的和。
但是这样显然是不够的，那么怎么办呢？我们试想：能否求出所要求的等差数列的平方和？
显然公差为 1 的时候用平方和公式计算，剩下公差不是 1 的时候我们轻易推一下式子即可。
那么我们只要用线段树维护一下：区间最小值、区间和、区间平方和即可，资磁单点修改。
正确性不会证明啊，但是满足的概率应该挺大的吧qwq
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
using namespace std;
typedef long long s64; const int ONE = ;
const int INF = 1e9+; int n, T;
s64 a[ONE];
int opt, x, y, d;
int num; struct power
{
s64 sumx, sumxx, minx;
}Node[ONE * ], res; int get()
{
int res=,Q=;char c;
while( (c=getchar())< || c> )
if(c=='-')Q=-;
res=c-;
while( (c=getchar())>= && c<= )
res=res*+c-;
return res*Q;
} void Renew(int i)
{
int a = i<<, b = i<<|;
Node[i].sumx = Node[a].sumx + Node[b].sumx;
Node[i].sumxx = Node[a].sumxx + Node[b].sumxx;
Node[i].minx = min(Node[a].minx, Node[b].minx);
} void Build(int i, int l, int r)
{
Node[i].minx = INF;
if(l == r)
{
Node[i].minx = a[l];
Node[i].sumx = a[l];
Node[i].sumxx = a[l] * a[l];
return;
} int mid = l + r >> ;
Build(i<<, l, mid); Build(i<<|, mid+, r);
Renew(i);
} void Update(int i, int l, int r, int L, s64 x)
{
if(l > r) return;
if(L == l && l == r)
{
Node[i].minx = x;
Node[i].sumx = x;
Node[i].sumxx = x * x;
return;
} int mid = l + r >> ;
if(L <= mid) Update(i<<, l, mid, L, x);
else Update(i<<|, mid+, r, L, x);
Renew(i);
} void Query(int i, int l, int r, int L, int R)
{
if(L <= l && r <= R)
{
res.minx = min(res.minx, Node[i].minx);
res.sumx += Node[i].sumx;
res.sumxx += Node[i].sumxx;
return;
} int mid = l + r >> ;
if(L <= mid) Query(i<<, l, mid, L, R);
if(mid+ <= R) Query(i<<|, mid+, r, L, R);
} s64 Calc_sumx(s64 a0, s64 n, s64 d)
{
s64 an = a0 + (n-) * d;
return (a0 + an) * n / ;
} s64 Calc_sumxx(s64 a0, s64 n, s64 d)
{
s64 item1 = n * a0 * a0;
s64 item2 = * a0 * d * n * (n-) / ;
s64 item3 = d * d * (n * (n+) * (*n+) / - n*n);
return item1 + item2 + item3;
} int main()
{
n = get(); T = get();
for(int i=; i<=n; i++)
a[i] = get();
Build(, , n); while(T--)
{
opt = get();
x = get() ^ num; y = get() ^ num; if(opt == )
{
Update(, , n, x, y);
continue;
}
else
{
d = get() ^ num;
res.minx = INF;
res.sumx = res.sumxx = ;
Query(, , n, x, y); if(res.sumx == Calc_sumx(res.minx, y-x+, d))
if(res.sumxx == Calc_sumxx(res.minx, y-x+, d))
{
printf("Yes\n");
num++;
continue;
} printf("No\n");
}
} }