SOURCE：P9019
这个题当T2多少还是有点过分的，我觉得当T3差不多（但是洛谷给了个蓝色）。
第一问很简单：我们定义表示从第个传送门出发，向左，向右步最多能跳到哪，显然可以倍增。
第二问的话，考虑我们知道答案的情况下，那么从起点向左跳步，从起点向右跳步是一定不会相遇的，只有从起点向左跳步，从起点向右跳步，才会相遇，也就是区间有交集。
定义表示区间内有多少个免费传送门，那么第二问的答案就是：
而显然可以拆分成，我们就可以定义表示从向左跳步所到达的位置的的和，来解决问题。
#include<cstdio>
#include<cstring>
#define N 200005
using namespace std;
int n,q,now,cnt,ans1,ans2,l[N],r[N],sum[N],f[N<<1][18],g[N<<1][18],fs[N<<1][18],gs[N<<1][18];
char s[N<<1],vs[N];
int dis(int x,int y)
{
if (x==y) return 0;
int res=0;
for (int i=17;i>=0;--i)
if (f[x][i]!=-1&&f[x][i]<y) res+=(1<<i),x=f[x][i];
return res+1;
}
int main()
{
scanf("%d%d",&n,&q);
scanf("%s",s+1);
cnt=0;now=1;
for (int i=1;i<=2*n;++i)
{
if (s[i]=='L') cnt++;
else r[now]=cnt,now++;
}
cnt=n+1;now=n;
for (int i=2*n;i;--i)
{
if (s[i]=='R') cnt--;
else l[now]=cnt,now--;
}
scanf("%s",vs+1);
for (int i=1;i<=n;++i)
sum[i]=sum[i-1]+vs[i]-'0';
memset(f,-1,sizeof(f));
memset(g,-1,sizeof(g));
for (int i=1;i<n;++i)
f[i][0]=r[i],fs[i][0]=sum[r[i]];
for (int i=n;i>1;--i)
g[i][0]=l[i],gs[i][0]=sum[l[i]-1];
for (int j=1;j<=17;++j)
for (int i=1;i<n;++i)
{
if (f[i][j-1]==-1) continue;
f[i][j]=f[f[i][j-1]][j-1];
if (f[i][j]!=-1) fs[i][j]=fs[i][j-1]+fs[f[i][j-1]][j-1];
}
for (int j=1;j<=17;++j)
for (int i=n;i>1;--i)
{
if (g[i][j-1]==-1) continue;
g[i][j]=g[g[i][j-1]][j-1];
if (g[i][j]!=-1) gs[i][j]=gs[i][j-1]+gs[g[i][j-1]][j-1];
}
while (q--)
{
int x,y;
scanf("%d%d",&x,&y);
ans1=dis(x,y);ans2=vs[x]-'0'+vs[y]-'0';
for (int i=17;i>=0;--i)
if ((ans1-1)&(1<<i)) ans2+=fs[x][i],x=f[x][i];
for (int i=17;i>=0;--i)
if ((ans1-1)&(1<<i)) ans2-=gs[y][i],y=g[y][i];
printf("%d %d\n",ans1,ans2);
}
return 0;
}