题解：AT_arc210_a [ARC210A] Always Increasing

· · 题解

::::info[说在前面] 这道题目其实非常的简单，质量还行，动点脑子就行了。但是我好像是讲得最详细的一个，就是给像我一样菜的人一点有用的帮助。有些语句可能虽然我竭尽全力用最形象的语言来讲但还是难以理解，可以多读一读想一想，最后恳请您阅读到底。 ::::

题意是给定 Q 次运算，每次将数组的某一项加上某一个数，你需要做的是确定和最小的初始数列，使得每次运算都能保证数列严格从小到大排序并且第一项大于 0 。

我们考虑寻找其中的规律。

首先，我们尝试能否还原最终所有操作后的数列？（这一步比较难想，需要仔细读题并想一会儿才能想到，详细看下面）

不难发现，如果当前数组满足上文的升序条件。每一次增加某一项的时候，前面的不会受到任何影响，因为增加的数是正数。而这个数后面的数中如果出现了小于等于这个数的情况的话，那么说明升序被破坏了，只需要将后面的所有数跟随着增加同样的某个值使得依然升序即可。这一点只要想到了，基本就完成思路了，就是这一点可能会兜几圈才到，但应该是可以想到的。

我们来讨论具体实现细节。由于在一次都没有运算前，根据上文所说的性质，我们要保证数组满足那个升序条件。那必然数组先设为 1,2,3 \dots, N ，然后每次增加某个数的值，前面的数不会有影响。如果加上以后大于等于下一项的值（也就是升序被破坏），后面的需要集体抬升，怎么办？我们发现，最优且唯一的方案是把后面所有数加上直到比这个数大为止。那么设现在被增加的那一项值增加后为 a_i ，那么我们要做的就是把 a_{i+1}, a_{i+2}, \dots, a_n 全部加上 a_i - a_{i + 1} + 1 ，这应该是比较好理解的，就相当于集体实现抬升。

那么直接一个一个加太慢了，我们便想到用树状数组来维护，树状数组都会吧？不会去 某个地方 学习。我们增加的时候运用树状数组，只增加 a_{i + 1} 的值，然后求和的时候取前缀和也可以获得这一项被增加的值（这是树状数组单点查询区间修改的特性），也因为这题增加这个数后面的值的特性导致只要这个数前面有过多少记录就会加多少次。或者区间修改单点查询也是可以的，正是树状数组适合维护的。由于每一项的值都在时刻变化，所以我们在获取每一项的值时都需要加上树状数组里存储的变化量。当然你也可以不像我代码用一个函数来表示这个点现在的状态值这样更清晰一些。

最后，我们获得了对应的最终数组，然后我们用这个数组的和减去所有增加值之和不久还原初始最小序列的和了吗？这是一种逆推的思路，极其巧妙。

::::success[AC 代码]

# include <bits/stdc++.h>
# define int long long
# define MAXN 200005
using namespace std;
inline int read (){
    int 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 - 48; ch = getchar();}
    return x * f;
}
int n, q, ans, sumz, I[MAXN], x[MAXN], sz[MAXN], tree[MAXN];
int lowbit (int x){
    return x & -x;
}
void add (int k, int x){
    while (k <= n){
        tree[k] += x;
        k += lowbit(k);
    }
}
int sum (int k){
    int s = 0;
    while (k >= 1){
        s += tree[k];
        k -= lowbit(k);
    }
    return s;
}
signed main (){
    n = read(), q = read();
    for (int i = 1; i <= n; i++){
        sz[i] = i;
    }
    for (int i = 1; i <= q; i++){
        I[i] = read(), x[i] = read();
        sz[I[i]] += x[i];
        sumz += x[i];
        if (sz[I[i]] + sum(I[i]) >= sz[I[i] + 1] + sum(I[i] + 1)){
            add(I[i] + 1, sz[I[i]] + sum(I[i]) - (sz[I[i] + 1] + sum(I[i] + 1)) + 1);
        }
    }
    for (int i = 1; i <= n; i++){
        sz[i] += sum(i);
        ans += sz[i];
    }
    cout << ans - sumz;
    return 0;
}

::::

代码仅供参考，抄袭必有后报。