Color it(线段树动态建树)

描述

传送门:HDU6183

Do you like painting? Little D doesn’t like painting, especially messy color paintings. Now Little B is painting. To prevent him from drawing messy painting, Little D asks you to write a program to maintain following operations. The specific format of these operations is as follows.

$0$ : clear all the points.

$1\ x\ y\ c$ : add a point which color is $c$ at point $(x,y)$.

$2\ x\ y_1\ y_2$ : count how many different colors in the square $(1,y_1)$ and $(x,y_2)$. That is to say, if there is a point $(a,b)$ colored $c$, that $1≤a≤x$ and $y_1≤b≤y_2$, then the color $c$ should be counted.

$3$ : exit.

Input

The input contains many lines.

Each line contains a operation. It may be 0, 1 x y c $( 1≤x,y≤10 ^ 6,0≤c≤50 )$, 2 x y1 y2 $(1≤x,y_1,y_2≤10 ^ 6 )$ or 3.

$x,y,c,y_1,y_2$ are all integers.

Assume the last operation is $3$ and it appears only once.

There are at most $150000$ continuous operations of operation $1$ and operation $2$.

There are at most $10$ operation $0$.

Output

For each operation $2$, output an integer means the answer.

Sample Input

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
0
1 1000000 1000000 50
1 1000000 999999 0
1 1000000 999999 0
1 1000000 1000000 49
2 1000000 1000000 1000000
2 1000000 1 1000000
0
1 1 1 1
2 1 1 2
1 1 2 2
2 1 1 2
1 2 2 2
2 1 1 2
1 2 1 3
2 2 1 2
2 10 1 2
2 10 2 2
0
1 1 1 1
2 1 1 1
1 1 2 1
2 1 1 2
1 2 2 1
2 1 1 2
1 2 1 1
2 2 1 2
2 10 1 2
2 10 2 2
3

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
1
2
2
3
3
1
1
1
1
1
1
1

思路

  • 菜鸡表示看到这题的第一反应就是线段树,可是用线段树维护什么呢?由于我们要查询一个区间内有多少种颜色,我们可以考虑沿着$y$方向建线段树,维护某种颜色$x$最小值,只要最小值在我们查询的$x$内,就有这种颜色。是的,你没看错,每一种颜色开一个线段树,最多也就$50$个。
  • 嗯,直接建$50$个线段树显然肉眼可见慢+MLE,所以我们要动态建树,因为单点更新每次操作只会多出$\log n$个新结点,这样的空间复杂度就是$q\log n$。然后单点更新和区间查询都是正常思路。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

#define Lson l, m, lson[rt]
#define Rson m + 1, r, rson[rt]

const int maxn = 1e6 + 5;
int minv[maxn << 2], lson[maxn << 2], rson[maxn << 2];
int tot, rt[55];

void init()
{
tot = 0;
clr(rt, 0);
clr(lson, 0);
clr(rson, 0);
}

void update(int p, int v, int l, int r, int &rt)
{
if (rt == 0)
rt = ++tot, minv[rt] = v;
minv[rt] = min(minv[rt], v);
if (l == r) return;
int m = (l + r) >> 1;
if (p <= m) update(p, v, Lson);
if (m < p) update(p, v, Rson);
}

bool flag;
void query(int L, int R, int v, int l, int r, int rt)
{
if (flag || rt == 0) return;
if (L <= l && r <= R)
{
if (minv[rt] <= v)
flag = true;
return;
}
int m = (l + r) >> 1;
if (L <= m) query(L, R, v, Lson);
if (m < R) query(L, R, v, Rson);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int cmd, x, y, c, y1, y2;
const int n = 1e6;
while (~scanf("%d", &cmd), cmd != 3)
{
if (cmd == 0)
init();
if (cmd == 1)
{
scanf("%d%d%d", &x, &y, &c);
update(y, x, 1, n, rt[c]);
}
if (cmd == 2)
{
int ans = 0;
scanf("%d%d%d", &x, &y1, &y2);
for (int i = 0; i <= 50; i++)
{
flag = false;
query(y1, y2, x, 1, n, rt[i]);
ans += flag;
}
printf("%d\n", ans);
}
}
return 0;
}
捐助作者
0%