UVA12436 Rip Van Winkle's Code

发表于2020-09-02更新于2023-09-15字数统计1.1k阅读时长11分

Rip Van Winkle’s Code

Description

有一个序列初始值全为零，现有一下四种操作：

  • A l r 将区间 [l,r][l, r] 加上等差数列 1,2,...,r−l+11, 2, ..., r - l + 1
  • B l r 将区间 [l,r][l, r] 加上等差数列 r−l+1,r−l,...,1r - l + 1, r - l, ..., 1
  • C l r x 将区间 [l,r][l, r] 赋值 xx
  • S l r 求区间 [l,r][l, r] 的和

Solution

难点在于区间加等差数列。
用 LvalLval 表示表示该区间增加的等差数列的首项标记，tag2tag2 表示表示该区间增加的等差数列的公差标记。因为一个加上等差数列的区间依旧是一个等差数列区间，于是两个标记可以累加。左右儿子增加的 sumsum 由父亲节点的 LvalLval 和 tag2tag2 推出。
注意：LvalLval 和 tag2tag2 都为 0 时标记不用下放；当有区间赋值标记时，等差数列标记无效，赋为 0。

Code

Rip Van Winkle's Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
#define int long long

using namespace std;

constexpr int MAXN = 3e5 + 5;

template <typename T>
inline void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct SegTree {
    SegTree *lson, *rson;
    int l, r;
    int sum, Lval; // sum为区间和，Lval为增加的等差数列首项标记
    int tag1 = 1e18, tag2;  // tag1为区间赋值标记，tag2为公差标记
} * root, tree[MAXN << 1];

inline SegTree* newNode(SegTree*& root) {
    static int tot;
    return root = &tree[tot++];
}

inline void update(SegTree* root) {
    root->sum = root->lson->sum + root->rson->sum;
}

inline int size(SegTree* root) { return root->r - root->l + 1; }
/*等差数列求和 @param Lval 首项 @param d 公差 @param len 项数*/
inline int sum(int Lval, int d, int len) {
    return Lval * len + d * len * (len - 1) / 2;
}

inline void build(SegTree* root, int l, int r) {
    root->l = l, root->r = r;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(newNode(root->lson), l, mid);
    build(newNode(root->rson), mid + 1, r);
}

inline void pushTag(SegTree* root) {
    if (root->tag1 != 1e18) {  //区间修改
        root->lson->tag1 = root->tag1, root->rson->tag1 = root->tag1;
        //区间修改后首项 公差为 0
        root->lson->Lval = root->rson->Lval = 0;
        root->lson->tag2 = root->rson->tag2 = 0;

        root->lson->sum = root->tag1 * size(root->lson);
        root->rson->sum = root->tag1 * size(root->rson);
        root->tag1 = 1e18;
    }
    if (root->tag2 || root->Lval) {  //区间等差数列
        root->lson->tag2 += root->tag2, root->rson->tag2 += root->tag2;

        root->lson->Lval += root->Lval;
        root->rson->Lval += root->Lval + root->tag2 * size(root->lson);
        //注意是从父亲root->Lval累加下来 新增的等差数列求和
        root->lson->sum += sum(root->Lval, root->tag2, size(root->lson));
        root->rson->sum += sum(root->Lval + root->tag2 * size(root->lson),
                               root->tag2, size(root->rson));
        root->tag2 = root->Lval = 0;  //两个都要清零
    }
}

inline void modify(SegTree* root, int l, int r, int val, int type) {
    if (l <= root->l && root->r <= r) {
        if (type == 1) {  //区间赋值
            root->sum = val * size(root);
            root->tag1 = val;
            root->Lval = root->tag2 = 0;  //!
        } else if (type == 2) {           //区间增加等差数列 公差 1
            root->Lval += root->l - l + val;
            root->tag2++;
            root->sum += sum(root->l - l + val, 1, size(root));
        } else {  //区间增加等差数列 公差 -1
            root->Lval += l - root->l + val;
            root->tag2--;
            root->sum += sum(l - root->l + val, -1, size(root));
        }
        return;
    }
    pushTag(root);
    int mid = (root->l + root->r) >> 1;
    if (l <= mid) modify(root->lson, l, r, val, type);
    if (r > mid) modify(root->rson, l, r, val, type);
    update(root);
}

inline int query(SegTree* root, int l, int r) {  //查询求和
    if (l <= root->l && root->r <= r) return root->sum;
    pushTag(root);
    int mid = (root->l + root->r) >> 1, res = 0;
    if (l <= mid) res += query(root->lson, l, r);
    if (r > mid) res += query(root->rson, l, r);
    return res;
}

signed main() {
    int n;
    read(n);
    build(newNode(root), 1, 250000);
    char opt[2];
    for (int i = 1, l, r, x; i <= n; i++) {
        scanf("%s", opt), read(l), read(r);
        if (opt[0] == 'A') modify(root, l, r, 1, 2);
        else if (opt[0] == 'B') modify(root, l, r, r - l + 1, 3);
        else if (opt[0] == 'C') read(x), modify(root, l, r, x, 1);
        else printf("%lld\n", query(root, l, r));
    }
    return 0;
}