AcWing算法提高课-4.2.3一个简单的整数问题2

宣传一下算法提高课整理 <—

CSDN个人主页：更好的阅读体验 <—

本题链接（AcWing）点这里

题目描述

给定一个长度为 $N$ 的数列 $A$ ，以及 $M$ 条指令，每条指令可能是以下两种之一：

C l r d，表示把 $A [l], A [l + 1], \dots, A [r]$ 都加上 $d$ 。
Q l r，表示询问数列中第 $\sim r$ 个数的和。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数 $N, M$ 。

第二行 $N$ 个整数 $A [i]$ 。

接下来 $M$ 行表示 $M$ 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

$\le N,M \le 10^5$ ,
$\le 10000$ ,
$\le 10^9$

输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出样例：

思路

考虑用树状数组 tr[] 维护差分数组

则求原数组的前缀和

$\left\{\begin{matrix} a_1& =& d_1& & & & & & & \\ a_2& =& d_1& +& d_2& & & & & \\ a_3& =& d_1& +& d_2& +& d_3& & & \\ .& .& .& .& .& .& & & & \\ a_n& =& d_1& +& d_2& +& ...& +& d_n& \\ \end{matrix}\right.$

$s_i=\sum_{i=1}^{n}a_i=\left\{\begin{matrix} d_1& & & & & & & \\ d_1& +& d_2& & & & & \\ d_1& +& d_2& +& d_3& & & \\ .& .& .& .& .& .& & & & \\ d_1& +& d_2& +& ...& +& d_n& \\ \end{matrix}\right.$

我们考虑把后面的矩阵补全：

则

$s_i=(n+1) \times \sum_{i=1}^{n}d_i-\sum_{i=1}^{n}(i \times d_i)$

所以我们需要两个树状数组，tr1[] 维护差分数组，tr2[] 维护 $\times d_i$

代码：

#include <iostream>

using namespace std;

typedef long long LL;

const LL N = 1000010;

LL n, m;
LL a[N];
LL t1[N], t2[N];

inline LL lowbit(LL x)
{
    return x & -x;
}

inline void add(LL t[], LL x, LL c)
{
    for (LL i = x; i <= n; i += lowbit(i))
        t[i] += c;
}

inline LL sum(LL t[], LL x)
{
    LL res = 0;
    for (LL i = x; i; i -= lowbit(i))
        res += t[i];
    return res;
}

inline LL psum(LL x)
{
    return sum(t1, x) * (x + 1) - sum(t2, x);
}

int main()
{
    scanf("%lld%lld", &n, &m);
    for (LL i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
    for (LL i = 1; i <= n; i ++ )
    {
        LL b = a[i] - a[i - 1];
        add(t1, i, b);
        add(t2, i, b * i);
    }

    while (m -- )
    {
        char op[2];
        LL l, r, d;
        scanf("%s%lld%lld", op, &l, &r);
        if (op[0] == '2')
        {
            printf("%lld\n", psum(r) - psum(l - 1));
        }
        else
        {
            scanf("%lld", &d);
            add(t1, l, d), add(t2, l, l * d);
            add(t1, r + 1, -d), add(t2, r + 1, -d * (r + 1));
        }
    }

    return 0;
}

（后附极限卡常代码，70ms，较优解）

#define qwq optimize
#pragma GCC qwq(1)
#pragma GCC qwq(2)
#pragma GCC qwq(3)
#pragma GCC qwq("Ofast")
#pragma GCC qwq("inline")
#pragma GCC qwq("-fgcse")
#pragma GCC qwq("-fgcse-lm")
#pragma GCC qwq("-fipa-sra")
#pragma GCC qwq("-ftree-pre")
#pragma GCC qwq("-ftree-vrp")
#pragma GCC qwq("-fpeephole2")
#pragma GCC qwq("-ffast-math")
#pragma GCC qwq("-fsched-spec")
#pragma GCC qwq("unroll-loops")
#pragma GCC qwq("-falign-jumps")
#pragma GCC qwq("-falign-loops")
#pragma GCC qwq("-falign-labels")
#pragma GCC qwq("-fdevirtualize")
#pragma GCC qwq("-fcaller-saves")
#pragma GCC qwq("-fcrossjumping")
#pragma GCC qwq("-fthread-jumps")
#pragma GCC qwq("-funroll-loops")
#pragma GCC qwq("-fwhole-program")
#pragma GCC qwq("-freorder-blocks")
#pragma GCC qwq("-fschedule-insns")
#pragma GCC qwq("inline-functions")
#pragma GCC qwq("-ftree-tail-merge")
#pragma GCC qwq("-fschedule-insns2")
#pragma GCC qwq("-fstrict-aliasing")
#pragma GCC qwq("-fstrict-overflow")
#pragma GCC qwq("-falign-functions")
#pragma GCC qwq("-fcse-skip-blocks")
#pragma GCC qwq("-fcse-follow-jumps")
#pragma GCC qwq("-fsched-interblock")
#pragma GCC qwq("-fpartial-inlining")
#pragma GCC qwq("no-stack-protector")
#pragma GCC qwq("-freorder-functions")
#pragma GCC qwq("-findirect-inlining")
#pragma GCC qwq("-fhoist-adjacent-loads")
#pragma GCC qwq("-frerun-cse-after-loop")
#pragma GCC qwq("inline-small-functions")
#pragma GCC qwq("-finline-small-functions")
#pragma GCC qwq("-ftree-switch-conversion")
#pragma GCC qwq("-fqwq-sibling-calls")
#pragma GCC qwq("-fexpensive-optimizations")
#pragma GCC qwq("-funsafe-loop-optimizations")
#pragma GCC qwq("inline-functions-called-once")
#pragma GCC qwq("-fdelete-null-pointer-checks")
#include <iostream>
#include <cstdio>

#define lb(x) (x & (-x))

using namespace std;

typedef long long LL;

const LL N = 100010;

LL n, m;
LL a[N];
LL t1[N], t2[N];

char *p1, *p2, buf[N];
#define nc() (p1 == p2 && (p2 = (p1 = buf) +\
fread(buf, 1, N, stdin), p1 == p2) ? EOF : *p1 ++ )
LL read()
{
    LL x = 0, f = 1;
    char ch = nc();
    while (ch < 48 || ch > 57)
    {
        if (ch == '-') f = -1;
        ch = nc();
    }
    while (ch >= 48 && ch <= 57)
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = nc();
    return x * f;
}

char obuf[N], *p3 = obuf;
#define putchar(x) (p3 - obuf < N) ? (*p3 ++ = x) :\
(fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3 ++ = x)
inline void write(LL x)
{
    if (!x)
    {
        putchar('0');
        return;
    }
    LL len = 0, k1 = x, c[40];
    if (k1 < 0) k1 = -k1, putchar('-');
    while (k1) c[len ++ ] = k1 % 10 ^ 48, k1 /= 10;
    while (len -- ) putchar(c[len]);
}

inline void add(LL t[], LL x, LL c)
{
    for (LL i = x; i <= n; i += lb(i))
        t[i] += c;
}

inline LL sum(LL t[], LL x)
{
    LL res = 0;
    for (LL i = x; i; i -= lb(i))
        res += t[i];
    return res;
}

inline LL psum(LL x)
{
    return sum(t1, x) * (x + 1) - sum(t2, x);
}

int main()
{
    n = read(), m = read();
    for (LL i = 1; i <= n; i ++ ) a[i] = read();
    for (LL i = 1; i <= n; i ++ )
    {
        LL b = a[i] - a[i - 1];
        add(t1, i, b);
        add(t2, i, b * i);
    }

    LL op, l, r, d;
    while (m -- )
    {
        op = read(), l = read(), r = read();
        if (op == 2) write(psum(r) - psum(l - 1)), putchar(10);
        else
        {
            d = read();
            add(t1, l, d), add(t2, l, l * d);
            add(t1, r + 1, -d), add(t2, r + 1, -d * (r + 1));
        }
    }
	fwrite(obuf, p3 - obuf, 1, stdout);
    return 0;
}