题目
题解
将区间[L,R]视作坐标系中的点(L,R),那么添加线段[L,R]就是在坐标系上添加点(L,R);查询[L,R]就是查询范围{(l,r)|l <= L and r <= R}对应的矩形范围内的最大值和最小值的差值。由于只有添加没有删除,可以使用二维树状数组;或者使用树套树,支持单点修改区间查询。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 3000 + 10;
const int M = 998244353;
typedef long long ll;
#define endl '\n'
int mx[N][N];
int mi[N][N];
int lowbit(int x) {
return x&-x;
}
void upd(int l, int r, int val) {
int pl = N - l;
while(pl < N) {
int pr = r;
while(pr < N) {
mx[pl][pr] = max(mx[pl][pr], val);
mi[pl][pr] = min(mi[pl][pr], val);
pr += lowbit(pr);
}
pl += lowbit(pl);
}
}
int que(int l, int r) {
int rmx = 0;
int rmi = 0x3f3f3f3f;
int pl = N - l;
while(pl) {
int pr = r;
while(pr) {
rmx = max(mx[pl][pr], rmx);
rmi = min(mi[pl][pr], rmi);
pr -= lowbit(pr);
}
pl -= lowbit(pl);
}
if(rmi == 0x3f3f3f3f) return 0;
else return rmx - rmi;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
memset(mi, 0x3f, sizeof mi);
memset(mx, 0, sizeof mx);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int l, r, val;
cin >> l >> r >> val;
upd(l, r, val);
}
int ans = 0;
while(m--) {
int op, a, b;
cin >> op >> a >> b;
int l = a ^ ans, r = b ^ ans;
if(op == 1) {
int val;
cin >> val;
upd(l, r, val);
} else {
ans = que(l, r);
cout << ans << endl;
}
}
}