题意：
二维线段树的查找与添加
注意：
- 二维线段树的更新方式要全更新：
(更新范围)
.....
.....
.....
.....
有一种错误的更新方式：
(更新范围)
.
.
.
.....
错误的代码
void addx(int x, int y, int v, int l, int r, int pos){
if (l == r){
addy(pos, y, v, 1, Size, 1);
return;
}
int mid = (l + r) >> 1;
if (mid >= x)
addx(x, y, v, lson);
else
addx(x, y, v, rson);
updatax(y, pos);
}
正确的代码
void addx(int x, int v, int l, int r, int pos){
addy(pos, b, v, 1, Size, 1);
if (l == r)
return;
int mid = (l + r) >> 1;
if (mid >= x)
addx(x, v, lson);
else
addx(x, v, rson);
}
poj 1195代码
#include <iostream>
#include <algorithm>
#define lson l, mid, pos << 1
#define rson mid + 1, r, pos << 1 | 1
using namespace std;
const int MAXN = 1030;
int tree[MAXN<<2][MAXN<<2];
int Size, a, b, c, d;
void updatay(int x, int p){
tree[x][p] = tree[x][p<<1] + tree[x][p<<1|1];
}
void addy(int x, int y, int v, int l, int r, int pos){
if (l == r){
tree[x][pos] += v;
return;
}
int mid = (l + r) >> 1;
if (mid >= y)
addy(x, y, v, lson);
else
addy(x, y, v, rson);
updatay(x, pos);
}
void addx(int x, int v, int l, int r, int pos){
addy(pos, b, v, 1, Size, 1);
if (l == r)
return;
int mid = (l + r) >> 1;
if (mid >= x)
addx(x, v, lson);
else
addx(x, v, rson);
}
int findy(int x, int L, int R, int l, int r, int pos){
if (l >= L && r <= R)
return tree[x][pos];
int mid = (l + r) >> 1;
int ans = 0;
if (mid >= L)
ans += findy(x, L, R, lson);
if (mid < R)
ans += findy(x, L, R, rson);
return ans;
}
int findx(int xl, int xr, int l, int r, int pos){
if (l >= xl && r <= xr)
return findy(pos, b, d, 1, Size, 1);
int mid = (l + r) >> 1;
int ans = 0;
if (mid >= xl)
ans += findx(xl, xr, lson);
if (mid < xr)
ans += findx(xl, xr, rson);
return ans;
}
int main(){
int n, ans;
while (~scanf("%d", &n) && n != 3){
if (n == 0)
scanf("%d", &Size);
else if (n == 1){
scanf("%d%d%d", &a, &b, &c);
b++;
addx(a+1, c, 1, Size, 1);
}
else if (n == 2){
scanf("%d%d%d%d", &a, &b, &c, &d);
b++;
d++;
ans = findx(a+1, c+1, 1, Size, 1);
printf("%d\n", ans);
}
}
return 0;
}
hdu 1823代码解法1
#include <iostream>
#include <algorithm>
#include <cstring>
#define lson l, mid, pos << 1
#define rson mid + 1, r, pos << 1 | 1
using namespace std;
const int MAXH = 110;
const int MAXN = 1010;
int tree[MAXH<<2][MAXN<<2];
int maxh = 101, maxn = 1001; //maxn是1001而不是1000, 因为有0.0这个元素, maxh同理
int a, aa;
double b, c;
void updatay(int x, int p){
tree[x][p] = max(tree[x][p<<1], tree[x][p<<1|1]);
}
void addy(int x, int y, int v, int l, int r, int pos){
if (l == r){
tree[x][pos] = max(tree[x][pos], v); //可能叠加，取最大
return;
}
int mid = (l + r) >> 1;
if (mid >= y)
addy(x, y, v, lson);
else
addy(x, y, v, rson);
updatay(x, pos);
}
void addx(int x, int v, int l, int r, int pos){
addy(pos, (int)b, v, 1, maxn, 1);
if (l == r)
return;
int mid = (l + r) >> 1;
if (mid >= x)
addx(x, v, lson);
else
addx(x, v, rson);
}
int findy(int x, int L, int R, int l, int r, int pos){
if (l >= L && r <= R)
return tree[x][pos];
int mid = (l + r) >> 1;
int ans = 0;
if (mid >= L)
ans = findy(x, L, R, lson);
if (mid < R)
ans = max(ans, findy(x, L, R, rson));
return ans;
}
int findx(int xl, int xr, int l, int r, int pos){
if (l >= xl && r <= xr)
return findy(pos, (int)b, (int)c, 1, maxn, 1);
int mid = (l + r) >> 1;
int ans = 0;
if (mid >= xl)
ans = findx(xl, xr, lson);
if (mid < xr)
ans = max(ans, findx(xl, xr, rson));
return ans;
}
int main(){
int m;
double ans;
char op;
while (~scanf("%d", &m) && m != 0){
memset(tree, 0, sizeof(tree));
while (m--){
scanf(" %c", &op);
if (op == 'I'){
scanf("%d%lf%lf", &a, &b, &c);
a = a - 99;
b = b * 10 + 1;
c = c * 10 + 1; //缘分值向右偏移 1 ，为什么？因为线段树初始化为0，缘分值也有0，会冲突，既无法判断范围内有没有mm
addx(a, (int)c, 1, maxh, 1);
}
else{
scanf("%d%d%lf%lf", &a, &aa, &b, &c);
a = a - 99;
aa = aa - 99;
b = b * 10 + 1;
c = c * 10 + 1;
if (a > aa)
swap(a, aa); //这是个坑
if (b > c)
swap(b, c); //这是个坑
ans = (findx(a, aa, 1, maxh, 1) - 1) * 1.0 / 10;
if (ans < 0) // ans == -0.1
printf("-1\n");
else
printf("%.1lf\n", ans);
}
}
}
return 0;
}
hdu 1823代码解法2
#include <iostream>
#include <algorithm>
#include <cstring>
#define lson l, mid, pos << 1
#define rson mid + 1, r, pos << 1 | 1
using namespace std;
const int MAXH = 110;
const int MAXN = 1010;
int tree[MAXH<<2][MAXN<<2];
int maxh = 101, maxn = 1001; //maxn是1001而不是1000, 因为有0.0这个元素, maxh同理
int a, aa;
double b, c;
void updatay(int x, int p){
tree[x][p] = max(tree[x][p<<1], tree[x][p<<1|1]);
}
void addy(int x, int y, int v, int l, int r, int pos){
if (l == r){
tree[x][pos] = max(tree[x][pos], v); //可能叠加
return;
}
int mid = (l + r) >> 1;
if (mid >= y)
addy(x, y, v, lson);
else
addy(x, y, v, rson);
updatay(x, pos);
}
void addx(int x, int v, int l, int r, int pos){
addy(pos, (int)b, v, 1, maxn, 1);
if (l == r)
return;
int mid = (l + r) >> 1;
if (mid >= x)
addx(x, v, lson);
else
addx(x, v, rson);
}
int findy(int x, int L, int R, int l, int r, int pos){
if (l >= L && r <= R)
return tree[x][pos];
int mid = (l + r) >> 1;
int ans = -1;
if (mid >= L)
ans = findy(x, L, R, lson);
if (mid < R)
ans = max(ans, findy(x, L, R, rson));
return ans;
}
int findx(int xl, int xr, int l, int r, int pos){
if (l >= xl && r <= xr)
return findy(pos, (int)b, (int)c, 1, maxn, 1);
int mid = (l + r) >> 1;
int ans = -1;
if (mid >= xl)
ans = findx(xl, xr, lson);
if (mid < xr)
ans = max(ans, findx(xl, xr, rson));
return ans;
}
int main(){
int m;
double ans;
char op;
while (~scanf("%d", &m) && m != 0){
memset(tree, -1, sizeof(tree));
while (m--){
scanf(" %c", &op);
if (op == 'I'){
scanf("%d%lf%lf", &a, &b, &c);
a = a - 99;
b = b * 10 + 1;
c = c * 10; //不用偏移，因为线段树初始化为-1，不与0.0冲突
addx(a, (int)c, 1, maxh, 1);
}
else{
scanf("%d%d%lf%lf", &a, &aa, &b, &c);
a = a - 99;
aa = aa - 99;
b = b * 10 + 1;
c = c * 10 + 1;
if (a > aa)
swap(a, aa); //...
if (b > c)
swap(b, c); //...
ans = findx(a, aa, 1, maxh, 1) * 1.0 / 10;
if (ans == -1)
printf("-1\n");
else
printf("%.1lf\n", ans);
}
}
}
return 0;
}