传送门
Solution:
我们考虑把所有能够互相翻到的牌归到一个集合里去 ，不难想到可以用并查集来维护这些集合。由于前面的骨牌可能太长以至于影响后面骨牌的统计答案，所以我们要离线询问，从后往前做。
并且再维护一个单调栈，用来存并查集的祖先们。
维护后缀和（即到达终点的所需花费）这样的话 对于询问[l,r] 我们就可以用l的后缀和减去r的后缀和从而得到答案
#include<bits/stdc++.h> #define N 200005 using namespace std; int n,m,father[N],fwl[N],fwr[N],sum[N],ans[N],ql[N],qr[N]; struct data { int l,r; }node[N]; vector <int> ask[N]; stack <int> sta; inline int getfather(int x) { if(father[x]==x) return x; father[x]=getfather(father[x]); return father[x]; } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n; for(int i=1;i<=n;i++) { cin>>node[i].l; cin>>node[i].r; node[i].r+=node[i].l; father[i]=i; } cin>>m; for(int i=1;i<=m;i++) { cin>>ql[i]>>qr[i]; ask[ql[i]].push_back(i); } //栈来存并查集的祖先们 for(int i=n;i>=1;i--) { fwl[i]=node[i].l,fwr[i]=node[i].r; while(!sta.empty()&&fwr[i]>=fwl[sta.top()])//能覆盖 { fwr[i]=max(fwr[i],fwr[sta.top()]); father[getfather(sta.top())]=i;//统一到一个并查集里去 sta.pop(); } if(!sta.empty()) { sum[i]=sum[sta.top()]+fwl[sta.top()]-fwr[i]; } else sum[i]=0; sta.push(i); for(int j=0;j<ask[i].size();j++) { int id=ask[i][j]; int a=qr[id]; ans[id]=sum[i]-sum[getfather(a)]; } } for(int i=1;i<=m;i++) cout<<ans[i]<<endl; return 0; }