Color it
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 302 Accepted Submission(s): 62
Problem Description
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
y1
y2
: count how many different colors in the square
(1,y1)
and
(x,y2)
. That is to say, if there is a point
(a,b)
colored
c
, that
1≤a≤x
and
y1≤b≤y2
, 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≤106,0≤c≤50
), '2 x y1 y2' (
1≤x,y1,y2≤106
) or '3'.
x,y,c,y1,y2
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
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
2
3
1
2
2
3
3
1
1
1
1
1
1
1
Source
2017ACM/ICPC广西邀请赛-重现赛（感谢广西大学）
解题思路：刚开始觉得这题很麻烦，因为可能会有点覆盖的情况，就是一个点先被一种颜色覆盖，然后被另外一种颜色覆盖，那么之前的颜色就没有了，但是，这题不会出现这种情况，就算被覆盖了，也算有两种颜色，从样例就可以看出，那么问题就变得很简单了，我们用50棵线段树搞一搞就行，我们按y坐标建树，维护x的最小值（为什么这样做，因为每次询问的矩形的左下点的横坐标是1，所以这样做可以化双边界约束为单边界，我们维护最小值就行），这里50棵线段树可能会超内存，所以要边更新，边建树，这样动态建树的话空间复杂度为O(n * logn)，因为每次更新，最多消耗logn个顶点。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 10;
int inf = 0x3f3f3f3f;
struct node
{
int l, r;
int lson, rson;
int sum;
int Min;
node()
{
sum = 0;
Min = inf;
lson = rson = 0;
}
}Node[maxn<<2];
int tot;
int root[55];
int judge;
void update(int &rt, int l, int r, int value, int Mi)
{
if(!rt) rt = ++tot;
Node[rt].l = l;
Node[rt].r = r;
Node[rt].sum++;
Node[rt].Min = min(Node[rt].Min, Mi);
if(l == r) return;
int mid = (l + r)>>1;
if(value <= mid) update(Node[rt].lson, l, mid, value, Mi);
else update(Node[rt].rson, mid + 1, r, value, Mi);
}
void query(int rt, int l, int r, int up)
{
if(!rt || judge) return;
if(Node[rt].l == l && Node[rt].r == r)
{
if(Node[rt].Min <= up && Node[rt].sum > 0)
{
judge = 1;
return;
}
return;
}
int mid = (Node[rt].l + Node[rt].r)>>1;
if(r <= mid) query(Node[rt].lson, l, r, up);
else if(l >= mid + 1) query(Node[rt].rson, l, r, up);
else
{
query(Node[rt].lson, l, mid, up);
query(Node[rt].rson, mid + 1, r, up);
}
}
void init()
{
tot = 0;
memset(root, 0, sizeof(root));
for(int i = 0; i < (maxn<<2); i++)
{
Node[i].lson = Node[i].rson = Node[i].sum = 0;
Node[i].Min = inf;
}
}
int main()
{
int op;
init();
while(~scanf("%d", &op) && op != 3)
{
if(op == 0) init();
else if(op == 1)
{
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
update(root[c], 1 , 1000000, y, x);
}
else if(op == 2)
{
int x, y1, y2;
scanf("%d%d%d", &x, &y1, &y2);
int ans = 0;
for(int i = 0; i <= 50; i++)
{
judge = 0;
query(root[i], y1, y2, x);
if(judge)
{
ans++;
}
}
printf("%d\n", ans);
}
}
return 0;
}
