Blackops

初心易得，始终难守

0%

POJ 3468 A Simple Problem with Integers（splay区间操作）

发表于 分类于 ， ，

A Simple Problem with Integers
Time Limit: 5000MS Memory Limit: 131072K
Total Submissions: 121627 Accepted: 37761
Case Time Limit: 2000MS
Description

You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, … , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
“C a b c” means adding c to each of Aa, Aa+1, … , Ab. -10000 ≤ c ≤ 10000.
“Q a b” means querying the sum of Aa, Aa+1, … , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

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

4
55
9
15
Hint

The sums may exceed the range of 32-bit integers.

题目链接：POJ 3468
$splay$居然还能用来更新区间，某位想到强行$splay$做这种题的大佬太厉害了%%%。
一开始我们先预先建立两个点，根节点和根节点的右儿子作为数列的第$0$个数和第$n+1$个数（后面会用到），然后用下标作为关键字，做一遍线段树动态开点建树，该$pushup$的$pushup$，然后就是重点，由于我们有$splay$操作，就把第$l-1$个点$splay$到根节点处，把第$r+1$个点$splay$到根节点的右儿子处，然后根据定义，以根节点的右儿子的左节点为根的子树内的点就是我们要的处理的所有区间节点，将其更新或者询问一下就好
代码：

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#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 = 100010;
struct node
{
    int ch[2], f, w;
    LL v, s, ad;
    void init()
    {
        ch[0] = ch[1] = f = w = 0;
        v = s = ad = 0;
    }
} T[N];
int rt, sz;
int arr[N];

inline void newnode(int &k, int f, LL v)
{
    T[k = ++sz].init();
    T[k].v = v;
    T[k].f = f;
}
inline void update(int k, LL ad)
{
    if (!k)
        return ;
    T[k].ad += ad;
    T[k].s += (LL)T[k].w * ad;
    T[k].v += ad;
}
inline void pushup(int k)
{
    T[k].w = T[T[k].ch[0]].w + T[T[k].ch[1]].w + 1;
    T[k].s = T[T[k].ch[0]].s + T[T[k].ch[1]].s + T[k].v;
}
inline void pushdown(int k)
{
    if (T[k].ad)
    {
        update(T[k].ch[0], T[k].ad);
        update(T[k].ch[1], T[k].ad);
        T[k].ad = 0;
    }
}
void build(int &k, int l, int r, int f)
{
    int mid = MID(l, r);
    newnode(k, f, arr[mid]);
    if (l < mid)
        build(T[k].ch[0], l, mid - 1, k);
    if (mid < r)
        build(T[k].ch[1], mid + 1, r, k);
    pushup(k);
}
inline int getson(int k)
{
    return T[T[k].f].ch[1] == k;
}
inline void rotate(int x, int &k)
{
    int f = T[x].f, ff = T[f].f, l = getson(x), r = l ^ 1;
    pushdown(f);
    pushdown(x);
    if (f == k)
        k = x;
    else
        T[ff].ch[getson(f)] = x;
    T[x].f = ff;
    T[f].ch[l] = T[x].ch[r];
    if (T[x].ch[r])
        T[T[x].ch[r]].f = f;
    T[x].ch[r] = f;
    T[f].f = x;
    pushup(f);
}
void splay(int x, int &k)
{
    pushdown(x);
    while (x != k)
    {
        int f = T[x].f;
        if (f != k)
        {
            if (getson(f)^getson(x))
                rotate(x, k);
            else
                rotate(f, k);
        }
        rotate(x, k);
    }
    pushup(x);
}
int get_kth(int x, int k)
{
    pushdown(x);
    int w = T[T[x].ch[0]].w + 1;
    if (k == w)
        return x;
    else if (k < w)
        return get_kth(T[x].ch[0], k);
    else
        return get_kth(T[x].ch[1], k - w);
}
void init(int l, int r)
{
    rt = sz = 0;
    T[0].init();
    newnode(rt, 0, -1);
    newnode(T[rt].ch[1], rt, -1);
    build(T[T[rt].ch[1]].ch[0], l, r, T[rt].ch[1]);
    pushup(T[rt].ch[1]);
    pushup(rt);
}
void add(int l, int r, LL v)
{
    splay(get_kth(rt, l), rt);
    splay(get_kth(rt, r + 2), T[rt].ch[1]);
    update(T[T[rt].ch[1]].ch[0], v);
    pushup(T[rt].ch[1]);
    pushup(rt);
}
LL query(int l, int r)
{
    splay(get_kth(rt, l), rt);
    splay(get_kth(rt, r + 2), T[rt].ch[1]);
    return T[T[T[rt].ch[1]].ch[0]].s;
}
int main(void)
{
    int n, m, l, r, i;
    LL v;
    while (~scanf("%d%d", &n, &m))
    {
        for (i = 1; i <= n; ++i)
            scanf("%d", arr + i);
        init(1, n);
        while (m--)
        {
            char ops[4];
            scanf("%s%d%d", ops, &l, &r);
            if (ops[0] == 'Q')
                printf("%lld\n", query(l, r));
            else
            {
                scanf("%lld", &v);
                add(l, r, v);
            }
        }
    }
    return 0;
}