hdu6183 Color it

题目大意 :
       D喜欢画画，为了防止他画太乱的画，D要你帮他维护一些操作，
        0:清除所有的颜色
        1 x y c:在点(x,y)添加颜色c
        2 x y1 y2:问矩形(1,y1)->(x,y2)中有多少种颜色

因为询问中x方向上的起点都是1，且只询问是存在性询问,所以我们贪心地维护每一行(yi)的每一种颜色出现的最小横坐标。
这样做时空复杂度都为50*n*logn
时空都不符合要求
对于时间：
剪枝1：我们在左右递归的时候，如果发现左子树存在解，则结束递归，不去搜索右子树。
剪枝2：维护区间最小值，当区间最小值大于询问值时，结束递归(此操作同时优化了空间)。

#include<bits/stdc++.h>
using namespace std;

#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=15e4+5;
int mii[maxn*2*25],rs[maxn*2*25],ls[maxn*2*25],tot;  // 90mb

void ini(){
    tot=0;
}
void push_son(int&son,int l,int r){
    if(son==0){
        son=++tot;
        ls[son]=0;
        rs[son]=0;
        mii[son]=0x7fffffff;
    }
}
void push_down(int rt,int l,int r){
    push_son(ls[rt],l,ml);
    push_son(rs[rt],mr,r);
}
void push_up(int rt,int l,int r){
    mii[rt]=min(mii[ls[rt]],mii[rs[rt]]);
}
void build(int&rt,int l,int r){//1 1 n
    rt=0;
    push_son(rt,l,r);
}
void update(int rt,int l,int r,int q,int d){
    if(l==r){
        mii[rt]=min(mii[rt],d);
    }
    else{
        push_down(rt,l,r);
        if(ml>=q) update(ls[rt],l,ml,q,d);
        else update(rs[rt],mr,r,q,d);
        push_up(rt,l,r);
    }
}
int query(int rt,int l,int r,int ql,int qr,int x){
    if(mii[rt]>x) return 0;
    if(ql<=l&&r<=qr){
        return 1;
    }
    else{
        push_down(rt,l,r);
        if(ml>=ql) if(query(ls[rt],l,ml,ql,qr,x)) return 1;
        if(mr<=qr) if(query(rs[rt],mr,r,ql,qr,x)) return 1;
        return 0;
    }
}

inline int read(){
    int ret=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while('0'<=ch&&ch<='9') ret=(ret<<1)+(ret<<3)+(ch^48),ch=getchar();
    return ret;
}

int rt[55];
int main(){
    while(true){
        int op=read();
        if(op==0){
            ini();
            for(int i=0;i<=50;i++) build(rt[i],1,1e6+5);
        }
        else if(op==1){
            int x,y,c;
            x=read();y=read();c=read();
            update(rt[c],1,1e6+5,y,x);
        }
        else if(op==2){
            int x,y1,y2;
            x=read();y1=read();y2=read();
            int ans=0;
            for(int i=0;i<=50;i++) ans+=query(rt[i],1,1e6+5,y1,y2,x);
            printf("%d\n",ans);
        }
        else break;
    }
}