题目链接

这个人居然也可以在这个沙雕问题 RE 一晚上

以下是问题简化。

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 上的想法…所以今天来实践一下。

#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 上的树状数组来偷懒代替线段树来维护区间和。（并没有什么卵用？）

以下是正常的动态下传线段树，只快一丢丢。

#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);
	}
}

以下是特殊优化的线段树，快了一倍。

#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);
	}
}