Color it
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)Total Submission(s): 629 Accepted Submission(s): 167
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.
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.
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
题意：
一个空的坐标系，有④种操作：①1 x y c表示在(x, y)点染上颜色c；②2 X y1 y2表示查询在(1, y1)到(X, y2)范围内有多少种不同的颜色：
③0表示清屏；④3表示程序退出（0<=x, y<=1000000, 0<=c<=50）
主要就是前两个操作，因为颜色数量较少，所以给每种颜色建立一颗线段树然后暴力查找，但是又不能以整个坐标系建树，考虑到题目条件一定包含坐标横坐标1
那么就可以只建Y坐标轴包存离y轴最近的点的坐标
这题的操作也是骚的一逼，线段树和主席树的变种操作
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<map>
#include <set>
#include <bits/stdc++.h>
using namespace std;
const int N = 200000+10;
typedef long long LL;
int rt[55], ls[N*20], rs[N*20], val[N*20], cnt;
void add(int &o,int x,int y,int l,int r)
{
if(o==0) o=++cnt,val[o]=x;
if(val[o]==0||val[o]>x) val[o]=x;
if(l==r) return ;
int mid=(l+r)/2;
if(y<=mid) add(ls[o],x,y,l,mid);
else add(rs[o],x,y,mid+1,r);
return ;
}
int flag;
void query(int o,int X,int L,int R,int l,int r)
{
if(o==0||flag) return ;
if(l>=L&&r<=R)
{
if(val[o]<=X) flag=1;
return ;
}
int mid=(l+r)/2;
if(L<=mid) query(ls[o],X,L,R,l,mid);
if(R>mid) query(rs[o],X,L,R,mid+1,r);
return ;
}
int main()
{
memset(rt,0,sizeof(rt));
memset(ls,0,sizeof(ls));
memset(rs,0,sizeof(rs));
cnt=0;
int q;
while(scanf("%d", &q))
{
if(q==1)
{
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
add(rt[z],x,y,1,1000000);
}
else if(q==2)
{
int x, y1, y2, ans=0;
scanf("%d %d %d", &x, &y1, &y2);
for(int i=0; i<=50; i++)
{
flag=0;
query(rt[i],x,y1,y2,1,1000000);
ans+=flag;
}
printf("%d\n",ans);
}
else if(q==0)
{
memset(rt,0,sizeof(rt));
memset(ls,0,sizeof(ls));
memset(rs,0,sizeof(rs));
cnt=0;
}
else break ;
}
return 0;
}