题目链接：https://ac.nowcoder.com/acm/contest/11215/H

（一）预备知识：

（1）upper_bound( begin,end,num)：
    从数组的begin位置到end-1位置二分查找
    第一个大于num的数字，找到返回该数字的地址，
    不存在则返回end。通过返回的地址减去起始地址begin,
    得到找到数字在数组中的下标。
    lower_bound是找不小于，可能等于也可能大于。

（2）map的用法

https://blog.csdn.net/sevenjoin/article/details/81943864

（3）vector

构建邻接表

vector<int>pos[N];

我理解的是，表示一个动态的二维数组，pos【N】类似于C语言的指针数组。

（二）解题思路 参考链接：https://ac.nowcoder.com/discuss/750372?type=101&order=0&pos=2&page=1&channel=-1&source_id=1

 

 

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
map<pair<int,int>,int>ma;
vector<int>pos[200005];//邻接表 
char s[200005];
int xx[200005],yy[200005];
int main()
{
    int n,m,tot=0,x=0,y=0;
    cin>>n>>m;
    scanf("%s",s+1);
    ma[{0,0}]=++tot;
    pos[tot].push_back(0);
    for(int i=1;i<=n;i++){
        if(s[i]=='U') y++;
        if(s[i]=='D') y--;
        if(s[i]=='L') x--;
        if(s[i]=='R') x++;
        if(!ma[{x,y}]) ma[{x,y}]=++tot;
        int p=ma[{x,y}];
        pos[p].push_back(i);
        xx[i]=x,yy[i]=y;
    }
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        l--;
        int p=ma[{xx[l],yy[l]}];
        int st=upper_bound(pos[p].begin(),pos[p].end(),l)-pos[p].begin();//大于l的第一个数字，起始在l的位置不计入 
        int ed=upper_bound(pos[p].begin(),pos[p].end(),r)-pos[p].begin();//大于r 
        cout<<ed-st<<endl;//计算[l,r]操作中经过相对起点l对应的坐标的次数 ed-1-st+1=ed-st 
     
    }
    return 0;
}