显然，对于给定的 \(l,r\)，最短路可以贪心求出，即每次走与当前区间相交且左端点最大的区间，这个可以用倍增加速。
定义 \(f_{i,j}\) 表示从区间 \(i\) 往右走 \(j\) 步后到达的区间，\(g_{i,j}\) 表示往左走的情况。
正反遍历一下即可求出 \(f_{i,1}\) 和 \(g_{i,1}\)。
对于第二问，第 \(i\) 步所能走到的区间会有一个范围，且对于每个 \(i\) 其范围不相交。
定义 \(s(i,j)\) 表示编号在 \([i,j]\) 范围内的特殊区间个数。
那么最终答案为 \(s(x,x)+s(y,y)+\sum\limits_{i=1}^{dis-1}s(g_{y,dis-i},f_{x,i})\)。
求倍增和的前缀和即可。复杂度 \(O(n\log n)\)。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,f[N][21],g[N][21],fs[N][21],gs[N][21],id[N*2],sum[N];
char c[N*2];
string s;
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>q;
int t=0,t2=0;
for(int i=1;i<=2*n;++i){
cin>>c[i];
if(c[i]=='L')id[i]=++t;
else id[i]=++t2;
}
cin>>s;s="."+s;
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+s[i]-'0';
for(int i=2*n;i>=1;--i){
if(c[i]=='L'){
g[id[i]][0]=id[t];
gs[id[i]][0]=sum[id[t]-1];
}else t=i;
}
for(int i=1;i<=2*n;++i){
if(c[i]=='R'){
f[id[i]][0]=id[t];
fs[id[i]][0]=sum[id[t]];
}else t=i;
}
for(int j=1;j<=20;++j)for(int i=1;i<=n;++i){
f[i][j]=f[f[i][j-1]][j-1];fs[i][j]=fs[i][j-1]+fs[f[i][j-1]][j-1];
g[i][j]=g[g[i][j-1]][j-1];gs[i][j]=gs[i][j-1]+gs[g[i][j-1]][j-1];
}
while(q--){
int x,y,d1=0,d2;cin>>x>>y;
d2=s[x]-'0'+s[y]-'0';
int u=x,v;
for(int i=20;i>=0;--i){
if(f[u][i]<y){
d1+=(1<<i);
u=f[u][i];
}
}
++d1;
cout<<d1<<" ";
u=x;v=y;
for(int i=0;i<=20;++i){
if((d1-1)&(1<<i)){
d2+=fs[u][i]-gs[v][i];
u=f[u][i];v=g[v][i];
}
}
cout<<d2<<endl;
}
return 0;
}