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

vector<int> v(1);
int push(int val) { return v.push_back(val), v.back(); }
v[0] = push(1);

## 正文

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 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)
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;
};
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)
else
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)
if (v[v[rt].rc].v.l <= l)
}
};
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)
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;
};
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);
}
else
{
if (v[rt].rc == NPOS)
v[rt].rc = v.size(), build(m + 1, v[rt].v.r);
}
}
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)
if (m < l)
}
};
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)