题解 P5278 【算术天才⑨与等差数列】

· · 题解

区间 [l,\ r] 所组成的等差数列首项为 \min{a_{l\cdots r}} ，末项为 \max{a_{l\cdots r}} ，公差为 k

可以考虑求出 [l,\ r] 和这个等差数列的hash值，接着对比即可

如果将区间和作为hash值，冲突率很高，可以考虑用每个数的平方作为hash值

设该等差数列首项为 l ，公差为 k ，项数为 t

则它的hash值为

\displaystyle\sum_{a=0}^t{(l+ak)^2}

接着大力化式子

hash=\displaystyle\sum_{a=0}^t{l^2+2lak+a^2k^2} =(t+1)l^2+k\displaystyle\sum_{a=0}^t{a^2k+2la} =(t+1)l^2+k(\displaystyle\sum_{a=0}^t{a^2}+2l\sum_{a=0}^ta) =(t+1)l^2+k(\frac{t(t+1)(2t+1)}{6}+lt(t+1))

故可 O(1) 求出

此题还需要特判 l=r 及 k=0 的情况

由于我担心被卡，用了双模数，常数稍大 qaq

时间复杂度 O(n\log n)

#include <bits/stdc++.h>
using namespace std;

#define mid ((l + r) >> 1)
#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, r
const int maxn = 3e5 + 10, P1 = 1e9 + 7, P2 = 1e9 + 9, inv1 = 166666668, inv2 = 833333341;
int n, m, lastans;

struct node {
  int mn, mx, v1, v2;
  node(int x = INT_MAX, int y = 0, int _v1 = 0, int _v2 = 0) :
    mn(x), mx(y), v1(_v1), v2(_v2) {}
} tree[maxn << 2];

inline node operator + (node a, node b) {
  return node(min(a.mn, b.mn), max(a.mx, b.mx), (a.v1 + b.v1) % P1, (a.v2 + b.v2) % P2);
}

void build(int k, int l, int r) {
  if (l == r) {
    int x;
    scanf("%d", &x);
    tree[k] = node(x, x, 1ll * x * x % P1, 1ll * x * x % P2);
    return;
  }
  build(lson), build(rson);
  tree[k] = tree[k << 1] + tree[k << 1 | 1];
}

void upd(int k, int l, int r, int x, int v) {
  if (l == r) {
    tree[k] = node(v, v, 1ll * v * v % P1, 1ll * v * v % P2);
    return;
  }
  if (x <= mid) {
    upd(lson, x, v);
  } else {
    upd(rson, x, v);
  }
  tree[k] = tree[k << 1] + tree[k << 1 | 1];
}

node query(int k, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    return tree[k];
  }
  node res;
  if (ql <= mid) res = query(lson, ql, qr);
  if (qr > mid) res = res + query(rson, ql, qr);
  return res;
}

inline int getsum(int l, int k, int t, int P, int inv) {
  return (1ll * l * l % P * (t + 1) % P + k * (1ll * l * t % P * (t + 1) % P + k * (1ll * t * (t + 1) % P * (2 * t + 1) % P * inv % P))) % P;
}

inline int getsum1(int l, int r, int k) {
  return getsum(l, k, (r - l) / k, P1, inv1);
}

inline int getsum2(int l, int r, int k) {
  return getsum(l, k, (r - l) / k, P2, inv2);
}

inline int reget(int x) {
  if (x < 1) x = 1;
  if (x > n) x = n;
  return x;
}

int main() {
  scanf("%d %d", &n, &m);
  build(1, 1, n);
  int op, x, y, k; node tmp;
  while (m--) {
    scanf("%d %d %d", &op, &x, &y);
    x ^= lastans, y ^= lastans, x = reget(x);
    if (op == 1) {
      upd(1, 1, n, x, y);
      continue;
    }
    y = reget(y);
    if (x > y) swap(x, y);
    bool ans;
    scanf("%d", &k);
    k ^= lastans;
    if (x == y) {
      ans = 1;
    } else {
      tmp = query(1, 1, n, x, y);
      ans = k ? tmp.mx - tmp.mn == 1ll * k * (y - x) && getsum1(tmp.mn, tmp.mx, k) == tmp.v1 && getsum2(tmp.mn, tmp.mx, k) == tmp.v2 : tmp.mn == tmp.mx;
    }
    ans ? lastans++, puts("Yes") : puts("No");
  }
  return 0;
}