专栏首页数据结构与算法BZOJ4373: 算术天才⑨与等差数列(线段树 hash?)

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

题意

题目链接

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
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷P3586 [POI2015]LOG(贪心 权值线段树)

    attack
  • 判断数组内是否有几个元素之和等于m

    1 #include<iostream> 2 using namespace std; 3 int a[10001]; 4 int f(int n,in...

    attack
  • loj#6033. 「雅礼集训 2017 Day2」棋盘游戏(二分图博弈)

    对于某个点,若它一定在最大匹配上,那么Bob必胜。因为Bob可以一直沿着匹配边都,Alice只能走非匹配边。到最后一定是Alice不能移动。

    attack
  • 欧拉计划 Problem7

    题目: 第10001个素数 列出前6个素数,它们分别是2、3、5、7、11和13。我们可以看出,第6个素数是13。

    用户4492257
  • leetcode-179-Largest Number(理解规则,自定义cmp函数进行排序)

    1、这道题给定一个vector,里面存放着int类型的非负整数,要求把这些非负整数拼起来,尽可能拼成一个最大的整数。

    chenjx85
  • Glide缓存流程

    Android上图片加载的解决方案有多种,但是官方认可的是Glide。Glide提供简洁易用的api,整个框架也方便扩展,比如可以替换网络请求库,同时也提供了完...

    2020labs小助手
  • 聊聊rocketmq的ExpressionForRetryMessageFilter

    本文主要研究一下rocketmq的ExpressionForRetryMessageFilter

    codecraft
  • LWC 59:728. Self Dividing Numbers

    LWC 59:728. Self Dividing Numbers 传送门:728. Self Dividing Numbers Problem: A sel...

    用户1147447
  • OKHttp源码解析(四)--中阶之拦截器及调用链

    那我们书接上文。上篇文章已经说明了OKHttp有两种调用方式,一种是阻塞的同步请求,一种是异步的非阻塞的请求。但是无论同步还是异步都会调用下RealCall的 ...

    隔壁老李头
  • 聊聊rocketmq的ExpressionForRetryMessageFilter

    本文主要研究一下rocketmq的ExpressionForRetryMessageFilter

    codecraft

扫码关注云+社区

领取腾讯云代金券