欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ4373: 算术天才⑨与等差数列(线段树 hash?)

程序员文章站 2023-02-14 23:35:40
题意 "题目链接" Sol 正经做法不会,听lxl讲了一种很神奇的方法 我们考虑如果满足条件,那么需要具备什么条件 设mx为询问区间最大值,mn为询问区间最小值 1. mx mn = (r l) k 2. 区间和 = mn len + $\frac{n (n 1)}{2} k$ 3. $\text{ ......

题意

题目链接

sol

正经做法不会,听lxl讲了一种很神奇的方法

我们考虑如果满足条件,那么需要具备什么条件

设mx为询问区间最大值,mn为询问区间最小值

  1. mx - mn = (r - l) * k

  2. 区间和 = mn * len + \(\frac{n * (n - 1)}{2} k\)

  3. \(\text{立方和} = \sum_{i = 1}^{len} (mn + (i - 1)k) ^2\)

第三条后面的可以直接推式子推出来(\(\sum_{i = 1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\))

最后的/6可以直接乘一下然后ull自然溢出。

#include<bits/stdc++.h> 
#define ull unsigned long long 
#define ll long long 
#define fin(x) {freopen(#x".in","r",stdin);}
#define fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int maxn = 4e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    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 n, m;
#define ls k << 1
#define rs k << 1 | 1
struct {
    int l, r, mn, mx;
    ull s, s2;
}t[maxn];
void update(int k) {
    t[k].mn = min(t[ls].mn, t[rs].mn);
    t[k].mx = max(t[ls].mx, t[rs].mx);
    t[k].s  = t[ls].s + t[rs].s;
    t[k].s2 = t[ls].s2 + t[rs].s2;
}
void build(int k, int ll, int rr) {
    t[k].l = ll; t[k].r = rr;
    if(ll == rr) {t[k].mn = t[k].mx = t[k].s = read(); t[k].s2 = t[k].s * t[k].s ; return ;}
    int mid = ll + rr >> 1;
    build(ls, ll, mid); build(rs, mid + 1, rr);
    update(k);
}
void modify(int k, int p, int v) {
    if(t[k].l == t[k].r) {t[k].mn = t[k].mx = t[k].s = v; t[k].s2 = t[k].s * t[k].s; return ;}
    int mid = t[k].l + t[k].r >> 1;
    if(p <= mid) modify(ls, p, v);
    if(p  > mid) modify(rs, p, v);
    update(k);
}
int querymn(int k, int ql, int qr) {
    if(ql <= t[k].l && t[k].r <= qr) return t[k].mn;
    int mid = t[k].l + t[k].r >> 1;
    if(ql > mid) return querymn(rs, ql, qr);
    else if(qr <= mid) return querymn(ls, ql, qr);
    else return min(querymn(ls, ql, qr), querymn(rs, ql, qr));
}
int querymx(int k, int ql, int qr) {
    if(ql <= t[k].l && t[k].r <= qr) return t[k].mx;
    int mid = t[k].l + t[k].r >> 1;
    if(ql > mid) return querymx(rs, ql, qr);
    else if(qr <= mid) return querymx(ls, ql, qr);
    else return max(querymx(ls, ql, qr), querymx(rs, ql, qr));
}
ull querysum(int k, int ql, int qr) {
    if(ql <= t[k].l && t[k].r <= qr) return t[k].s;
    int mid = t[k].l + t[k].r >> 1;
    if(ql > mid) return querysum(rs, ql, qr);
    else if(qr <= mid) return querysum(ls, ql, qr);
    else return querysum(ls, ql, qr) + querysum(rs, ql, qr);
}
ull querysum2(int k, int ql, int qr) {
    if(ql <= t[k].l && t[k].r <= qr) return t[k].s2;
    int mid = t[k].l + t[k].r >> 1;
    if(ql > mid) return querysum2(rs, ql, qr);
    else if(qr <= mid) return querysum2(ls, ql, qr);
    else return querysum2(ls, ql, qr) + querysum2(rs, ql, qr);
}
signed main() {
    n = read(); m = read();
    build(1, 1, n); 
    int gg = 0;
    while(m--) {
        int opt = read();
        if(opt == 1) {
            int x = read() ^ gg, y = read() ^ gg;
            modify(1, x, y);
        } else {
            int l = read() ^ gg, r = read() ^ gg; ull k = read() ^ gg;
            ull n = r - l + 1, mn = querymn(1, l, r), mx = querymx(1, l, r);
            ull s = querysum(1, l, r), s2 = querysum2(1, l, r), ns = mn * n + n * (n - 1) * k / 2;
            ull gg = (6 * mn * mn * n) + (6 * mn * k * n * (n - 1))  + (k * k * (n - 1) * n * (2 * (n - 1) + 1)), 
                gg2 = 6 * s2;
            if((mx - mn == (r - l) * k) && 
               (mn * n + n * (n - 1) / 2 * k == s) &&
               (gg  == gg2)) puts("yes"), gg++;
            else puts("no");
        }
    }
    return 0;
}
/*
5 3
1 3 2 5 6
2 2 2 23333
1 5 4
2 1 5 1
*/