二维线段树
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#define PI atan(1.0)*4
#define e 2.718281828
#define rp(i,s,t) for (i = (s); i <= (t); i++)
#define RP(i,s,t) for (i = (t); i >= (s); i--)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int ls(int p){ return p<<1; }
int rs(int p){ return p<<1|1;}
int n=1000, s[1005][4005]; //s[i][j]：身高区间i，活泼区间j的最大缘分
void subBuild(int xp, int p, int pl, int pr) { //建立第二维线段树：活泼度线段树
s[xp][p] = -1;
if(pl == pr) return;
int mid=(pl+pr)>>1;
subBuild(xp, ls(p), pl, mid);
subBuild(xp, rs(p), mid + 1, pr);
}
void build(int p,int pl, int pr) { // 建立第一维线段树：身高线段树
subBuild(p, 1, 0, n); //行，列，元素个数
if(pl == pr) return;
int mid=(pl+pr)>>1;
build(ls(p),pl, mid);
build(rs(p),mid + 1, pr);
}
void subUpdate(int xp, int y, int c, int p, int pl, int pr) { //更新第二维线段树
if(pl == pr && pl == y) s[xp][p] = max(s[xp][p], c); //同样条件，留下最大缘分
else {
int mid=(pl+pr)>>1;
if(y <= mid) subUpdate(xp, y, c, ls(p), pl, mid);
else subUpdate(xp, y, c, rs(p), mid + 1, pr);
s[xp][p] = max(s[xp][ls(p)], s[xp][rs(p)]); //左右节点里的最大缘分赋值给父节点
}
}
void update(int x, int y, int c, int p, int pl, int pr){ //更新第一维线段树：身高x
subUpdate(p, y, c, 1, 0, n); //更新第二维线段树：活泼度y，线段树自上而下更新
if(pl != pr) { //一直更新到叶节点
int mid=(pl+pr)>>1;
if(x <= mid) update(x, y, c, ls(p), pl, mid);
else update(x, y, c, rs(p), mid + 1, pr);
}
}
int subQuery(int xp, int yL, int yR, int p, int pl, int pr) { //查询第二维线段树
if(yL <= pl && pr <= yR) return s[xp][p];
else {
int mid=(pl+pr)>>1;
int res = -1;
if(yL <= mid) res = subQuery(xp, yL, yR, ls(p), pl, mid);
if(yR > mid) res = max(res, subQuery(xp, yL, yR, rs(p), mid + 1, pr));
return res;
}
}
int query(int xL, int xR, int yL, int yR, int p, int pl, int pr) {//查询第一维线段树
if(xL <= pl && pr <= xR) return subQuery(p, yL, yR, 1, 0, n); //满足身高区间时，查询活泼度区间
else { //当前结点不满足身高区间
int mid = (pl+pr)>>1;
int res = -1;
if(xL <= mid) res = query(xL, xR, yL, yR, ls(p), pl, mid);
if(xR > mid) res = max(res, query(xL, xR, yL, yR, rs(p), mid + 1, pr));
return res;
}
}
int main(){
int t;
while(scanf("%d", &t) && t) {
build(1,100, 200);
while(t--) {
char ch[2]; scanf("%s", ch);
if(ch[0] == 'I') { //插入
int h;double c, d; scanf("%d%lf%lf", &h, &c, &d);
update(h, c * 10, d * 10, 1, 100, 200);
} else { //查询
int xL, xR, yL, yR; double c,d;
scanf("%d%d%lf%lf", &xL, &xR, &c, &d);
yL = c * 10, yR = d * 10; //转整数
if(xL > xR) swap(xL, xR); //区间左小右大
if(yL > yR) swap(yL, yR);
int ans = query(xL, xR, yL, yR, 1,100, 200); //x：身高，y：活泼度
if(ans == -1) printf("-1\n");
else printf("%.1f\n", ans / 10.0);
}
}
}
return 0;
}
笔记：二维线段树就是“树套树”，在外层的线段树的节点里，再放一个线段树。按照题目，外层线段是身高，内层线段是活泼度，内层节点储存的是缘分分值。程序里的线段树更新是从父结点先更新，留下最大值，再依次向下更新。查询也是在全覆盖的区间里返回最大值