题意概述
一个长度为 \(n\) 的序列 \(a\)，初始全 \(0\)。
有一个长度为 \(m\) 的操作序列 \((r_i, v_i)\)，每个操作表示将 \(a[1, r_i]\) 和 \(v_i\) 取 \(\max\)。
给定 \(q\) 次询问，求依次执行 \([L_i, R_i]\) 里面的操作之后 \(a\) 的和。
特别地，设 \(p_i\) 表示左边第一个 \(v_j > v_i\) 的位置，那么有 \(\max_{j=p_i+1}^i r_j = r_i\)。
输出所有询问答案的异或和。
多测，\(T=5，1 \le n, m, q \le 10^5，1 \le v_i \le 10^9\)。
思路
根据特别约束，如果询问区间 \([L, R]\) 包含 \(i\)，那么 \([p_i+1,i-1]\) 是没有贡献的。考虑连 \(p_i\) 到 \(i\) 的边，建出来的图是个森林。求 \(p_i\) 的过程可以用单调栈实现。
每次查询所有需要考虑的点就是 \([L, R]\) 包含的最长链，记深度小的为链头。
不难发现，链中元素的 \(v\) 是递减的，于是链中能产生贡献的点就是 \(r_u > curR\) 的点，这样会产生 \(v_u \times (r_u - curR)\) 的贡献。而通过维护 \(r\) 的最大值，这样的点是可以在链上二分找到的，那么先找链头，从链头开始跳即可。
可以倍增或者树剖实现，每个询问的链都是由若干个块拼接形成，每次跳跃都是找深度最小的 \(u\) 满足 \(r_u \gt curR\) ，倍增的做法就维护块的最大 \(r\)，分治寻找；树剖的做法就用线段树维护最大 \(r\)，在线段树上二分寻找。
期望时间复杂度应该是 \(\mathcal{O}(q\cdot \log^2 m)\) ，预处理部分取决于实现。
倍增代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int INF = 1e9;void solve(){int n,m,q;cin >> n >> m >> q;vector<int> R(m+1);vector<ll> V(m+1);for (int i=1;i<=m;i++){cin >> R[i] >> V[i];}vector<int> p(m+1);stack<int> stk;for (int i=1;i<=m;i++){while (!stk.empty() && V[i]>=V[stk.top()]){stk.pop();}p[i] = stk.empty()?-1:stk.top();stk.push(i);}vector<vector<int>> dp(m+1,vector<int>(32,-1));vector<vector<int>> mxr(m+1,vector<int>(32,-INF));for (int i=1;i<=m;i++){if (p[i]!=-1){dp[i][0] = p[i];mxr[i][0] = R[i]; }}for (int k=1;k<32;k++){for (int i=1;i<=m;i++){if (dp[i][k-1]==-1) continue;dp[i][k] = dp[dp[i][k-1]][k-1];mxr[i][k] = max(mxr[i][k-1],mxr[dp[i][k-1]][k-1]);}}ll fres = 0;while (q--){int l,r;cin >> l >> r;vector<pair<int,int>> wait;int cur = r;for (int k=31;k>=0;k--){if (dp[cur][k]>=l){wait.emplace_back(cur,k);cur = dp[cur][k];}}reverse(wait.begin(),wait.end());ll res = V[cur]*R[cur];ll curR = R[cur];function<void(int,int)> cal = [&](int s,int k){if (mxr[s][k]<=curR) return;if (k==0){res += V[s]*(R[s]-curR);curR = R[s];return;}cal(dp[s][k-1],k-1);cal(s,k-1);};for (auto& [s,k]:wait){cal(s,k);}fres^=res;}cout << fres << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--) solve();return 0;
}
树剖代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int INF = 1e9;class node{
public:int mx = -INF;
};class segmentTree{
public:int n;vector<node> seg;segmentTree(int _n){n = _n;seg = vector<node>(4*n+1);}node merge(node p1,node p2){node temp;temp.mx = max(p1.mx,p2.mx);return temp;}void build(vector<ll>& a){build(1,1,n,a);} void build(int rt,int l,int r,vector<ll>& a){if (l==r){seg[rt].mx = a[l];return;} int mid = l+r >> 1;build(rt<<1,l,mid,a);build(rt<<1|1,mid+1,r,a);seg[rt] = merge(seg[rt<<1],seg[rt<<1|1]); }void push_down(int rt,int l,int r){}void update(int pos,ll val){update(1,1,n,pos,val);}void update(int rt,int l,int r,int pos,ll val){if (l==r){//return;} int mid = l+r >> 1;push_down(rt,l,r);if (pos<=mid){update(rt<<1,l,mid,pos,val);}else{update(rt<<1|1,mid+1,r,pos,val);}seg[rt] = merge(seg[rt<<1],seg[rt<<1|1]);}void update_range(int x,int y,ll val){update_range(1,1,n,x,y,val);}void update_range(int rt,int l,int r,int x,int y,ll val){if (r<x || l>y){return;}if (x<=l && y>=r){//return;}int mid = l+r >> 1;push_down(rt,l,r);update_range(rt<<1,l,mid,x,y,val);update_range(rt<<1|1,mid+1,r,x,y,val);seg[rt] = merge(seg[rt<<1],seg[rt<<1|1]);}node query(int pos){if (pos<1 || pos>n) return {};return query(1,1,n,pos);}node query(int rt,int l,int r,int pos){if (l==r){return seg[rt];} int mid = l+r >> 1;push_down(rt,l,r);if (pos<=mid){return query(rt<<1,l,mid,pos);}else{return query(rt<<1|1,mid+1,r,pos);}}node query_range(int l,int r){if (l<1 || l>n || r<1 || r>n || l>r) return {};return query_range(1,1,n,l,r);}node query_range(int rt,int l,int r,int x,int y){if (r<x || l>y){return {};}if (x<=l && y>=r){return seg[rt];}int mid = l+r >> 1;push_down(rt,l,r);return merge(query_range(rt<<1,l,mid,x,y),query_range(rt<<1|1,mid+1,r,x,y));}bool is_valid(int rt,int l,int r,int x,int y,ll val){if (r<x || l>y) return false;if (seg[rt].mx>val){return true;}return false;}int first_valid(int l,int r,ll val){if (l>r) return -1;return first_valid(1,1,n,l,r,val);}int first_valid(int rt,int l,int r,int x,int y,ll val){if (!is_valid(rt,l,r,x,y,val)) return -1;if (l==r){return l;}int mid = l+r >> 1;push_down(rt,l,r);int res = first_valid(rt<<1,l,mid,x,y,val);if (res!=-1){return res;}return first_valid(rt<<1|1,mid+1,r,x,y,val);}int last_valid(int l,int r,ll val){if (l>r) return -1;return last_valid(1,1,n,l,r,val); }int last_valid(int rt,int l,int r,int x,int y,ll val){if (!is_valid(rt,l,r,x,y,val)) return -1;if (l==r){return l;}int mid = l+r >> 1;push_down(rt,l,r);int res = last_valid(rt<<1|1,mid+1,r,x,y,val);if (res!=-1){return res;}return last_valid(rt<<1,l,mid,x,y,val);}
};void solve(){int n,m,q;cin >> n >> m >> q;vector<int> R(m+1);vector<ll> V(m+1);for (int i=1;i<=m;i++){cin >> R[i] >> V[i];}vector<int> p(m+2,-1);stack<int> stk;vector<vector<int>> adj(m+2);for (int i=1;i<=m;i++){while (!stk.empty() && V[i]>=V[stk.top()]){stk.pop();}p[i] = stk.empty()?-1:stk.top();stk.push(i);}for (int i=1;i<=m;i++){if (p[i]!=-1){adj[p[i]].push_back(i);}}vector<int> sz(m+1),depth(m+1),dfn(m+1),top(m+1),ref(m+1),son(m+1);function<void(int)> dfs = [&](int u){sz[u] = 1;int pos = -1;int mx = 0;for (auto& v:adj[u]){depth[v] = depth[u]+1;dfs(v);sz[u] += sz[v];if (sz[v]>mx){mx = sz[v];pos = v;} }son[u] = pos;};for (int i=1;i<=m;i++){if (p[i]==-1){dfs(i);}}int timer = 1;function<void(int,int)> dfs2 = [&](int u,int head){dfn[u] = timer++;ref[dfn[u]] = u;top[u] = head;if (son[u]!=-1){dfs2(son[u],head);} for (auto& v:adj[u]){if (v!=son[u]){dfs2(v,v);}}};for (int i=1;i<=m;i++){if (p[i]==-1){dfs2(i,i);}}segmentTree sg(m);vector<ll> b(m+1);for (int i=1;i<=m;i++){b[dfn[i]] = R[i]; }sg.build(b);ll fres = 0;while (q--){int l,r;cin >> l >> r;vector<int> wait;int cur = r;while (1){wait.push_back(cur);if (top[cur]>l){if (p[top[cur]]==-1 || p[top[cur]]<l){cur = top[cur];break;}cur = p[top[cur]];}else{int left = dfn[top[cur]];int right = dfn[cur];while (left<=right){int mid = left+right>>1;if (ref[mid]>=l){right = mid-1;}else{left = mid+1;}}cur = ref[left];break;}}int curR = R[cur];ll res = V[cur]*R[cur];reverse(wait.begin(),wait.end());for (auto& v:wait){while (1){int t = depth[cur]>depth[top[v]]?cur:top[v];int left = dfn[t];int right = dfn[v];int temp = sg.first_valid(left,right,curR);if (temp!=-1){int u = ref[temp];res += V[u]*(R[u]-curR);curR = R[u];cur = u; } else break; }} fres^=res;} cout << fres << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--) solve();return 0;
}