萌新刚学OI,求助HDU6183

回复帖子

@x义x 2019-01-12 11:36 回复

一道动态开点线段树的模板题,不知为何TLE……

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

const int INF=1<<29;

int inline read(){
    int num=0,neg=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
    while(isdigit(c)) num=num*10+c-'0',c=getchar();
    return num*neg;
}

vector<int> Min[55],Lc[55],Rc[55];int idx[55];
void Update(int C,int x,int l,int r,int X,int K){
    Min[C][x]=min(Min[C][x],K);
    if(l==r) return;
    int mid=(l+r)/2;
    if(X<=mid){
        if(!Lc[C][x]){
            Lc[C][x]=++idx[C];
            Min[C].push_back(INF),Lc[C].push_back(0),Rc[C].push_back(0);
        }
        Update(C,Lc[C][x],l,mid,X,K);
    }
    else{
        if(!Rc[C][x]){
            Rc[C][x]=++idx[C];
            Min[C].push_back(INF),Lc[C].push_back(0),Rc[C].push_back(0);
        }
        Update(C,Rc[C][x],mid+1,r,X,K); 
    }
}
int Query(int C,int x,int l,int r,int L,int R){
    if(!x) return INF;
    if(L<=l && r<=R) return Min[C][x];
    int mid=(l+r)/2,ans=INF;
    if(L<=mid) ans=min(ans,Query(C,Lc[C][x],l,mid,L,R));
    if(R>mid) ans=min(ans,Query(C,Rc[C][x],mid+1,r,L,R));
    return ans;
}

int opr;

int main(){
    opr=read();
    while(opr!=3){
        for(int i=0;i<=50;i++){
            Min[i].clear(),Lc[i].clear(),Rc[i].clear();
            Min[i].push_back(INF),Lc[i].push_back(0),Rc[i].push_back(0);
            Min[i].push_back(INF),Lc[i].push_back(0),Rc[i].push_back(0);
            idx[i]=1;
        }
        while(opr!=0 && opr!=3){
            if(opr==1){
                int x=read(),y=read(),c=read();
                Update(c,1,1,1000000,y,x);
            }
            else{
                int x=read(),y1=read(),y2=read(),ans=0;
                for(int i=0;i<=50;i++){
                    if(Query(i,1,1,1000000,y1,y2)<=x) ans++;
                }
                printf("%d\n",ans);
            }
            opr=read();
        }
        if(opr==3) return 0;
        opr=read();
    }
}
@BIGBUG 2019-01-12 15:06 回复

$\Huge \text{去}_{\text{你}_{\text{的}_{\text{萌}_{\text{新}}}}}$

真正的萌新正瑟瑟发抖