Znzryb's Blog
0%

Posted on Edited on

AC代码

AC

相比于上一次WA，修改了这些（这没啥好多说的，idx2为-会导致一系列问题）

1
2
if(idx2<0)
       idx2=0;

以及加了一个n+1（原来是n）（一般情况下不会被击穿因为如果超了我会减掉，但正巧空的默认值是0，即
xp[idx2].first）为0，正好我的判断条件是xp[idx2].first!=r，碰巧hack数据r也为0，就被击穿了，idx2没减，让我的程序WA了。

1
2
3
for(int i=1;i<=n+1;i++) {
        sumVil[i]=sumVil[i-1]+xp[i].second;
}

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=2e5+10,MAXP=1e11+10;
pair<ll,ll> xp[N];
ll n,m,sumVil[N];
void debug() {
    for(int i=1;i<=n;i++) {
        cout<<sumVil[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<xp[i].first<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<xp[i].second<<" ";
    }
    cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>xp[i].first;
    }
    for(int i=1;i<=n;i++) {
        cin>>xp[i].second;
    }
    sort(&xp[1],&xp[n+1]);
    for(int i=1;i<=n+1;i++) {
        sumVil[i]=sumVil[i-1]+xp[i].second;
    }
    cin>>m;
    for(int _=1;_<=m;_++) {
        ll l,r;
        cin>>l>>r;
        ll idx1=lower_bound(&xp[0],&xp[n+1],make_pair(l,-MAXP))-&xp[0]-1;
        ll idx2=upper_bound(&xp[0],&xp[n+1],make_pair(r, MAXP))-&xp[0];
        if(idx1<0)
            idx1=0;
        if(xp[idx2].first!=r)
            idx2--;
        if(idx2<0)
            idx2=0;
        // cout<<idx1<<" "<<idx2<<": ";
        cout<<sumVil[idx2]-sumVil[idx1]<<endl;
    }
    // debug();
    return 0;
}
// 就WA了一个 https://atcoder.jp/contests/abc371/submissions/59255550

心路历程（WA，TLE，MLE……）

挺神奇的，就WA了一个点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <algorithm>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=2e5+10,MAXP=1e11+10;
pair<ll,ll> xp[N];
ll n,m,sumVil[N];
// bool comp(pair<ll,ll> a, pair<ll,ll> b) {
//     if(a.first!=b.first)
//         return a.first<b.first;
//     return false;
// }
// struct cmp {
//     bool operator()(const pair<ll,ll> &a ,const pair<ll,ll> &b) const{
//         return a.first<b.first;
//     }
// };
void debug() {
    for(int i=1;i<=n;i++) {
        cout<<sumVil[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<xp[i].first<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<xp[i].second<<" ";
    }
    cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>xp[i].first;
    }
    for(int i=1;i<=n;i++) {
        cin>>xp[i].second;
    }
    sort(&xp[1],&xp[n+1]);
    for(int i=1;i<=n;i++) {
        sumVil[i]=sumVil[i-1]+xp[i].second;
    }
    cin>>m;
    for(int _=1;_<=m;_++) {
        ll l,r;
        cin>>l>>r;
        ll idx1=lower_bound(&xp[0],&xp[n+1],make_pair(l,-MAXP))-&xp[0]-1;
        ll idx2=upper_bound(&xp[0],&xp[n+1],make_pair(r, MAXP))-&xp[0];
        if(idx1<0)
            idx1=0;
        if(xp[idx2].first!=r)
            idx2--;
        //cout<<idx1<<" "<<idx2<<": ";
        cout<<sumVil[idx2]-sumVil[idx1]<<endl;
    }
    //debug();
    return 0;
}
// 就WA了一个 https://atcoder.jp/contests/abc371/submissions/59255550

Posted on Edited on

AC代码

这题面说起来也简单，就是P1=5 那我就用P5代替你———同理 所有的Pi都要进行这个操作

题意很简单，就是操作数很大，不可能模拟。

那我们的问题就变成了这个变化有什么规律吗？

image

一个非常详细的题解

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,p[N],k,ans[N],cnt,ring[N],d[N];
bool vis[N];
vector<ll> g[N];
void dfs(ll i,ll dis) {
    if(vis[i]) {
        return;
    }
    vis[i]=true;
    g[cnt].push_back(i);
    ring[i]=cnt,d[i]=dis;
    dfs(p[i],dis+1);
}
ll binpow(ll a,ll b,ll p) {
    if(b==0) return 1;
    ll res=binpow(a,b/2,p)%p;
    if(b%2)  // b%2!=0
        return res%p*res%p*a%p; // 毕竟res是
    else
        return res%p*res%p;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>p[i];
        if(p[i]==i)
            ans[i]=i;
    }
    for(int i=1;i<=n;i++) {
        if(ans[i]!=0)   // 这相当于一个自环，倒也不用走
            continue;
        if(vis[i])      // 走过了，不用处理
            continue;
        cnt++;
        dfs(i,0);
    }
    // 答案解决阶段
    for(int i=1;i<=n;i++) {
        if(ans[i]!=0)   // 答案都确定了也就无所谓了
            continue;
        ll ringSize=g[ring[i]].size();
        ll advStep=binpow(2,k,ringSize);
        ans[i]=g[ring[i]][(d[i]+advStep)%ringSize];
    }
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}
// AC https://atcoder.jp/contests/abc377/submissions/59254380

心路历程（WA，TLE，MLE……）

挺难想的，实现起来其实也比较难，还需要快速幂，但确实是一次提交AC，只能说我的图论代码实现水平还是比较高的

Posted on Edited on

题目大意

给定 nn 条线段 [Li,Ri][L_i, R_i]，线段端点都在 1∼m1\sim m 的范围内。需要统计满足题意的区间数量（等价于对每个左端点 ll，能延伸到的最大右端点受右侧最小的 RR 约束），并输出总数。

AC代码

主要思路是一个点所能到达的最大边界取决于它的minR，也即在它右边的最小右边界

可以看到minR的统计过程是这样的

1
2
3
4
5
6
7
8
9
10
11
for(int _=1;_<=n;_++) {
        ll l,r;
        cin>>l>>r;
        minR[l]=min(minR[l],r);     // 其实包括l之前所有的点，minR的值应该设为r（min（ r ，现有值））
                                        // 但如果直接这样设，时间复杂度会来到O（n^2）级别，显然无法通过全部数据
    }                                   // 那我们为什么不先设一个l，在最后来一个汇总，反正也不要求强制在线。
    ll currMin=m+1;
    for(int i=m;i>=1;--i) {             // 汇总
        currMin=min(currMin,minR[i]);
        minR[i]=currMin;
    }

可以证明在 【Li,Ri】，比Li还小的地方 l（包含Li）的【l，r】区间包含Ri，必然导致【l，r】包含【Li，Ri】

所以比Li更小的地方应该将Ri考虑在minR的取值中

比如说minR[1]==4 他的答案怎么统计那？

1
2
3
4
5
1 2 3

1 2

1

可以看到一共有三种区间（[1,3],[1,2],[1,1]）即区间长度之和即为答案（[1,4]）

然后还有一些离线化的优化方法，注释里写的很清楚

AC 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,m,cnt,minR[N],ans;    // minR代表该点l对应的最小R

void debug() {
    for(int i=1;i<=m;++i) {
        cout<<minR[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {             // 初始化minR
        minR[i]=m+1;
    }
    for(int _=1;_<=n;_++) {
        ll l,r;
        cin>>l>>r;
        minR[l]=min(minR[l],r);     // 其实包括l之前所有的点，minR的值应该设为r（min（ r ，现有值））
                                        // 但如果直接这样设，时间复杂度会来到O（n^2）级别，显然无法通过全部数据
    }                                   // 那我们为什么不先设一个l，在最后来一个汇总，反正也不要求强制在线。
    ll currMin=m+1;
    for(int i=m;i>=1;--i) {             // 汇总
        currMin=min(currMin,minR[i]);
        minR[i]=currMin;
    }
    ans=0;
    for(int i=1;i<=m;++i) {
        ans+=minR[i]-i;           // 答案统计
    }
    cout<<ans<<endl;
    // debug();
}
// AC https://atcoder.jp/contests/abc377/submissions/59206219

心路历程（WA，TLE，MLE……）

一次提交过的，之前的代码样例都过不了就不放在这里了

Posted on Edited on

题目大意

给定多个 nn，要求输出满足某种异或性质的最小的 2k2^k（或按题意构造出的答案）。本题可通过打表/找规律解决，并需要对小值（如 n=1,2n=1,2）特判。

AC代码

打表题

注意特判一下1 and 2

其他的没什么好多说的

其实下次这种题目建议写一个对拍程序

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll T,n,a=1e18;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n;
        if(n==1 || n==2) {
            cout<<1<<endl;
            continue;
        }
        ll ans=1;
        while(true) {
            ans*=2;
            if(ans>=n) {
                cout<<ans<<endl;
                break;
            }
        }
    }
    return 0;
}

心路历程（WA，TLE，MLE……）

哈哈，没特判2

Posted on Edited on

题目大意

有一个环形的 nn 个点（编号 1simn1sim n），两只手初始在固定位置。给出 mm 次操作，每次要求移动某一只手到指定点，移动代价为沿环走的最短步数，同时两只手不能占用同一个点（或有重叠限制）。求完成所有操作的最小总代价。

AC代码

其实与B题的唯一不同点就是你可以动另一只手。

这题让我想起来天津省选的线段

https://www.luogu.com.cn/problem/P3842

AC记录

这个线段就是你要忽略一些其实没有意义的情况，这道题应该也是一样，你不必把两只手在哪个点都存下来，因为后走和前走是一样的

注意防重叠条件的书写

就是我之前写if(pos≠j) 但实际上j有可能代表副手，也有可能代表主手，如果代表副手就有问题了，pos就是移动副手，副手不应该和副手重叠？搞笑

其实可以在cal函数中写这个逻辑，但因为这个cal函数是从B题拉过来的，我就懒得改了

分享一组hack数据

1
2
3
4
5
6
7
8
8 7
L 2
L 3
L 4
L 5
L 6
L 7
L 8

应输出

1
14

AC https://atcoder.jp/contests/abc376/submissions/59140626

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,m,dp[N][N],object;
char oper;
void debug() {
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++)
            cout<<dp[i][j]<<" ";
        cout<<endl;
    }
}
ll cal(char op,ll L,ll R,ll obj) {  // 计算并返回需要走几步
    ll res=0;
    if(op=='L') {
        ll zhenMove=abs(L-obj);
        ll fanMove=n-zhenMove;
        if(obj<L) {
            if(R<L && R>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(R>L && R<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }else {
        ll zhenMove=abs(R-obj);
        ll fanMove=n-zhenMove;
        if(obj<R) {
            if(L<R && L>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(L>R && L<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int opup=0;
    memset(dp,0x3f,sizeof(dp));
    ll inf = dp[0][0];
    dp[0][2]=0;                // 此时r在2
    ll opupObj=1;             // 假装有一个0号命令 让L走到 1
    for(int i=1;i<=m;i++) {
        cin>>oper>>object;
        int op= oper=='L'? 0:1;
        for(int j=1;j<=n;j++) {
            if(dp[i-1][j]==inf)
                continue;

            if(op==opup && op==0) {     // 此时 j 即为right手 opuploc 即为 left   dp里应该存的仍然是r手
                // r手可自由移动
                ll l=opupObj,r=j;
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                if(pos!=l)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=l)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }else if(op==opup && op==1) {
                // l手可自由移动
                ll l=j,r=opupObj;
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                if(pos!=r)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=r)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==1 && opup==0) {
                ll l=opupObj,r=j;           // 可以随便动的手是left 要动的手是right
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                if(pos!=r)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=r)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==0 && opup==1) {
                ll l=j,r=opupObj;           // 可以随便动的手是right 要动的手是left
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                if(pos!=l)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=l)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }
        }
        opup=op;opupObj=object;
    }
    ll ans=inf;
    for(int i=1;i<=n;i++) {
        ans=min(ans,dp[m][i]);
    }

    cout<<ans<<endl;
    // debug();
}
// AC https://atcoder.jp/contests/abc376/submissions/59140626

心路历程（WA，TLE，MLE……）

WA了13个点

https://atcoder.jp/contests/abc376/submissions/59134285

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,m,dp[N][N],object;
char oper;
void debug() {
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++)
            cout<<dp[i][j]<<" ";
        cout<<endl;
    }
}
ll cal(char op,ll L,ll R,ll obj) {  // 计算并返回需要走几步
    ll res=0;
    if(op=='L') {
        ll zhenMove=abs(L-obj);
        ll fanMove=n-zhenMove;
        if(obj<L) {
            if(R<L && R>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(R>L && R<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }else {
        ll zhenMove=abs(R-obj);
        ll fanMove=n-zhenMove;
        if(obj<R) {
            if(L<R && L>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(L>R && L<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int opup=0;
    memset(dp,0x3f,sizeof(dp));
    ll inf = dp[0][0];
    dp[0][2]=0;                // 此时r在2
    ll opupObj=1;             // 假装有一个0号命令 让L走到 1
    for(int i=1;i<=m;i++) {
        cin>>oper>>object;
        int op= oper=='L'? 0:1;
        for(int j=1;j<=n;j++) {
            if(dp[i-1][j]==inf)
                continue;

            if(op==opup && op==0) {     // 此时 j 即为right手 opuploc 即为 left   dp里应该存的仍然是r手
                // r手可自由移动
                ll l=opupObj,r=j;
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }else if(op==opup && op==1) {
                // l手可自由移动
                ll l=j,r=opupObj;
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==1 && opup==0) {
                ll l=opupObj,r=j;           // 可以随便动的手是left 要动的手是right
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==0 && opup==1) {
                ll l=j,r=opupObj;           // 可以随便动的手是right 要动的手是left
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }
        }
        opup=op;opupObj=object;
    }
    ll ans=inf;
    for(int i=1;i<=n;i++) {
        ans=min(ans,dp[m][i]);
    }

    cout<<ans<<endl;
    //debug();
}

WA了9个点，解决了一些特殊情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,m,dp[N][N],object;
char oper;
void debug() {
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++)
            cout<<dp[i][j]<<" ";
        cout<<endl;
    }
}
ll cal(char op,ll L,ll R,ll obj) {  // 计算并返回需要走几步
    ll res=0;
    if(op=='L') {
        ll zhenMove=abs(L-obj);
        ll fanMove=n-zhenMove;
        if(obj<L) {
            if(R<L && R>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(R>L && R<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }else {
        ll zhenMove=abs(R-obj);
        ll fanMove=n-zhenMove;
        if(obj<R) {
            if(L<R && L>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(L>R && L<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int opup=0;
    memset(dp,0x3f,sizeof(dp));
    ll inf = dp[0][0];
    dp[0][2]=0;                // 此时r在2
    ll opupObj=1;             // 假装有一个0号命令 让L走到 1
    for(int i=1;i<=m;i++) {
        cin>>oper>>object;
        int op= oper=='L'? 0:1;
        for(int j=1;j<=n;j++) {
            if(dp[i-1][j]==inf)
                continue;

            if(op==opup && op==0) {     // 此时 j 即为right手 opuploc 即为 left   dp里应该存的仍然是r手
                // r手可自由移动
                ll l=opupObj,r=j;
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }else if(op==opup && op==1) {
                // l手可自由移动
                ll l=j,r=opupObj;
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==1 && opup==0) {
                ll l=opupObj,r=j;           // 可以随便动的手是left 要动的手是right
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==0 && opup==1) {
                ll l=j,r=opupObj;           // 可以随便动的手是right 要动的手是left
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }
        }
        opup=op;opupObj=object;
    }
    ll ans=inf;
    for(int i=1;i<=n;i++) {
        ans=min(ans,dp[m][i]);
    }

    cout<<ans<<endl;
    //debug();
}