hdu6183-2017广西邀请赛 发表于 2018-10-30 | 分类于 题解 | 阅读数 次 链接:hdu6183-2017广西邀请赛 题解 仔细观察,可以发现我们只要维护每个y轴区间内最小的x就可以了 显然51棵线段树就可以解决,普通线段树是开不下的,所以需要动态开点 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e6+7;const int inf=0x3f3f3f3f;int rt[55],lson[N],rson[N],v[N],cnt,op,res,X;void update(int &o,int l,int r,int x,int y){ if(!o)v[o=++cnt]=x; v[o]=min(v[o],x); if(l==r)return ; int mid=l+r>>1; if(y<=mid)update(lson[o],l,mid,x,y); else update(rson[o],mid+1,r,x,y);}void query(int o,int l,int r,int a,int b){ if(!o||res)return ; if(a<=l&&b>=r){res=(v[o]<=X);return ;} int mid=l+r>>1; if(a<=mid)query(lson[o],l,mid,a,b); if(b>mid)query(rson[o],mid+1,r,a,b);}int main(){ while(~scanf("%d",&op)&&op!=3){ if(op==0){ cnt=0; memset(rt,0,sizeof rt); memset(lson,0,sizeof lson); memset(rson,0,sizeof rson); memset(v,0x3f,sizeof v); } else if(op==1){ int x,y,c; scanf("%d%d%d",&x,&y,&c); update(rt[c],1,N-3,x,y); } else { int ans=0,y1,y2; scanf("%d%d%d",&X,&y1,&y2); rep(i,0,50){ res=0; query(rt[i],1,N-3,y1,y2); if(res)ans++; } printf("%d\n",ans); } } return 0;}