Codeforces 1136E（转化+线段树维护）

虽然线段树比较显然但是发现a数组并不好维护。考虑将a转化为好维护的数组b。

方法

这里我将k[1]设为0，对应着$$a[1] + k[1] <= a[2]$$不难得出$$a[i] + k[i] <= a[i+1]$$

\[a[i]+k[i]+k[i+1] <=a[i+2]
\]

所以设$$a[i] = b[i] + t[i]，其中t[i]为k[i]的前缀和$$

以样例来说话：

pos	1	2	3
a	1	2	3
k	0	1	-1
t	0	1	0
b	1	1	3

可以发现b数组是一个不下降的序列，原因是b是以a[1]为基石的，无论t数组是正是负，只会影响a数组的升降。这样我们就可以选择用线段树维护b，对于'+'操作，相当于修改线段树上的b数组：

1.在b[i]的位置加上x：

ll k = T.Query(i, i, 1) + x;

2.找到小于“修改后的b[i]”的第一个位置，因为只要保持b不下降就可以了，大于等于这个b[i]的位置不修改：

int pos = T.Position(i, n, 1, k);

3.区间修改：

T.Modify(i, pos, 1, k);

对于询问操作，就不难得出：$$\sum_{i = l}^ra[i] = \sum_{i = l}^r b[i]+t[i]$$

所以求t[i]时顺手求个t[i]的前缀和，这道题就完成了。

最后注意线段树的tag，要设成-inf，这题的数组值是正负皆可的，不能用是否为0来判断tag：

void Push_down(int p) {

        if (t[p].tag > -INF) {

最终代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 5;

const ll INF = 1e18;

int n, q;

ll a[maxn], k[maxn], t[maxn], sum[maxn], b[maxn];

class SegmentTree {

public:

    #define ls(p)   p << 1

    #define rs(p)   p << 1 | 1

    struct Node {

        int l, r;

        ll minn, sum, tag = -INF;

    }t[maxn << 2];

    void Push_up(int p) {

        t[p].minn = min(t[ls(p)].minn, t[rs(p)].minn);

        t[p].sum = t[ls(p)].sum + t[rs(p)].sum;

    }

    void Push_down(int p) {

        if (t[p].tag > -INF) {

            t[ls(p)].minn = t[rs(p)].minn = t[ls(p)].tag = t[rs(p)].tag = t[p].tag;

            t[ls(p)].sum = t[p].tag * (t[ls(p)].r - t[ls(p)].l + 1);

            t[rs(p)].sum = t[p].tag * (t[rs(p)].r - t[rs(p)].l + 1);

            t[p].tag = -INF;

        }

    }

    void Build(int l, int r, int p) {

        t[p].l = l, t[p].r = r;

        if (l == r) {

            t[p].minn = t[p].sum = b[l];

            return;

        }

        int mid = (l + r) >> 1;

        Build(l, mid, ls(p));

        Build(mid + 1, r, rs(p));

        Push_up(p);

    }

    void Modify(int l, int r, int p, ll k) {

        if (l <= t[p].l && t[p].r <= r) {

            t[p].minn = t[p].tag = k;

            t[p].sum = k * (t[p].r - t[p].l + 1);

            return;

        }

        int mid = (t[p].l + t[p].r) >> 1;

        Push_down(p);

        if (l <= mid)   Modify(l, r, ls(p), k);

        if (mid < r)    Modify(l, r, rs(p), k);

        Push_up(p);

    }

    int Position(int l, int r, int p, ll k) {

        if (t[p].minn < k && t[p].l == t[p].r)  return t[p].l;

        int mid = (t[p].l + t[p].r) >> 1;

        Push_down(p);

        if (t[rs(p)].minn < k)  return Position(l, r, rs(p), k);

        else    return  Position(l, r, ls(p), k);

    }

    ll Query(int l, int r, int p) {

        if (l <= t[p].l && t[p].r <= r) return t[p].sum;

        int mid = (t[p].l + t[p].r) >> 1;

        Push_down(p);

        if (l > mid)    return Query(l, r, rs(p));

        if (r <= mid)   return Query(l, r, ls(p));

        return Query(l, r, ls(p)) + Query(l, r, rs(p));

    }

}T;

int main(int argc, char const *argv[]) {

    ios_base::sync_with_stdio(0);

    cin.tie(0), cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)

        cin >> a[i];

    for (int i = 2; i <= n; i++)

        cin >> k[i], t[i] = t[i - 1] + k[i], sum[i] = sum[i - 1] + t[i];

    for (int i = 1; i <= n; i++)

        b[i] = a[i] - t[i];

    T.Build(1, n, 1);

    for (cin >> q; q; q--) {

        string op;

        cin >> op;

        if (op == "+") {

            int i, x;

            cin >> i >> x;

            ll k = T.Query(i, i, 1) + x;

            int pos = T.Position(i, n, 1, k);

            T.Modify(i, pos, 1, k);

        } else {

            int l, r;

            cin >> l >> r;

            cout << T.Query(l, r, 1) + sum[r] - sum[l - 1] << endl;

        }

    }

    return 0;

}

巴特西

Codeforces 1136E（转化+线段树维护）

方法

最新文章

热门文章