Blackops

初心易得，始终难守

0%

HDU 4348 To the moon（主席树+区间操作）

发表于 更新于 分类于 ， ，

To the moon

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 6373 Accepted Submission(s): 1481

Problem Description
Background
To The Moon is a independent game released in November 2011, it is a role-playing adventure game powered by RPG Maker.
The premise of To The Moon is based around a technology that allows us to permanently reconstruct the memory on dying man. In this problem, we’ll give you a chance, to implement the logic behind the scene.

You‘ve been given N integers A[1], A[2],…, A[N]. On these integers, you need to implement the following operations:

  1. C l r d: Adding a constant d for every {Ai | l <= i <= r}, and increase the time stamp by 1, this is the only operation that will cause the time stamp increase.
  2. Q l r: Querying the current sum of {Ai | l <= i <= r}.
  3. H l r t: Querying a history sum of {Ai | l <= i <= r} in time t.
  4. B t: Back to time t. And once you decide return to a past, you can never be access to a forward edition anymore.
    .. N, M ≤ 105, |A[i]| ≤ 109, 1 ≤ l ≤ r ≤ N, |d| ≤ 104 .. the system start from time 0, and the first modification is in time 1, t ≥ 0, and won’t introduce you to a future state.

Input
n m
A1 A2 … An
… (here following the m operations. )

Output
… (for each query, simply print the result. )

Sample Input
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

2 4
0 0
C 1 1 1
C 2 2 -1
Q 1 2
H 1 2 1

Sample Output
4
55
9
15

0
1

题目链接：HDU 4348
函数式线段树，照着网上的代码，自己改了一份可以对两个历史版本$history_L ～ history_R$之间的区间操作的代码，不知道有没有BUG，其实最普通的主席树就是动态开点的线段树，但是它的版本是一直依靠第$0$个版本，那么我们可以改成让它依靠前一个版本，这样就可以进行区间差分操作，然后由于build本身占用$O(NlogN)$的空间，修改也是$O(NlogN)$的空间，那么实际上数组要开$2*NlogN$大小，大约开$40$倍应该够了。由于对$(l,r)$区间操作，实际上用的差分是$L-1$与$R$，因此要让一开始的版本成为$root[1]$，然后后面的版本从$2$开始更新，历史版本也要往后推一个位置
代码：

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
117
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
struct seg
{
    int ls, rs;
    LL v, add;
} T[N * 34];
int root[N], arr[N], sz;

void build(int &x, int l, int r)
{
    x = ++sz;
    T[x].ls = T[x].rs = 0;
    T[x].add = 0;
    if (l == r)
        T[x].v = arr[l];
    else
    {
        int mid = MID(l, r);
        build(T[x].ls, l, mid);
        build(T[x].rs, mid + 1, r);
        T[x].v = T[T[x].ls].v + T[T[x].rs].v;
    }
}
void update(int &x, int y, int l, int r, int ql, int qr, int v)
{
    x = ++sz;
    T[x] = T[y];
    T[x].v += (LL)(qr - ql + 1) * (LL)v;
    if (ql <= l && r <= qr)
        T[x].add += v;
    else
    {
        int mid = MID(l, r);
        if (qr <= mid)
            update(T[x].ls, T[y].ls, l, mid, ql, qr, v);
        else if (ql > mid)
            update(T[x].rs, T[y].rs, mid + 1, r, ql, qr, v);
        else
            update(T[x].ls, T[y].ls, l, mid, ql, mid, v), update(T[x].rs, T[y].rs, mid + 1, r, mid + 1, qr, v);
    }
}
LL query(int x, int y, int l, int r, int ql, int qr)
{
    if (ql <= l && r <= qr)
        return T[x].v - T[y].v;
    LL add = (LL)(qr - ql + 1) * (T[x].add - T[y].add);
    int mid = MID(l, r);
    if (qr <= mid)
        return query(T[x].ls, T[y].ls, l, mid, ql, qr) + add;
    else if (ql > mid)
        return query(T[x].rs, T[y].rs, mid + 1, r, ql, qr) + add;
    else
        return query(T[x].ls, T[y].ls, l, mid, ql, mid) + query(T[x].rs, T[y].rs, mid + 1, r, mid + 1, qr) + add;
}
int main(void)
{
    int n, m, i;
    char ops[N];
    while (~scanf("%d%d", &n, &m))
    {
        sz = 0;
        for (i = 1; i <= n; ++i)
            scanf("%d", &arr[i]);
        build(root[1], 1, n);
        int idx = 1;
        for (i = 0; i < m; ++i)
        {
            scanf("%s", ops);
            if (ops[0] == 'C')
            {
                int l, r, d;
                scanf("%d%d%d", &l, &r, &d);
                ++idx;
                update(root[idx], root[idx - 1], 1, n, l, r, d);
            }
            else if (ops[0] == 'Q')
            {
                int l, r;
                scanf("%d%d", &l, &r);
                printf("%I64d\n", query(root[idx], root[0], 1, n, l, r));
            }
            else if (ops[0] == 'H')
            {
                int l, r, h;
                scanf("%d%d%d", &l, &r, &h);
                printf("%I64d\n", query(root[h + 1], root[0], 1, n, l, r));
            }
            else
                scanf("%d", &idx), ++idx;
        }
    }
    return 0;
}