题目大意：
有多次操作。操作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=100005; int rt[52],tot; int R[maxn*20],L[maxn*20],v[maxn*20],flag; int op,x,y,y1,y2,co; void init(){ tot=0,clr(rt,0); } void update(int &o,int l,int r,int y,int x){ if(!o){ L[o=++tot]=0,R[o]=0; v[o]=x; } v[o]=min(v[o],x); if(l==r)return; int mid=(l+r)>>1; if(y<=mid)update(L[o],l,mid,y,x); else update(R[o],mid+1,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=1; return; } int mid=(l+r)>>1; if(ql<=mid)query(L[o],l,mid,ql,qr); if(qr>mid)query(R[o],mid+1,r,ql,qr); return ; } int main(){ // freopen("simple.in","r",stdin); int n=1e6; while(scanf("%d",&op)!=EOF){ if(op==3)break; else if(op==0){ init(); }else if(op==1){ scanf("%d%d%d",&x,&y,&co); update(rt[co],1,n,y,x); }else{ scanf("%d%d%d",&x,&y1,&y2); int ans=0; for(int i=0;i<=50;i++) { flag=0; query(rt[i],1,n,y1,y2); ans+=flag; } printf("%d ",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
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
Source
Recommend