ST 表 MLE：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, t, lst;
ll ans_xor, ans_sum, v;
int val[2000010];
int id[2000010];
ll mx[2000010];
struct node
{
	int val;
	int p;
}; vector <vector<node> > tree;
node Max(node x, node y)
{
	if ((ll)x.val - v * (ll)x.p > (ll)y.val - v * (ll)y.p) return x;
	return y;
}
void build()
{
	tree.push_back(vector<node>());
	for (int i = 1; i <= n; ++i)
	{
		tree.push_back(vector<node>());
		tree[i].push_back( (node){val[i], i} );
	}
	for (int i = 1; i <= 21; ++i)
	{
		for (int j = 1; j + (1 << i) - 1 <= n; ++j)
		{
			tree[j].push_back( Max(tree[j][i - 1], tree[j + (1 << (i - 1))][i - 1]) );
		}
	}
}
int f(int x)
{
	if (x < 2) return 0;
	return log2(x);	
}
node query(int ql, int qr)
{
	int k = f(qr - ql) + 1;
//	cout << ql << " " << qr << " " << k << endl;
	return Max(tree[ql][k - 1], tree[qr - (1 << (k - 1)) + 1][k - 1]);
}
int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> t >> v;
	for (int i = 1; i <= n; ++i)
		cin >> val[i];
	build();
	mx[1] = (ll)val[1] + v;
	lst = 1; id[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		if ((ll)val[i] > mx[i - 1] || ((ll)val[i] == mx[i - 1] && val[i] > val[lst]))
		{
			mx[i] = (ll)val[i] + v;
			lst = i;
		}
		else mx[i] = mx[i - 1] + v;
		id[i] = lst;
	}
	while (t--)
	{
		int x, k;
		cin >> x >> k;
		if (n - x + 1 < k)
			continue;
		ll tmp = -100;
		if (k != 1)
		{
			node cur = query(x + 1, x + k - 1);
			tmp = (ll)cur.val - (ll)(cur.p - x) * v;
		}
		ans_xor ^= max(mx[x - 1], tmp + 1);
		ans_sum += max(mx[x - 1], tmp + 1);
	}
	cout << ans_xor << " " << ans_sum;
    return 0;
}

线段树 TLE：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ls (pos << 1)
#define rs (ls | 1)
int n, t, lst;
ll ans_xor, ans_sum, v;
ll val[2000010];
int id[2000010];
ll mx[2000010];
struct node
{
	ll val;
	int p;
} tree[8000010];
node Max(node x, node y)
{
	if (x.val - v * x.p > y.val - v * y.p) return x;
	return y;
}
void build(int l, int r, int pos)
{
	if (l == r)
	{
		tree[pos] = (node){val[l], l};
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, ls);
	build(mid + 1, r, rs);
	tree[pos] = Max(tree[ls], tree[rs]);
}
node query(int l, int r, int pos, int ql, int qr)
{
	node res = (node){-10000000000, 1000000000};
	if (ql <= l && qr >= r) return tree[pos];
	int mid = (l + r) >> 1;
	if (ql <= mid)
		res = Max(res, query(l, mid, ls, ql, qr));
	if (qr > mid)
		res = Max(res, query(mid + 1, r, rs, ql, qr));
	return res;
}
int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> t >> v;
	for (int i = 1; i <= n; ++i)
		cin >> val[i];
	build(1, n, 1);
	mx[1] = val[1] + v;
	lst = 1; id[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		if (val[i] > mx[i - 1] || (val[i] == mx[i - 1] && val[i] > val[lst]))
		{
			mx[i] = val[i] + v;
			lst = i;
		}
		else mx[i] = mx[i - 1] + v;
		id[i] = lst;
	}
	while (t--)
	{
		int x, k;
		cin >> x >> k;
		if (n - x + 1 < k)
			continue;
		node cur = query(1, n, 1, x + 1, x + k - 1);
		ll tmp = cur.val - (ll)(cur.p - x) * v;
		ans_xor ^= max(mx[x - 1], tmp + 1);
		ans_sum += max(mx[x - 1], tmp + 1);
	}
	cout << ans_xor << " " << ans_sum;
    return 0;
}