Color it
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
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
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
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 1 1
1
2 1 1
2 1 1
1
1 1 2
1 1 2
1
2 1 1
2 1 1
2
1 2 2
1 2 2
1
2 1 1
2 1 1
2
1 2 1
1 2 1
1
2 2 1
2 2 1
2
2 10
2 10
1 2
2 10
2 10
2 2
3
Sample Output
2
3
1
2
2
3
3
1
1
1
1
1
1
1
3
1
2
2
3
3
1
1
1
1
1
1
1
题解：
对于加入的点，我把第一维， x 进行排序， cdq分治优化时间这一维，其余部分用线段树
因为只有50中颜色，我将每一位颜色进行二进制压缩，当作一个数存在线段树里
利用线段树查询一个区间有多少不同的颜色（位运算）
#include <bits/stdc++.h>
inline int read(){int x=,f=;char ch=getchar();while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}return x*f;}
using namespace std;
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
const int N = 1e6 + ;
namespace IO {
const int MX = 4e7; //1e7占用内存11000kb
char buf[MX]; int c, sz;
void begin() {
c = ;
sz = fread(buf, , MX, stdin);
}
inline bool read(int &t) {
while(c < sz && buf[c] != '-' && (buf[c] < '' || buf[c] > '')) c++;
if(c >= sz) return false;
bool flag = ; if(buf[c] == '-') flag = , c++;
for(t = ; c < sz && '' <= buf[c] && buf[c] <= ''; c++) t = t * + buf[c] - '';
if(flag) t = -t;
return true;
}
}
struct ss{
int op,x,y,z,id;
long long ans;
ss(int op = ,int x = ,int y = ,int z = ,int id = ,long long ans = ) : op(op), x(x), y(y), z(z), id(id), ans(ans) {}
}Q[N],t[N];
bool cmp(ss s1,ss s2) { if(s1.x == s2.x) return s1.op < s2.op;else return s1.x < s2.x; }
int n,mx,san[N];
void init() {n = ;}
long long v[N * ];
void update(int i,int ll,int rr,int x,long long c,int ff) {
if(ll == rr && x == ll) {if(!ff)v[i] |= 1LL<<c;else v[i] = c;return ;}
if(x <= mid) update(ls,ll,mid,x,c,ff);
else update(rs,mid+,rr,x,c,ff);
v[i] = v[ls] | v[rs];
}
long long ask(int i,int ll,int rr,int x,int y) {
if(x > y) return ;
if(ll == x && rr == y) return v[i];
if(y <= mid) return ask(ls,ll,mid,x,y);
else if(x > mid) return ask(rs,mid+,rr,x,y);
else return (ask(ls,ll,mid,x,mid) | ask(rs,mid+,rr,mid+,y));
}
void cdq(int ll,int rr) {
if(ll == rr) return ;
for(int i = ll; i <= rr; ++i) {
if(Q[i].id <= mid && Q[i].op == )
update(,,mx,Q[i].y,Q[i].z,);
else if(Q[i].id > mid && Q[i].op == )
Q[i].ans |= ask(,,mx,Q[i].y,Q[i].z);
}
for(int i = ll; i <= rr; ++i) {
if(Q[i].id <= mid && Q[i].op == )
update(,,mx,Q[i].y,,);
}
int L1 = ll, R1 = mid+;
for(int i = ll; i <= rr; ++i) {
if(Q[i].id <= mid) t[L1++] = Q[i];
else t[R1++] = Q[i];
}
for(int i = ll; i <= rr; ++i) Q[i] = t[i];
cdq(ll,mid);cdq(mid+,rr);
}
void solve() {
if(n == ) return ;
int cny = ;
for(int i = ; i <= n; ++i) {
if(Q[i].op == ) san[++cny] = Q[i].y;
else {
san[++cny] = Q[i].y;
san[++cny] = Q[i].z;
}
}
sort(san+,san+cny+);
int SA = unique(san+,san+cny+) - san - ;
for(int i = ; i <= n; ++i) {
if(Q[i].op == ) Q[i].y = lower_bound(san+,san+SA+,Q[i].y) - san;
else {
Q[i].y = lower_bound(san+,san+SA+,Q[i].y) - san;
Q[i].z = lower_bound(san+,san+SA+,Q[i].z) - san;
}
}
mx = SA;
sort(Q+,Q+n+,cmp);
cdq(,n);
for(int i = ; i <= n; ++i) {
if(Q[i].op == ) {
int sum = ;
for(int j = ; j <= ; ++j)
if((Q[i].ans >> j) & ) sum++;
printf("%d\n",sum);
}
}
}
int op,x,z,y;
int main() {
IO::begin();
while() {
IO::read(op);
if(op == || op == ) {
solve();
init();
if(op == ) return ;
continue;
}
IO::read(x);
IO::read(y);
IO::read(z);
Q[++n] = ss(op,x,y,z,n,);
}
return ;
}