题目链接:hdu1823二维线段树单点更新区间查询
题意
向一个100*1000的二维空间中插入点,每次查询时,查询区间最大值.
题解
身高既然是100~200,那就相当于100;活泼度相当于1000.所以建立100*1000的二维线段树.
大坑有如下几个
输出-1,而不是-1.0
输入的h1,h2,a1,a2,大小不一定,需要加上一个判断
代码
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<string>
using namespace std;
typedef long long ll;
#define re(i,n) for(int i=0;i<n;i++)
const int maxn = 4;
const int xsz = 107, ysz = 1007;
double h,a, l;
double hf, ht, af, at;
double tr[(xsz+1)<<2][(ysz+1)<<2];
#define lson(id) id<<1,f,mid
#define rson(id) id<<1|1,mid+1,t
void yinsert(int x, int y, int f, int t){tr[x][y] = max(tr[x][y], l);if (f == t)return;int mid = (f + t) >> 1;if (a <= mid)yinsert(x, lson(y));else yinsert(x, rson(y));
}
void xinsert(int id,int f,int t){yinsert(id, 1, 0, ysz);if (f == t)return;int mid = (f + t) >> 1;if (h <= mid)xinsert(lson(id));else xinsert(rson(id));
}
void yquery(int x, int y, int f, int t){if (af <= f&&at >= t){l = max(l, tr[x][y]);return;}int mid = (f + t) >> 1;if (af <= mid)yquery(x, lson(y));if (at > mid)yquery(x, rson(y));
}
void xquery(int x, int f, int t){if (hf <= f&&ht >= t){yquery(x, 1, 0, ysz);return;}int mid = (f + t) >> 1;if (ht > mid)xquery(rson(x));if(hf<=mid) xquery(lson(x));
}
void yclear(int x, int y, int f, int t){tr[x][y] = -1;if (f == t)return;int mid = (f + t) >> 1;yclear(x, lson(y)), yclear(x, rson(y));
}
void xclear(int x, int f, int t){yclear(x, 1, 0, ysz);if (f == t)return;int mid = (f + t) >> 1;xclear(lson(x)), xclear(rson(x));
}
int main(){freopen("in.txt", "r", stdin); int Q;while (scanf("%d", &Q) && Q){xclear(1, 0, xsz);while (Q--){char op[2]; scanf("%s", op);if (op[0] == 'I'){ scanf("%lf%lf%lf", &h, &a, &l);h -= 100, a *= 10;xinsert(1,0,xsz);}else{scanf("%lf%lf%lf%lf", &hf, &ht, &af, &at);hf -= 100, ht -= 100, af *= 10, at *= 10;if (hf > ht)swap(hf, ht); if (af > at)swap(af, at);l= -1;xquery(1,0,xsz);if (l == -1)puts("-1");else printf("%.1lf\n", l);}}}return 0;
}
