题目大意：
有多次操作。操作0是清空二维平面的点，操作1是往二维平面（x,y）上放一个颜色为c的点，操作2是查询一个贴着y轴的矩形内有几种颜色的点，操作3退出程序。
思路：
由于查询的矩形是贴着y轴的，所以以y轴为线段树节点，建立52颗线段树，然后每个节点都保存这个纵坐标下x的最小值，然后查询。
这样的线段树显然是开不下的，所以我们考虑线段树动态开点，但是发现有50颗，如果按照50*n*logn的查询，还是会TLE，这里需要一个减枝，就是如果一部分区间内已经有一个颜色了，就直接退出所有查询即可，否则会TLE（卡常数？）
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=;
int rt[],tot;
int R[maxn*],L[maxn*],v[maxn*],flag;
int op,x,y,y1,y2,co;
void init(){
tot=,clr(rt,);
}
void update(int &o,int l,int r,int y,int x){
if(!o){
L[o=++tot]=,R[o]=;
v[o]=x;
}
v[o]=min(v[o],x);
if(l==r)return;
int mid=(l+r)>>;
if(y<=mid)update(L[o],l,mid,y,x);
else update(R[o],mid+,r,y,x);
}
void query(int o,int l,int r,int ql,int qr){
if(flag||!o){
return ;
}
if(ql<=l&&qr>=r)
{
if(v[o]<=x)flag=;
return;
}
int mid=(l+r)>>; if(ql<=mid)query(L[o],l,mid,ql,qr);
if(qr>mid)query(R[o],mid+,r,ql,qr);
return ;
}
int main(){
// freopen("simple.in","r",stdin);
int n=1e6;
while(scanf("%d",&op)!=EOF){
if(op==)break;
else if(op==){
init();
}else if(op==){
scanf("%d%d%d",&x,&y,&co);
update(rt[co],,n,y,x);
}else{
scanf("%d%d%d",&x,&y1,&y2);
int ans=;
for(int i=;i<=;i++)
{
flag=;
query(rt[i],,n,y1,y2);
ans+=flag;
}
printf("%d\n",ans);
}
}
}
Color it
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 2327 Accepted Submission(s): 703
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.
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.
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
3
1
2
2
3
3
1
1
1
1
1
1
1