首页 > 其他分享 >洛谷 P1438 无聊的数列

洛谷 P1438 无聊的数列

时间:2024-01-31 22:11:48浏览次数:49  
标签:洛谷 数列 标记 int 线段 公差 首项 等差数列 P1438

这题题解的做法千奇百怪,有写了两棵线段树的,有线段树套差分的,还有线段树套二阶差分的。我承认是我看不懂所以我决定写一篇只用一棵线段树的题解。

分析

众所周知,普通线段树的懒标记存的是一个待更新的量。那对于这个题来说,直接存和(也就是 add 操作在这个线段上的影响)肯定是不切实际的,因为知道了这个线段上待更新的和之后并不能很方便的计算出两个子线段上待更新的和。那既然不能直接存,那就间接存。我们可以把懒标记稍微改一下,使得这个懒标记可以很方便的传递,并且通过懒标记可以推出唯一的等差数列。这时,你可能已经想到了:可以在懒标记上存下等差数列的首项和公差,这样传递也方便,计算也方便。那么现在每个节点上的懒标记就是首项和公差,它代表了一个等差数列。所以每个节点上的懒标记都是一个等差数列

对于下传来说,我们可以直接把两个懒标记上的首项相加,公差相加,就完成了下传。这样的正确性显而易见。设有两个等长的等差数列 \(a\) 和 \(b\),\(a\) 的首项是 \(s_1\),公差是 \(d_1\),\(b\) 的首项是 \(s_2\),公差是 \(d_2\),长度都为 \(l\),则他们的和就是 \(s_1*l+s_2*l+l*[(l-1)/2]*d_1+l*[(l-1)/2]*d_2\),也就是 \((s_1+s_2)*l+l*[(l-1)/2]*(d_1+d_2)\),也就相当于一个首项为 \((s_1+s_2)\),公差为 \((d_1+d_2)\) 的等差数列的和。

对于计算来说,我觉得我不用多说。等差数列求和公式大家应该都会。

需要注意的是,在传递懒标记给右儿子时,首项需要改变,打懒标记的时候首项也要根据该线段左端点与 add 区间左端点的距离改变。

代码

#include <iostream>
#define int long long                           // 三年OI一场空,不开long long见祖宗!!!
#define st first
#define dif second
using namespace std;
const int N = 131072;
int arr[N * 4], sm[N * 4];
pair<int, int> tag[N * 4];
void Build(int o, int l, int r) {
    if (l == r) {
        sm[o] = arr[l];
        return;
    }
    int mid = l + r >> 1;
    Build(o << 1, l, mid);                     // 建左儿子
    Build(o << 1 | 1ll, mid + 1, r);           // 建右儿子
    sm[o] = sm[o << 1] + sm[o << 1 | 1ll];     // 上传
}
inline int getsum(int l, int r, int L, int R, int k, int d) { // 已知公差和 add 区间与当前区间的求和
    int bg = k + d * (l - L);                  // 求首项
    int ed = k + d * (r - L);                  // 求末项
    return (bg + ed) * (r - l + 1) / 2;        // 求和
}
inline int getsum2(int bg, int dif, int l) {  // 已知首项 公差 长度的求和
    int ed = bg + dif * (l - 1);              // 求末项
    return (bg + ed) * l / 2;                 // 求和
}
void pushdown(int o, int l, int r) {
    if (tag[o].st == 0 && tag[o].dif == 0) 
        return;
    int nst = tag[o].st, ndif = tag[o].dif;   // 当前区间懒标记的首项及公差
    int mid = l + r >> 1;
    tag[o].st = tag[o].dif = 0;
    sm[o << 1] += getsum2(nst, ndif, mid - l + 1); // 给左儿子加上
    sm[o << 1 | 1ll] += getsum2(nst + (mid - l + 1) * ndif, ndif, r - mid); // 给右儿子加上
    tag[o << 1].st += nst, tag[o << 1].dif += ndif; // 更新左儿子的懒标记
    tag[o << 1 | 1ll].st += nst + (mid - l + 1) * ndif, tag[o << 1 | 1ll].dif += ndif; // 更新右儿子的等差数列
}
void add(int o, int l, int r, int L, int R, int k, int d) {
    if (L <= l && r <= R) {
        int tmp = k + d * (l - L);           // 这里是首项
        tag[o].st += tmp;                    // 打懒标记
        tag[o].dif += d;
        sm[o] += getsum(l, r, L, R, k, d);   // 更新当前区间和
        return;
    }
    pushdown(o, l, r);                       // 进行一个下传
    int mid = l + r >> 1;
    if (L <= mid) 
        add(o << 1, l, mid, L, R, k, d);
    if (R > mid) 
        add(o << 1 | 1ll, mid + 1, r, L, R, k, d);
}
int query(int o, int l, int r, int x) {      // 线段树标准query
    if (l == r) 
        return sm[o];
    pushdown(o, l, r);
    int mid = l + r >> 1;
    if (x <= mid) 
        return query(o << 1, l, mid, x);
    else 
        return query(o << 1 | 1ll, mid + 1, r, x);
}
signed main() { // 以下都是板子
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%lld", arr + i);
    Build(1, 1, N);
    for (int i = 0, c, l, r, k, d; i < m; i++) {
        scanf("%lld", &c);
        if (c == 1) {
            scanf("%lld%lld%lld%lld", &l, &r, &k, &d);
            add(1, 1, N, l, r, k, d);
        } else {
            scanf("%lld", &l);
            printf("%lld\n", query(1, 1, N, l));
        }
    }
    return 0;
 }

完结撒花~~~

标签:洛谷,数列,标记,int,线段,公差,首项,等差数列,P1438
From: https://www.cnblogs.com/forgotmyhandle/p/18000234

相关文章

  • 洛谷 P4429 [BJOI2018] 染色
    洛谷传送门LOJ传送门非常有趣的结论题。首先显然,整个图不是二分图就无解。然后显然每个连通块独立,可以分连通块判定。然后发现一度点是没什么用的,因为无论和它相连的点颜色是什么,它都能找到一种和这种颜色不同的颜色。所以考虑类似拓扑排序剥一度点。剩下的图的\(deg_u\ge......
  • 洛谷题单指南-暴力枚举-P1088 [NOIP2004 普及组] 火星人
    原题链接:https://www.luogu.com.cn/problem/P1088题意解读:火星人的手指可以通过全排列来表示数字,全排列由小到大的顺序即为表示的数字大小,题目可以转化为:给定按顺序全排列中的某一个排列,求往后数m个排列的内容。解题思路:此题与经典全排列问题的差异在于,需要从指定一个排列开......
  • 洛谷题单指南-暴力枚举-P1706 全排列问题
    原题链接:https://www.luogu.com.cn/problem/P1706题意解读:n个数全排列问题,本质上,给定n个空位,枚举每个能填入空位的数,依次填入,每个数只能填一次。解题思路:如何填入n个数呢,可以借助于递归,流程如下:dfs(填入第k个数){如果已经填满n个数输出结果返回......
  • 洛谷题单指南-暴力枚举-P1157 组合的输出
    原题链接:https://www.luogu.com.cn/problem/P1157题意解读:在1~n的数中挑选r个,有多少种组合,与P1036类似,有两种做法:二进制法、DFS,下面给出DFS版的代码。100分代码:#include<bits/stdc++.h>usingnamespacestd;constintN=25;intn,r;intt[N];voiddfs(intk){......
  • 洛谷题单指南-暴力枚举-P1036 [NOIP2002 普及组] 选数
    原题链接:https://www.luogu.com.cn/problem/P1036题意解读:题目即要在n个数中,枚举出所有的子集,当子集中数字个数刚好为k时,求和,判断是否是素数。解题思路:方法一:二进制法通过二进制法,可以枚举一个集合中所有元素“选”或者“不选”的情况,用二进制1表示选该元素,二进制0表示不选。......
  • 洛谷题单指南-暴力枚举-P1618 三连击(升级版)
    原题链接:https://www.luogu.com.cn/problem/P1618题意解读:枚举所有三位数的组合情况,判断是否符合比例。解题思路:方法一:枚举第一个数根据题意,目的是寻找三个符合比例的三位数,可以直接枚举第一个,最小是123,最大是987设第一个数为x,三个数的比例关系是a:b:c设另外两个数为y,z那么,根......
  • 洛谷题单指南-暴力枚举-P2241 统计方形(数据加强版)
    原题链接:https://www.luogu.com.cn/problem/P2241题意解读:要在整个n*m区域计算正方形和长方形的个数,枚举法即可。解题思路:此题枚举的对象是矩形的高i和宽j,高的范围[1,n],宽的范围[1,m],然后计算在n*m区域内有多少个i*j,i==j即属于正方形,i!=j属于长方形。那么,问题就集中在了......
  • 洛谷题单指南-排序-P1012 [NOIP1998 提高组] 拼数
    原题链接:https://www.luogu.com.cn/problem/P1012题意解读:通过某种合理的排序方式,使得排序后的数字连在一起最大。解题思路:此题关键在于排序,对于两个数字,哪个数字应该排在前面呢?1、思考误区很容易想到,给定两个数abcd、xyz,先比较第一位a和x,谁大谁排前面,一直到c和z。再来看d,这......
  • 洛谷题单指南-排序-P1104 生日
    原题链接:https://www.luogu.com.cn/problem/P1104题意解读:将学生按照年龄由大到小排序,如果年龄相同,后输入的排在前面,输出排序后的学生姓名。解题思路:此题是一个排序常规题,年龄大排在前说明年、月、日越小越在前面,核心的排序思路如下:1、如果年份不同,按年份由小到大排序2、如果......
  • 洛谷题单指南-排序-P5143 攀爬者
    原题链接:https://www.luogu.com.cn/problem/P5143题意解读:给出一系列的点,按某种顺序经过所有点,计算距离。解题思路:如果小学生,可能对于三维坐标距离有些陌生,没关系,题目已经给出了计算公式,直接套公式即可,关键步骤如下:1、读取所有坐标点2、按高度值从小到大排序3、从头依次计算......