题目大意： 给你n个数， 给两种操作， 一种给你l, r, k，问你[l, r]区间里的数排序后能否构成一个公差为k的等差数列。 另一种是将位置x的数变为y。 强制在线。
可以用hash来做， 用线段树保存一个区间里的最小值， 和， 以及平方的和。 然后每次询问， 假设这个区间构成等差数列，那么首项为这个区间的最小值， 然后按公式算出以minn为首项， k为公差的数列的和， 为a1*len+len*（len-1)/2*d, 然后算出平方的和， 相当于sigma(i : 0 to len-1) (a1+i*d)^2, 然后把它拆开， 就变成a1*a1*len+a1*d*len*(len-1)+d*d*len*(len-1)*(2*len-1)/6, 记得时刻取模防止爆longlong， /6那里用乘法逆元算。 然后看是否相等就可以了。
正解当然不是这样的..
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const ll mod = 1e9+;
const ll inf = 1e18;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxn = 3e5+;
ll sum1[maxn<<], sum2[maxn<<], minn[maxn<<], ans1, ans2, ans3;
void pushUp(int rt) {
sum1[rt] = sum1[rt<<]+sum1[rt<<|];
sum2[rt] = (sum2[rt<<] + sum2[rt<<|])%mod;
minn[rt] = min(minn[rt<<], minn[rt<<|]);
}
void build(int l, int r, int rt) {
if(l == r) {
scanf("%I64d", &sum1[rt]);
minn[rt] = sum1[rt];
sum2[rt] = sum1[rt]*sum1[rt]%mod;
return ;
}
int m = l+r>>;
build(lson);
build(rson);
pushUp(rt);
}
void update(int p, ll val, int l, int r, int rt) {
if(l == r) {
sum1[rt] = minn[rt] = val;
sum2[rt] = val*val%mod;
return ;
}
int m = l+r>>;
if(p<=m)
update(p, val, lson);
else
update(p, val, rson);
pushUp(rt);
}
void query(int L, int R, int l, int r, int rt) {
if(L<=l&&R>=r) {
ans1 += sum1[rt];
ans2 = (ans2+sum2[rt])%mod;
ans3 = min(ans3, minn[rt]);
return ;
}
int m = l+r>>;
if(L<=m)
query(L, R, lson);
if(R>m)
query(L, R, rson);
}
ll pow(ll a, ll b) {
ll ret = ;
while(b) {
if(b&) {
ret = ret*a%mod;
}
a = a*a%mod;
b>>=;
}
return ret;
}
ll get1(ll a1, ll l, ll d) {
ll ret = a1*l+l*(l-)/*d;
return ret;
}
ll get2(ll a1, ll l, ll d) {
ll ret = a1*a1%mod*l%mod;
ll rev = pow(6LL, mod-)%mod;
ret = (ret + d*d%mod*l%mod*(l-)%mod*(*l-)%mod*rev%mod)%mod;
ret = (ret + a1*d%mod*l%mod*(l-)%mod)%mod;
return ret%mod;
}
int main()
{
int n, m, cnt = , sign, x, y, z;
cin>>n>>m;
build(, n, );
while(m--) {
scanf("%d%d%d", &sign, &x, &y);
x ^= cnt, y ^= cnt;
if(sign == ) {
update(x, 1LL*y, , n, );
} else {
scanf("%d", &z);
z ^= cnt;
ans3 = inf, ans1 = ans2 = ;
query(x, y, , n, );
ll tmp1 = get1(ans3, y-x+, z);
ll tmp2 = get2(ans3, y-x+, z);
if(tmp1 == ans1 && tmp2 == ans2) {
cnt++;
puts("Yes");
} else {
puts("No");
}
}
}
return ;
}