CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
这个人居然也可以在这个沙雕问题 RE 一晚上
以下是问题简化。
1
2
3
vector<int> v(1);
int push(int val) { return v.push_back(val), v.back(); }
v[0] = push(1);
假如有上面这段代码，在push时改变了v.size()，就可能会导致容器在内存里移动，但是左边v[0]的引用先于push被构造，结果真正赋值的时候期望的地址可能已经发生移动，就导致了 RE。
道理我都懂，但是问题发生的地方也太隐密了…想想平时的代码习惯不禁冒出冷汗。以后还是要多多注意。
正文
在16 号那场集训曾经产生了把树状数组建在 map 上的想法…所以今天来实践一下。
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
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct Fenwick
{
map<int, ll> v;
void add(int x, ll val, int M = 1e9 + 7)
{
for (; x < M; x += x & -x)
v[x] += val;
}
ll ask(int x)
{
ll r = 0;
for (; x; x -= x & -x)
r += v[x];
return r;
}
};
map<int, Fenwick> mp;
int n, a, t, x;
int main()
{
for (scanf("%d", &n); n--;)
{
scanf("%d%d%d", &a, &t, &x);
if (a == 3)
printf("%d\n", mp[x].ask(t));
else
mp[x].add(t, a == 2 ? -1 : 1);
}
}
时空最优解当然是动态开点线段树啦，比上面的代码快了正好一倍（171ms:342ms），空间也小了一些（45344kB:52676kB）。
启示是，假如题目空间给的足够大的话，可以用建在 map 上的树状数组来偷懒代替线段树来维护区间和。（并没有什么卵用？）
以下是正常的动态下传线段树，只快一丢丢。
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
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int NPOS = -1;
struct SegmentTree
{
struct Val
{
int l, r;
ll sum;
void upd(ll add) { sum += add; }
};
struct Node
{
Val v;
int lc, rc;
};
vector<Node> v;
SegmentTree(int l = 0, int r = 1e9 + 7) { build(l, r); }
void build(int l, int r) { v.push_back({{l, r, 0}, NPOS, NPOS}); }
Val up(const Val &lc, const Val &rc) { return {lc.l, rc.r, lc.sum + rc.sum}; }
void down(int rt)
{
int m = v[rt].v.l + v[rt].v.r >> 1;
if (v[rt].lc == NPOS)
v[rt].lc = v.size(), build(v[rt].v.l, m);
if (v[rt].rc == NPOS)
v[rt].rc = v.size(), build(m + 1, v[rt].v.r);
}
void add(int pos, ll val, int rt = 0)
{
if (pos <= v[rt].v.l && v[rt].v.r <= pos)
return v[rt].v.upd(val);
down(rt);
if (v[v[rt].lc].v.r >= pos)
add(pos, val, v[rt].lc);
else
add(pos, val, v[rt].rc);
v[rt].v = up(v[v[rt].lc].v, v[v[rt].rc].v);
}
Val ask(int l, int r, int rt = 0)
{
if (l <= v[rt].v.l && v[rt].v.r <= r)
return v[rt].v;
down(rt);
if (v[v[rt].lc].v.r >= r)
return ask(l, r, v[rt].lc);
if (v[v[rt].rc].v.l <= l)
return ask(l, r, v[rt].rc);
return up(ask(l, v[v[rt].lc].v.r, v[rt].lc), ask(v[v[rt].rc].v.l, r, v[rt].rc));
}
};
map<int, SegmentTree> mp;
int n, a, t, x;
int main()
{
for (scanf("%d", &n); n--;)
{
scanf("%d%d%d", &a, &t, &x);
if (a == 3)
printf("%d\n", mp[x].ask(0, t).sum);
else
mp[x].add(t, a == 2 ? -1 : 1);
}
}
以下是特殊优化的线段树，快了一倍。
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
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int NPOS = -1;
struct SegmentTree
{
struct Val
{
int l, r;
ll sum;
void upd(ll add) { sum += add; }
};
struct Node
{
Val v;
int lc, rc;
};
vector<Node> v;
SegmentTree(int l = 0, int r = 1e9 + 7) { build(l, r); }
void build(int l, int r) { v.push_back({{l, r, 0}, NPOS, NPOS}); }
Val up(const Val &lc, const Val &rc) { return {lc.l, rc.r, lc.sum + rc.sum}; }
void add(int pos, ll val, int rt = 0)
{
v[rt].v.upd(val);
if (pos <= v[rt].v.l && v[rt].v.r <= pos)
return;
int m = v[rt].v.l + v[rt].v.r >> 1;
if (m >= pos)
{
if (v[rt].lc == NPOS)
v[rt].lc = v.size(), build(v[rt].v.l, m);
add(pos, val, v[rt].lc);
}
else
{
if (v[rt].rc == NPOS)
v[rt].rc = v.size(), build(m + 1, v[rt].v.r);
add(pos, val, v[rt].rc);
}
}
Val ask(int l, int r, int rt = 0)
{
if (rt == NPOS)
return {l, r, 0};
if (l <= v[rt].v.l && v[rt].v.r <= r)
return v[rt].v;
int m = v[rt].v.l + v[rt].v.r >> 1;
if (m >= r)
return ask(l, r, v[rt].lc);
if (m < l)
return ask(l, r, v[rt].rc);
return up(ask(l, m, v[rt].lc), ask(m + 1, r, v[rt].rc));
}
};
map<int, SegmentTree> mp;
int n, a, t, x;
int main()
{
for (scanf("%d", &n); n--;)
{
scanf("%d%d%d", &a, &t, &x);
if (a == 3)
printf("%d\n", mp[x].ask(0, t).sum);
else
mp[x].add(t, a == 2 ? -1 : 1);
}
}