【题型总结】给区间加等差数列求值问题

一、前言:

上一篇题型总结不知道扔哪去了,下午训练看到个很眼熟的题,感觉见过很多次了,就顺手总结下。

需要会的前置知识有:差分与前缀和,树状数组基础,线段树基础

二、UPC 2020年夏混合个人训练第八十场 问题 B: 序列 (二阶差分)

题意:

给定长度为n的数组和m次操作,每次操作都表示将区间[l,r]加上一个首项为s,末项为e的等差数列,求操作后序列每一项的异或和。

思路:
在这里插入图片描述

序列[l]+=首项;
序列[l+1]+=公差-首项;
序列[r+1]-=首项+(r-l+1)公差;//注意r+1处要减,其余的均为加。
序列[r+2]+=首项+(r-l)
公差;

代码:

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define I_int ll
typedef pair<int,int> PII;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}

const int maxn=500000+100;

ll a[maxn],n,m;

int main(){
    n=read(),m=read();
    while(m--){
        ll l=read(),r=read(),s=read(),e=read();
        ll q=(e-s)/(r-l);
        a[l]+=s;a[l+1]+=q-s;
        a[r+1]-=s+(r-l+1)*q;a[r+2]+=s+(r-l)*q;
    }
    for(int i=1;i<=n;i++) a[i]+=a[i-1];
    ll res=0;
    for(int i=1;i<=n;i++){
        a[i]+=a[i-1];
        res^=a[i];
    }
    out(res);
    return 0;
}

参考博客:

1

博客的题就是以前训练的题,只是变了变题目背景。

2

3

三、洛谷P1438 无聊的数列 (差分+线段树/树状数组/分块)

原题链接

题意:

维护一个数组和两种操作,操作一就是将区间加上一个等差数列,操作二是查询某点的值。

思路:

考虑一下本题跟上一题的区别,上一题的询问是执行完所有区间加法后进行的,本题是强制在线。这时候如果再采用上题的二阶差分显然不可取。

最特殊的情况就是等差数列的公差为0,这样题目就变成了单纯的区间修改 单点查询,线段树树状数组分块都可以写。

那么对于一般情况可以借鉴一下上题的思路,开设一个差分数组,对于区间[l,r]进行修改的话,就是对于第l个点加首项s,对于第l+1到r的点加上公差d,对于第r+1个点减去之前加上的所有差分值,即减去s+(r-l)*d;

简单说下原理,根据差分的性质,我们执行完以上操作后,对原数组的贡献是第l个数加了s,第l+1个数加了s+d……第r+1个数不变。这就恰好符合我们的要求。

这样对于操作一,我们就转化成了单点修改和区间修改。

对于操作二,我们只需要在原数组的基础上加上差分数组的前缀和即可,本质就是一个区间求和。

然后用线段树什么的维护一下差分数组就可以了。

其他思路和代码: 洛谷题解

看到了个很短的分块代码,还是分块无敌啊。

四、牛客小白月赛20 E 区区区间(等差数列求和公式+线段树)

原题链接

题意:

给定一个长度为n的数组和m次操作,操作一是将区间替换程以k为首项,1为公差的等差数列,操作二是查询区间的和。

思路:

操作一可以看成是区间修改,操作二可以看成是区间求和,因为一段区间被修改后一定是等差数列,所以知道首项的值就可以根据等差数列的求和公式推出区间的和,所以记录一下修改后左端点的值,然后线段树维护一下左端点的值和区间的和即可。

代码:
但学长说我写法常数有点大emm,还是参考下其他巨巨的写法吧。

五、感谢阅读。

希望各位期末不挂!