将问题转换为，1.更新：在第一维线段树中每个包含R端点的节点， 在其对应节点所开的第二维线段树的L位置上更新权值v，2.查询：在第一维线段树区间[L,R]区间中，查询区间所开的第二维线段树区间[L,R]的最值，答案为两个最值相减

记得考虑线段端点重合的情况，否则会像我一样WA了一个下午。。。 因为这个题的范围有点大，刚好卡了比较好理解的线段树套线段树，所以只能动态开点了。。。

// Problem: Kera's line segment
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/17797/K
// Memory Limit: 1048576 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back

using namespace std;
using ll = long long;
using db = double;
using pii = pair<int , int>;

const int mod = 1e9 + 7;
const int maxn  = 3e3 + 10;


int n, m;
#define lson l, mid, num << 1
#define rson mid + 1, r, num << 1 | 1

struct node
{
	int l, r, ma, mi;
}tr[maxn * maxn];
int cnt;


	void update1(int rt, int id, int v, int l, int r)
	{
		if (l == r)
		{
			tr[rt].ma = max(tr[rt].ma, v);
			tr[rt].mi = min(tr[rt].mi, v);
			return;
		}
		int mid = l + r >> 1;
		if (id <= mid)
		{
			if (tr[rt].l == 0)
				tr[rt].l = ++cnt, tr[cnt].mi = tr[cnt].ma = v;
			update1(tr[rt].l, id, v, l, mid);
			tr[rt].ma = max(v, tr[rt].ma);
			tr[rt].mi = min(v, tr[rt].mi);
		}
		else
		{
			if (tr[rt].r == 0)
				tr[rt].r = ++cnt, tr[cnt].mi = tr[cnt].ma = v;
			update1(tr[rt].r, id, v, mid + 1, r);
			tr[rt].ma = max(v, tr[rt].ma);
			tr[rt].mi = min(v, tr[rt].mi);
		}
	}
	pii query1(int rt, int lef, int rig, int l, int r)
	{
		if (rt == 0)
		{
			return {0, mod};
		}
		if (lef <= l && rig >= r)
		{
			return {tr[rt].ma, tr[rt].mi};
		}
		int mid = l + r >> 1;
		pii ans = {0, mod};
		if (lef <= mid)
		{
			if (tr[rt].l)
			{
				pii t = query1(tr[rt].l, lef, rig, l, mid);
				ans.first = max(ans.first, t.first);
				ans.second = min(ans.second, t.second);
			}
		}
		if (rig > mid)
		{
			if (tr[rt].r)
			{
				pii t = query1(tr[rt].r, lef, rig, mid + 1, r);
				ans.first = max(ans.first, t.first);
				ans.second = min(ans.second, t.second);
			}
		}
		return ans;
	}
	
int tree[maxn * maxn];

void update(int id, int id2, int val, int l, int r, int num)
{
	if (tree[num] == 0) tree[num] = ++cnt, tr[cnt].ma = tr[cnt].mi = val;
	update1(tree[num], id2, val, 1, r);
	if (l == r) return;
	int mid = l + r >> 1;
	if (id <= mid)
		update(id, id2, val, lson);
	else update(id, id2, val, rson);
}

pii query(int lef, int rig, int l, int r, int num)
{
	if (l >= lef && r <= rig)
	{
		if (tree[num] == 0)
			return {0, mod};
		pii tt = query1(tree[num], lef, r, 1, r);
		return tt;
	}
	int mid = l + r >> 1;
	pii ans = {0, mod};
	if (lef <= mid)
	{
		pii t = query(lef, rig, l, mid, num << 1);
		ans.first = max(ans.first, t.first);
		ans.second = min(ans.second, t.second);
	}
	if (mid < rig)
	{
		pii t = query(lef, rig, mid + 1, r, num << 1 | 1);
		ans.first = max(ans.first, t.first);
		ans.second = min(ans.second, t.second);
	}
	return ans;
}

void solve()
{
	int i, j;
	int l, r, op, ls = 0, v;
	cin >> n >> m;
	for (i = 1; i <= n; i++)
	{
		cin >> l >> r >> v;
		update(r, l, v, 1, 3000, 1);
	}
	for (i = 1; i <= m; i++)
	{
		cin >> op >> l >> r;
		l = l ^ ls, r = r ^ ls;
		int xx = l, yy = r;
		if (l > r) swap(l, r);
		if (op == 1)
		{
			cin >> v;
			update(r, l, v, 1, 3000, 1);
		}
		else
		{
			pii tr = query(l, r, 1, 3000, 1);
			ls = tr.first - tr.second;
			cout << ls << endl;
		}
	}
}

int main()
{

    int T = 1;
   // cin >> T;
    while (T--)
        solve();
    
    return 0;
}

附上比较好理解的树套树，即把第二维抽象化了 当这题范围是1000-2000，应该就不会被卡

// Problem: Kera's line segment
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/17797/K
// Memory Limit: 1048576 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back

using namespace std;
using ll = long long;
using db = double;
//using pii = pair<int , int>;

const int mod = 1e9 + 7;
const int maxn  = 3e3 + 10;


int n, m;
#define lson l, mid, num << 1
#define rson mid + 1, r, num << 1 | 1

struct pii
{
	int first, second;
	pii(){first = 0, second = mod;}
	pii(int x, int y) {first = x, second = y;}
};


void ma(pii &a, pii b, pii c)
{
	a.first = max(b.first, c.first);
	a.second = min(b.second, c.second);
}

struct seg
{
	pii tree[maxn << 2];
	void update(int id, int v, int l, int r, int num)
	{
		int mid = l + r >> 1;
		if (l == r)
		{
			ma(tree[num], tree[num], {v, v});
			return;
		}
		if (id <= mid) update(id, v, lson);
		else update(id, v, rson);
		ma(tree[num], tree[num << 1], tree[num << 1 | 1]);
	}
	pii query(int lef, int rig, int l, int r, int num)
	{
		if (l >= lef && r <= rig)
			return tree[num];
		int mid = l + r >> 1;
		pii ans = {0, mod};
		if (mid >= lef)
		{
			pii t = query(lef, rig, lson);
			ma(ans, ans, t);
		}
		if (rig > mid)
		{
			pii t = query(lef, rig, rson);
			ma(ans, ans, t);
		}
		return ans;
	}
}tree[maxn << 2];

void update(int id, int id2, int val, int l, int r, int num)
{
	tree[num].update(id2, val, 1, 3000, 1);
	if (l == r) return;
	int mid = l + r >> 1;
	if (id <= mid)
		update(id, id2, val, lson);
	else update(id, id2, val, rson);
}

pii query(int lef, int rig, int l, int r, int num)
{
	if (l >= lef && r <= rig)
		return tree[num].query(lef, rig, 1, 3000, 1);
	int mid = l + r >> 1;
	pii ans = {0, mod};
	if (lef <= mid)
	{
		pii t = query(lef, rig, lson);
		ma(ans, ans, t);
	}
	if (mid < rig)
	{
		pii t = query(lef, rig, rson);
		ma(ans, ans, t);
	}
	return ans;
}

void solve()
{
	int i, j;
	int l, r, op, ls = 0, v;
	cin >> n >> m;
	for (i = 1; i <= n; i++)
	{
		cin >> l >> r >> v;
		update(r, l, v, 1, 3000, 1);
	}
	for (i = 1; i <= m; i++)
	{
		cin >> op >> l >> r;
		l = l ^ ls, r = r ^ ls;
		if (l > r)
			swap(l, r);
		if (op == 1)
		{
			cin >> v;
			update(r, l, v, 1, 3000, 1);
		}
		else
		{
			pii tr = query(l, r, 1, 3000, 1);
			ls = tr.first - tr.second;
			cout << ls << endl;
		}
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
   // cin >> T;
    while (T--)
        solve();
    
    return 0;
}

暴力竟然能偷过去。。。