• 周四. 8月 11th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

P5278 算术天才⑨与等差数列

admin

11月 28, 2021

给定一个长度为 (n) 的序列,第 (i) 个数为 (a_i)

进行以下操作:

  • 单点修改
  • 查询区间排完序是否是个公差为 (k) 的等差数列

(1leq n,mleq 3 imes10^5, 0leq a_i,y,kleq10^9)

solution:

一种新方法:维护区间的平方和的 (hash)

如果这个区间为等差数列,首项为 (x) ,公差为 (k) ,项数为 (n) 那么就有

[hash = sum_{i = 0}^{i = n – 1}(x + ki)^2 \
= sum_{i = 0}^{i = n – 1}(x^2 + 2kix + k^2i^2)\~~
= nx^2 + 2ksum_{i = 0}^{i = n – 1}ix + k^2sum_{i = 0}^{i = n – 1}i^2
]

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

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

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

维护两个 hash 值,线段树维护两个区间平方和,最后比较是否相等就可以判断等差数列了

/*
work by:Ariel_
inv[10^9 + 7] = 166666668
inv[10^9 + 9] = 833333341
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define rg register
#define lson rt << 1
#define rson rt << 1 | 1
#define mid ((tree[rt].l + tree[rt].r) >> 1) 
using namespace std;
const int N = 3e5 + 100;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
const int INF = 0x7fffffff;
typedef long long ll;
int read(){	
    int x = 0,f = 1; char c = getchar();
    while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
    return x*f;
}
int a[N];
struct Tree{int l, r, min, val1, val2;}tree[N << 2];
void push_up(int rt) {
   tree[rt].min = min(tree[lson].min, tree[rson].min);
   tree[rt].val1 = (tree[lson].val1 + tree[rson].val1) % mod1;
   tree[rt].val2 = (tree[lson].val2 + tree[rson].val2) % mod2;
}
void build(int rt, int l, int r) {
  tree[rt].l = l, tree[rt].r = r;
  if (l == r) {
    tree[rt].min = a[l];
    tree[rt].val1 = (ll(a[l]) * a[l]) % mod1;
    tree[rt].val2 = (ll(a[l])* a[l]) % mod2;
    return ;
  } 
  build(lson, l, mid), build(rson, mid + 1, r);
  push_up(rt); 
}
int query_min(int rt, int L, int R) {
   if (L <= tree[rt].l && tree[rt].r <= R) return tree[rt].min;
   int res = INF;
   if (L <= mid) res = min(res, query_min(lson, L, R));
   if (R > mid) res = min(res, query_min(rson, L, R));
   return res;
}
int query_val1(int rt, int L, int R) {
   if (L <= tree[rt].l && tree[rt].r <= R) return tree[rt].val1;
   int res = 0;
   if (L <= mid) res += query_val1(lson, L, R),  res %= mod1;
   if (R > mid) res += query_val1(rson, L, R), res %= mod1;
   return res;
}
int query_val2(int rt, int L, int R) {
   if (L <= tree[rt].l && tree[rt].r <= R) return tree[rt].val2;
   int res = 0;
   if (L <= mid) res += query_val2(lson, L, R), res %= mod2;
   if (R > mid) res += query_val2(rson, L, R), res %= mod2;
   return res;
} 
void modify(int rt, int pos, int k) {
    if (tree[rt].l == tree[rt].r) {
       tree[rt].min = k;
       tree[rt].val1 = (ll(k) * k) % mod1;
       tree[rt].val2 = (ll(k) * k) % mod2;
       return ; 
	}
	if (pos <= mid) modify(lson, pos, k);
	else modify(rson, pos, k);
	push_up(rt);
}
int solve(ll x, ll n, ll k, ll mod){
	x %= mod,n %= mod,k %= mod;
	ll res = 0;
	res += ((ll(n) * x % mod) * x) % mod, res %= mod;
	res += (((ll(n) * (n - 1)  % mod) * k % mod) * x) % mod,res %= mod;
	res += (((((ll(k) * k  % mod) * n % mod) * (n - 1) % mod) * (2 * n - 1) % mod) * ((mod == 1e9 + 7) ? 166666668 : 833333341)) % mod,res %= mod;
	return res % mod;
}
bool Check(int l, int r, int k) {
    int n = r - l + 1, x = query_min(1, l, r);
    return query_val1(1, l, r) == solve(x, n, k, mod1) && (query_val2(1, l, r) == solve(x, n, k, mod2));
}
int n, m, opt, cnt;
int main(){
   //freopen("a.in", "r", stdin);
   n = read(), m = read();
   for (int i = 1; i <= n; i++) a[i] = read();
   build(1, 1, n);
   for (int i = 1; i <= m; i++) {
   	  int opt = read();
   	  if (opt == 1) {
   	     int x = read(), y = read();
   	     modify(1, x ^ cnt, y ^ cnt);
	  }
	  else {
	  	int l = read(), r = read(), k = read();
		Check(l ^ cnt, r ^ cnt, k ^ cnt) ? cnt++, printf("Yes
") : printf("No
");
	  }
   }
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。