题意:
共两种操作,
1)I a b c:插入一个MM,身高a,活跃值b,缘分值c。
2)Q a b c d:一次询问,输出身高在[a,b]内,活跃值在[c,d]内的最大缘分值。
共n次操作,开始为空,活跃值和缘分值精确到小数点后一位。
题解:
由于浮点型只有一位小数,所以可以*10来变成int型(注意浮点误差,一开始死在这了,*10竟然也出现误差。。)。之后就是标准的二维线段树了,跟一维线段树类似,不过在判断条件时比较多。这次看别人的写法写在一维数组内了。。汗。浪费了很多空间。
现在写了个标准点二维线段树,空间大幅度下降,时间也下降了一半。
代码:
之后写的代码:
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <queue> #include <stack> using namespace std; const int maxn=110; struct tree1{ int al,ar; int w; }; struct tree2{ int hl,hr; tree1 f[maxn*40]; }e[maxn*4]; void build1(int a,int b,int c,int d) { e[d].f[c].al=a; e[d].f[c].ar=b; e[d].f[c].w=-1; if(a==b)return ; int mid=(a+b)/2; build1(a,mid,2*c,d); build1(mid+1,b,2*c+1,d); } void build2(int a,int b,int x,int y,int c) { e[c].hl=x; e[c].hr=y; build1(a,b,1,c); if(x==y)return; int mid=(x+y)/2; build2(a,b,x,mid,2*c); build2(a,b,mid+1,y,2*c+1); } void update1(int a,int b,int c,int d,int val) { if(e[d].f[c].al==a&&e[d].f[c].ar==b) { if(e[d].f[c].w<val)e[d].f[c].w=val; return ; } int mid=(e[d].f[c].al+e[d].f[c].ar)/2; if(b<=mid)update1(a,b,2*c,d,val); else if(a>mid)update1(a,b,2*c+1,d,val); e[d].f[c].w=max(e[d].f[2*c].w,e[d].f[2*c+1].w); } void update2(int a,int b,int x,int y,int c,int val) { update1(a,b,1,c,val); if(e[c].hl==x&&e[c].hr==y) { return ; } int mid=(e[c].hl+e[c].hr)/2; if(y<=mid)update2(a,b,x,y,2*c,val); else if(x>mid)update2(a,b,x,y,2*c+1,val); } int query1(int a,int b,int c,int d) { if(e[d].f[c].al==a&&e[d].f[c].ar==b) { return e[d].f[c].w; } int mid=(e[d].f[c].al+e[d].f[c].ar)/2; if(b<=mid)return query1(a,b,2*c,d); else if(a>mid)return query1(a,b,2*c+1,d); else return max(query1(a,mid,2*c,d),query1(mid+1,b,2*c+1,d)); } int query2(int a,int b,int x,int y,int c) { if(e[c].hl==x&&e[c].hr==y) { return query1(a,b,1,c); } int mid=(e[c].hl+e[c].hr)/2; if(y<=mid)return query2(a,b,x,y,2*c); else if(x>mid)return query2(a,b,x,y,2*c+1); else return max(query2(a,b,x,mid,2*c),query2(a,b,mid+1,y,2*c+1)); } int main() { int n; while(scanf("%d",&n)!=EOF) { if(n==0)break; build2(0,1000,100,200,1); int i,j,k,a,b,x,y,ans; double c,d; char s[2]; for(i=0;i<n;i++) { scanf("%s",s); if(s[0]=='I') { scanf("%d%lf%lf",&a,&c,&d); x=(int)(c*10+0.5); y=(int)(d*10+0.5); update2(x,x,a,a,1,y); } else { scanf("%d%d%lf%lf",&a,&b,&c,&d); x=(int)(c*10+0.5); y=(int)(d*10+0.5); if(a>b)swap(a,b); if(x>y)swap(x,y); //printf("%d %d %d %d\n",x,y,a,b); ans=query2(x,y,a,b,1); if(ans==-1)printf("-1\n"); else printf("%.1f\n",ans/10.0); } } } return 0; } /* #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <queue> #include <stack> using namespace std; const int maxn=2100000; struct node{ int al,ar,hl,hr,w; }e[maxn]; int maxv=-1; void build(int a,int b,int x,int y,int c) { //if(c>maxv)maxv=c; //printf("%d %d %d %d %d\n",a,b,x,y,c); e[c].al=a;e[c].ar=b;e[c].hl=x;e[c].hr=y; e[c].w=-1; if(a==b&&x==y)return ; int amid=(a+b)/2; int hmid=(x+y)/2; build(a,amid,x,hmid,4*c); if(hmid<y);build(a,amid,hmid+1,y,4*c+1); if(amid<b)build(amid+1,b,x,hmid,4*c+2); if(amid<b&&hmid<y)build(amid+1,b,hmid+1,y,4*c+3); } void update(int a,int b,int x,int y,int c,int val) { if(e[c].al==a&&e[c].ar==b&&e[c].hl==x&&e[c].hr==y) { if(val>e[c].w)e[c].w=val; return ; } int amid=(e[c].al+e[c].ar)/2; int hmid=(e[c].hl+e[c].hr)/2; if(b<=amid&&y<=hmid)update(a,b,x,y,4*c,val); else if(b<=amid&&x>hmid)update(a,b,x,y,4*c+1,val); else if(a>amid&&y<=hmid)update(a,b,x,y,4*c+2,val); else if(a>amid&&x>hmid)update(a,b,x,y,4*c+3,val); e[c].w=max(max(max(e[4*c].w,e[4*c+1].w),e[4*c+2].w),e[4*c+3].w); //printf("%d %d %d %d %d\n",e[c].al,e[c].ar,e[c].hl,e[c].hr,e[c].w); } int query(int a,int b,int x,int y,int c) { if(e[c].al==a&&e[c].ar==b&&e[c].hl==x&&e[c].hr==y)return e[c].w; int amid=(e[c].al+e[c].ar)/2; int hmid=(e[c].hl+e[c].hr)/2; if(b<=amid) { if(y<=hmid)return query(a,b,x,y,4*c); else if(x>hmid)return query(a,b,x,y,4*c+1); else return max(query(a,b,x,hmid,4*c),query(a,b,hmid+1,y,4*c+1)); } else if(a>amid) { if(y<=hmid)return query(a,b,x,y,4*c+2); else if(x>hmid)return query(a,b,x,y,4*c+3); else return max(query(a,b,x,hmid,4*c+2),query(a,b,hmid+1,y,4*c+3)); } else { if(y<=hmid)return max(query(a,amid,x,y,4*c),query(amid+1,b,x,y,4*c+2)); else if(x>hmid)return max(query(a,amid,x,y,4*c+1),query(amid+1,b,x,y,4*c+3)); else return max(max(max(query(a,amid,x,hmid,4*c),query(a,amid,hmid+1,y,4*c+1)), query(amid+1,b,x,hmid,4*c+2)),query(amid+1,b,hmid+1,y,4*c+3)); } } int main() { int n; while(scanf("%d",&n)!=EOF) { if(n==0)break; build(100,200,0,1000,1); //printf("*%d\n",maxv); int i,j,k,a,b,x,y,ans; double c,d; char s[2]; for(i=0;i<n;i++) { scanf("%s",s); if(s[0]=='I') { scanf("%d%lf%lf",&a,&c,&d); x=(int)(c*10+0.5); y=(int)(d*10+0.5); update(a,a,x,x,1,y); } else { scanf("%d%d%lf%lf",&a,&b,&c,&d); x=(int)(c*10+0.5); y=(int)(d*10+0.5); if(a>b)swap(a,b); if(x>y)swap(x,y); ans=query(a,b,x,y,1); if(ans==-1)printf("-1\n"); else printf("%.1f\n",ans/10.0); } } } return 0; } */
一开始写的代码,将一堆空间浪费了。。
</pre><pre name="code" class="cpp">#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <queue> #include <stack> using namespace std; const int maxn=2100000; struct node{ int al,ar,hl,hr,w; }e[maxn]; int maxv=-1; void build(int a,int b,int x,int y,int c) { //if(c>maxv)maxv=c; //printf("%d %d %d %d %d\n",a,b,x,y,c); e[c].al=a;e[c].ar=b;e[c].hl=x;e[c].hr=y; e[c].w=-1; if(a==b&&x==y)return ; int amid=(a+b)/2; int hmid=(x+y)/2; build(a,amid,x,hmid,4*c); if(hmid<y);build(a,amid,hmid+1,y,4*c+1); if(amid<b)build(amid+1,b,x,hmid,4*c+2); if(amid<b&&hmid<y)build(amid+1,b,hmid+1,y,4*c+3); } void update(int a,int b,int x,int y,int c,int val) { if(e[c].al==a&&e[c].ar==b&&e[c].hl==x&&e[c].hr==y) { if(val>e[c].w)e[c].w=val; return ; } int amid=(e[c].al+e[c].ar)/2; int hmid=(e[c].hl+e[c].hr)/2; if(b<=amid&&y<=hmid)update(a,b,x,y,4*c,val); else if(b<=amid&&x>hmid)update(a,b,x,y,4*c+1,val); else if(a>amid&&y<=hmid)update(a,b,x,y,4*c+2,val); else if(a>amid&&x>hmid)update(a,b,x,y,4*c+3,val); e[c].w=max(max(max(e[4*c].w,e[4*c+1].w),e[4*c+2].w),e[4*c+3].w); //printf("%d %d %d %d %d\n",e[c].al,e[c].ar,e[c].hl,e[c].hr,e[c].w); } int query(int a,int b,int x,int y,int c) { if(e[c].al==a&&e[c].ar==b&&e[c].hl==x&&e[c].hr==y)return e[c].w; int amid=(e[c].al+e[c].ar)/2; int hmid=(e[c].hl+e[c].hr)/2; if(b<=amid) { if(y<=hmid)return query(a,b,x,y,4*c); else if(x>hmid)return query(a,b,x,y,4*c+1); else return max(query(a,b,x,hmid,4*c),query(a,b,hmid+1,y,4*c+1)); } else if(a>amid) { if(y<=hmid)return query(a,b,x,y,4*c+2); else if(x>hmid)return query(a,b,x,y,4*c+3); else return max(query(a,b,x,hmid,4*c+2),query(a,b,hmid+1,y,4*c+3)); } else { if(y<=hmid)return max(query(a,amid,x,y,4*c),query(amid+1,b,x,y,4*c+2)); else if(x>hmid)return max(query(a,amid,x,y,4*c+1),query(amid+1,b,x,y,4*c+3)); else return max(max(max(query(a,amid,x,hmid,4*c),query(a,amid,hmid+1,y,4*c+1)), query(amid+1,b,x,hmid,4*c+2)),query(amid+1,b,hmid+1,y,4*c+3)); } } int main() { int n; while(scanf("%d",&n)!=EOF) { if(n==0)break; build(100,200,0,1000,1); //printf("*%d\n",maxv); int i,j,k,a,b,x,y,ans; double c,d; char s[2]; for(i=0;i<n;i++) { scanf("%s",s); if(s[0]=='I') { scanf("%d%lf%lf",&a,&c,&d); x=(int)(c*10+0.5); y=(int)(d*10+0.5); update(a,a,x,x,1,y); } else { scanf("%d%d%lf%lf",&a,&b,&c,&d); x=(int)(c*10+0.5); y=(int)(d*10+0.5); if(a>b)swap(a,b); if(x>y)swap(x,y); ans=query(a,b,x,y,1); if(ans==-1)printf("-1\n"); else printf("%.1f\n",ans/10.0); } } } return 0; }