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
| #include <set>
#include <cstdio>
#include <vector>
#include <algorithm>
using std::set;
using std::vector;
const int MAXN = 100001;
const int MEMORYSIZE = 1024*1024*4;
//------1D SegmentTree
struct Segment1D
{
long long sum;
Segment1D *lef, *rig;
} _memory[MEMORYSIZE], *_memory_top = _memory;
int n, _n;
class SegmentTree1D
{
#define CREATE_AND_GO(func, node, ...) { if (!node) node = _memory_top++; func(node, __VA_ARGS__); }
Segment1D *root;
long long query(Segment1D* const node, const int lef, const int rig, const int st, const int ed)
{
if (!node->sum) return 0;
if (st <= lef && rig <= ed) return node->sum;
const int mid = (lef+rig)/2;
long long sum = 0;
if (st <= mid && node->lef) sum += query(node->lef, lef, mid, st, ed);
if (mid+1 <= ed && node->rig) sum += query(node->rig, mid+1, rig, st, ed);
return sum;
}
void modify(Segment1D* const node, const int lef, const int rig, const int pos, const int delta)
{
node->sum += delta;
if (lef == rig) return;
const int mid = (lef+rig)/2;
if (pos <= mid) CREATE_AND_GO(modify, node->lef, lef, mid, pos, delta)
else CREATE_AND_GO(modify, node->rig, mid+1, rig, pos, delta)
}
#undef CREATE_AND_GO
public:
long long Query(const int lef, const int rig) { return query(root, 1, n, lef, rig); }
void Modify(const int pos, const int delta) { modify(root, 1, n, pos, delta); }
SegmentTree1D(): root(_memory_top++) { }
};
//------2D BIT
SegmentTree1D C[MAXN*2];
inline void Modify(const int x, const int y, const int delta)
{
for (int i = x+1; i <= _n; i += i&-i)
C[i].Modify(y, delta);
}
inline long long Query(const int x, const int y1, const int y2)
{
long long res = 0;
for (int i = x+1; i; i -= i&-i)
res += C[i].Query(y1, y2);
return res;
}
//------Main Program
int m, a[MAXN], x[MAXN], y[MAXN];
char o[MAXN];
set<int> sets[MAXN*2];
int main()
{
scanf("%d", &n);
vector<int> v;
for (int i = 1; i <= n; ++i)
{
scanf("%d", a+i);
v.push_back(a[i]);
}
scanf("%d", &m);
for (int i = 0; i < m; ++i)
{
scanf("\n%c%d%d", o+i, x+i, y+i);
if (o[i] == 'U') v.push_back(y[i]);
}
std::sort(v.begin(), v.end());
v.resize(std::unique(v.begin(), v.end())-v.begin());
_n = n+1;
for (size_t i = 0; i < v.size(); ++i) sets[i].insert(0);
for (int i = 1; i <= n; ++i)
{
const int cur = std::lower_bound(v.begin(), v.end(), a[i])-v.begin();
const int last = *sets[cur].rbegin();
Modify(last, i, +a[i]);
sets[cur].insert(i);
}
for (int i = 0; i < m; ++i)
{
if (o[i] == 'Q')
printf("%lld\n", Query(x[i]-1, x[i], y[i]));
else
{
const int pos = x[i], value = y[i];
const int pre = std::lower_bound(v.begin(), v.end(), a[pos])-v.begin();
set<int>::iterator target = sets[pre].find(pos), succ, prev;
Modify(*--(prev = target), pos, -a[pos]);
if (++(succ = target) != sets[pre].end())
{
Modify(pos, *succ, -a[pos]);
Modify(*prev, *succ, +a[pos]);
}
sets[pre].erase(target);
const int cur = std::lower_bound(v.begin(), v.end(), value)-v.begin();
sets[cur].insert(pos);
target = sets[cur].find(pos);
Modify(*--(prev = target), pos, +value);
if (++(succ = target) != sets[cur].end())
{
Modify(*prev, *succ, -value);
Modify(pos, *succ, +value);
}
a[pos] = value;
}
}
//printf("\n\n%10d\n%10d\n%.6fMBytes\n", _memory_top-_memory, MEMORYSIZE, (sizeof(_memory)+sizeof(x)+sizeof(y)+sizeof(o)+sizeof(C))/1024.0/1024.0);
}
|
