noip2021 训练2(USACO)

发表于 更新于 分类于 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 6 分钟

Link

[USACO10MAR] Great Cow Gathering G

换根 dp 板子

先用树形 dp 求出以 11 为根的最小不方便值，然后 bfs 向儿子换根

fv=fu+(sizu−sizv×2)×wf_v=f_u + (siz_u - siz_v \times 2) \times w

这个手推一下就好了，大概就是把两边子树中的点经过 (u,v)(u,v) 这条边的代价算一下。

Code 
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
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 5;
int n, c[N];
struct edge
{
    int v, w, nxt;
}e[N << 1];
int head[N], tot;

void add(int u, int v, int w)
{
    e[++tot] = (edge) {v, w, head[u]};
    head[u] = tot;
}

ll f[N], siz[N], ans;

void dfs(int u, int fa)
{
    siz[u] = c[u];
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
        f[u] += f[v] + siz[v] * e[i].w;
    }
    return;
}

queue <int> que;
bool vis[N];

void bfs()
{
    ans = 1e18;
    que.push(1);
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        ans = min(ans, f[u]);
        for(int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            f[v] = f[u] + (siz[u] - siz[v] * 2) * e[i].w;
            siz[v] = siz[u];
            que.push(v);
        }
    }
    return;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for(int i = 1, u, v, w; i < n; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }
    dfs(1, 0);
    bfs();
    printf("%lld\n", ans);
    return 0;
}

[USACO09FEB] Stock Market G

CSP-J2019 T3 原题

感觉思路还是比较难的，虽然代码难度极低

要求最终能获得的最大钱数，其实可以分别对每一天，求当天能获得的最大钱数。

对于每个物品在每天，有三种情况：

  1. 不买
  2. 今天买，明天卖
  3. 今天买，过几天卖

其实第三种可以通过第二种实现

今天买了，明天卖掉，然后明天再买，后天卖掉…

就相当于今天买了，过几天再卖。

所以就两种情况，然后就是一个完全背包了

设 fif_i 表示手上有 ii 元钱时最大收益，注意总钱数要每天更新。

Code 
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
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 5;
int n, m, s, p[55][15];
int f[MAXN];

int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &p[i][j]);
    for(int j = 2; j <= m; j++)
    {
        int mx = 0;
        memset(f, 0, sizeof(f));
        for(int i = 1; i <= n; i++)
        {
            for(int k = p[i][j - 1]; k <= s; k++)
            {
                f[k] = max(f[k], f[k - p[i][j - 1]] + p[i][j] - p[i][j - 1]);
                mx = max(mx, f[k]);
            }
        }
        s += mx;
    }
    printf("%d\n", s);
    return 0;
}

USACO13MAR Necklace G

这里用的 AC自动机，也可以用 kmp，但如果有多个不能出现的子串就不行了。

正难则反，求出最多能保留多少，然后减一下就行了

先建出 AC自动机，在上面 dp

设 fi,jf_{i,j} 表示在第 ii 个位置，在 AC自动机上走到了 jj 时最多能保留多长

如果 jj 不是子串的末尾，fi,j=max(fi,j,fi−1,j)f_{i,j}=max(f_{i,j},f_{i-1,j})

令 k=triej,aik=trie_{j,a_i}，也就是在 AC自动机上从 jj 向后沿着 aia_i 走到哪个点。

如果 kk 不是子串的末尾，fi,k=max(fi,k,fi−1,j+1)f_{i,k}=max(f_{i,k},f_{i-1,j}+1)

Code 
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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 5;
char a[N], b[N];
int n, m, nxt[N];
int trie[N][30], tot, ed;
int fail[N];
int f[N][1010];

void insert(char s[])
{
    int len = strlen(s + 1), x = 0;
    for(int i = 1; i <= len; i++)
    {
        int c = s[i] - 'a';
        if(!trie[x][c]) trie[x][c] = ++tot;
        x = trie[x][c];
    }
    ed = x;
    return;
}

void build()
{
    queue <int> que;
    for(int i = 0; i < 26; i++)
        if(trie[0][i]) que.push(trie[0][i]);
    while(!que.empty())
    {
        int x = que.front();
        que.pop();
        for(int i = 0; i < 26; i++)
            if(trie[x][i]) fail[trie[x][i]] = trie[fail[x]][i], que.push(trie[x][i]);
            else trie[x][i] = trie[fail[x]][i];
    }
    return;
}

int main()
{
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1), m = strlen(b + 1);
    insert(b), build();
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
        {
            if(j != ed) f[i][j] = max(f[i][j], f[i - 1][j]);
            int k = trie[j][a[i] - 'a'];
            if(k != ed) f[i][k] = max(f[i][k], f[i - 1][j] + 1);
        }
    int ans = 0;
    for(int i = 0; i <= m; i++)
        ans = max(ans, f[n][i]);
    printf("%d\n", n - ans);
    return 0;
}

USACO12DEC Running Away From the Barn G

神奇的树上差分

因为只求子树内的，所以第 ii 个点的贡献只在这个点到根的链上

所以预处理每个点的深度，然后对每个点向上倍增找到最高的能产生贡献的点，链上都要 +1+1，做个差分即可。

COde 
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
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 5;
int n, m;
int f[N][25], dep[N];
int val[N];

int Find(int x)
{
    int d = dep[x];
    for(int i = 20; i >= 0; i--)
        if(d - dep[f[x][i]] <= m)
            x = f[x][i];
    return f[x][0];
}

signed main()
{
    scanf("%lld%lld", &n, &m);
    for(int i = 2; i <= n; i++)
    {
        int w;
        scanf("%lld%lld", &f[i][0], &w);
        dep[i] = dep[f[i][0]] + w;
        for(int j = 1; j <= 20; j++)
            f[i][j] = f[f[i][j - 1]][j - 1];
    }
    for(int i = n; i >= 1; i--)
    {
        int x = Find(i);
        val[x]--, val[i]++;
    }
    for(int i = n; i >= 1; i--)
        val[f[i][0]] += val[i];
    for(int i = 1; i <= n; i++)
        printf("%lld\n", val[i]);
    return 0;
}

USACO18FEB Snow Boots G

见 noip2021训练1 最后一题

USACO12FEB Nearby Cows G

非常的套路

分别求出每个点子树内的答案和子树外的答案，求和即可。

在求子树外的时候细节还是比较多

初始化数组不要 memset()，那样复杂度就变成 O(n2)O(n^2) 了，需要用多少就初始化多少。

Code 
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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 1e5 + 5;
int n, m, c[N];
vector <int> G[N];
int f[N][25], g[N][25], pre[25], suf[N][25];

void dfs1(int u, int fa)
{
    for(int i = 0; i <= m; i++)
        f[u][i] = c[u];
    for(auto v : G[u])
    {
        if(v == fa) continue;
        dfs1(v, u);
        for(int i = 1; i <= m; i++)
            f[u][i] += f[v][i - 1];
    }
    return;
}

void dfs2(int u, int fa)
{
    vector <int> ch;
    for(auto v : G[u])
        if(v != fa) ch.pb(v);
    
    memset(pre, 0, sizeof(pre));
    for(int i = 0; i <= (int)ch.size(); i++)
        for(int j = 0; j <= m; j++)
            suf[i][j] = 0;

    for(int i = (int)ch.size() - 1; i >= 0; i--)
    {
        int v = ch[i];
        for(int j = 0; j <= m; j++)
            suf[i][j] = suf[i + 1][j] + f[v][j];
        for(int j = 1; j <= m; j++)
            g[v][j] = c[u];
    }

    for(int i = 0; i < (int)ch.size(); i++)
    {
        int v = ch[i];
        for(int j = 2; j <= m; j++)
            g[v][j] += pre[j - 2] + suf[i + 1][j - 2] + g[u][j - 1];
        for(int j = 0; j <= m; j++)
            pre[j] += f[v][j];
    }

    for(auto v : ch) dfs2(v, u);
    return;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1, u, v; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        G[u].pb(v), G[v].pb(u);
    }
    for(int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    dfs1(1, 0);
    dfs2(1, 0);
    for(int i = 1; i <= n; i++)
        printf("%d\n", f[i][m] + g[i][m]);
    return 0;
}

USACO05DEC Layout G

差分约束板子题

disx−disy≤wdisx≤disy+wadd(y,x,w)dis_x-dis_y\le w\qquad dis_x\le dis_y+w\qquad add(y,x,w)

disx−disy≥wdisy≤disx−wadd(x,y,−w)dis_x-dis_y\ge w\qquad dis_y\le dis_x-w\qquad add(x,y,-w)

有负环无解，disn=infdis_n=inf 可以无穷远

（很久以前的代码了）

Code 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 1010
#define M 21010
#define INF 0x3f3f3f3f

using namespace std;

int n,ml,md;
struct edge
{
	int v,w,nxt;
}e[M];
int tot,head[N];

void add(int a,int b,int d)
{
	e[++tot]=(edge){b,d,head[a]};
	head[a]=tot;
}

int dis[N],vis[N],cnt[N];

void spfa(int S)
{
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	for(int i=0; i<=n; i++)
		dis[i]=(i==S)?0:INF;
	queue<int>que;
	vis[S]=1;
	que.push(S);
	while(!que.empty())
	{
		int u=que.front();
		que.pop();
		vis[u]=0;
		if((++cnt[u])>=n)
		{
			printf("-1\n");
			exit(0);
		}
		for(int i=head[u]; i; i=e[i].nxt)
		{
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w)
			{
				dis[v]=dis[u]+e[i].w;
				if(!vis[v])
				{
					que.push(v);
					vis[v]=1;
				}
			}
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&ml,&md);
	for(int i=1; i<=ml; i++)
	{
		int a,b,d;
		scanf("%d%d%d",&a,&b,&d);
		add(a,b,d);
	}
	for(int i=1; i<=md; i++)
	{
		int a,b,d;
		scanf("%d%d%d",&a,&b,&d);
		add(b,a,-d);
	}
	for(int i=1; i<=n; i++)
		add(0,i,0);
	spfa(0);
	spfa(1);
	if(dis[n]==INF) printf("-2\n");
	else printf("%d\n",dis[n]);
	return 0;
}

USACO12OPEN Bookshelf G

考虑朴素 dp

设 fif_i 表示放了前 ii​ 本书，书架高度的最小值。

fi=min{fj−1+maxj≤k≤i{hk}} (∑p=jiwp≤L)f_i=min\{f_{j-1}+max_{j\le k\le i}\{h_k\}\}\ (\sum_{p=j}^iw_p\le L)

这样是 O(n2)O(n^2) 的，考虑优化。

因为我们要求区间最小值，不难想到用线段树维护，但是有些困难。

需要用线段树维护 ff 和 f+hf+h 的最小值，用 valval 存 ff 的最小值，mnmn 存 f+hf+h 的最小值。

对于每层书架，高度为最高的那本书，所以可以用单调栈处理出第 ii 本书在前面多少本书中是最高的。然后只需要区间修改。

注意 valival_i 的值应改为 fi−1f_{i-1}，原因见上面转移方程。

所以只需要区间修改、单点修改、区间查询。

在查询时的左端点可以用指针扫一遍，类似于单调队列。

Code 
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
121
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 5;
int n, m, h[N], w[N];
int stk[N], top;
ll f[N];

namespace seg
{
    #define INF 1e18
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)

    ll val[N << 2], mn[N << 2], tag[N << 2];

    void pushup(int rt)
    {
        val[rt] = min(val[ls], val[rs]);
        mn[rt] = min(mn[ls], mn[rs]);
    }

    void pushdown(int rt)
    {
        if(~tag[rt])
        {
            mn[ls] = val[ls] + tag[rt];
            mn[rs] = val[rs] + tag[rt];
            tag[ls] = tag[rs] = tag[rt];
            tag[rt] = -1;
        }
    }

    void build(int l, int r, int rt)
    {
        val[rt] = mn[rt] = INF;
        tag[rt] = -1;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, ls);
        build(mid + 1, r, rs);
        pushup(rt);
    }

    void init(int pos, int l, int r, int rt)
    {
        if(l == r)
        {
            val[rt] = f[l - 1], mn[rt] = INF;
            return;
        }
        pushdown(rt);
        int mid = (l + r) >> 1;
        if(pos <= mid) init(pos, l, mid, ls);
        else init(pos, mid + 1, r, rs);
        pushup(rt);
    }

    void update(int L, int R, ll h, int l, int r, int rt)
    {
        if(l > R || r < L) return;
        if(L <= l && r <= R)
        {
            mn[rt] = val[rt] + h;
            tag[rt] = h;
            return;
        }
        pushdown(rt);
        int mid = (l + r) >> 1;
        update(L, R, h, l, mid, ls);
        update(L, R, h, mid + 1, r, rs);
        pushup(rt);
    }

    ll query(int L, int R, int l, int r, int rt)
    {
        if(l > R || r < L) return INF;
        if(L <= l && r <= R) return mn[rt];
        pushdown(rt);
        int mid = (l + r) >> 1;
        return min(query(L, R, l, mid, ls), query(L, R, mid + 1, r, rs));
    }
}

template <typename T>
void read(T &x)
{
    x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return;
}

int main()
{
    read(n), read(m);

    seg::build(1, n, 1);

    ll sum = 0;
    stk[++top] = 1;
    for(int i = 1, l = 1; i <= n; i++)
    {
        read(h[i]), read(w[i]);

        seg::init(i, 1, n, 1);

        while(top && h[i] >= h[stk[top]]) top--;
        seg::update(stk[top] + 1, i, h[i], 1, n, 1);
        stk[++top] = i;

        sum += w[i];
        while(l < i && sum > m) sum -= w[l++];
        f[i] = seg::query(l, i, 1, n, 1);
    }
    printf("%lld\n", f[n]);

    return 0;
}

USACO08MAR Land Acquisition G

斜率优化板子题，暑假的时候学长讲过，但当时没写 qaq

我把 x,yx,y 分别当作长和宽

首先可以将被包含的矩形去掉，然后剩下的矩形 xx 递增，yy 递减

设 fif_i 表示前 ii 个矩形的最小代价

fi=min{fj−1+xi×yj} (1≤j≤i)f_i=min\{f_{j-1}+x_i\times y_j\}\ (1\le j \le i)

现在已经有了 O(n2)O(n^2) 的暴力 dp，考虑优化

比较显然的斜率优化，先将式子变形一下

fj−1=−xi×yi+fif_{j-1}=-x_i\times y_i+f_i

把 yiy_i 看作 xx，fj−1f_{j-1} 看作 yy，xix_i 看作 kk，fif_i 看作 bb

然后就得到了一次函数的基本形式 y=−k×x+by=-k\times x + b

kk 是已知的 xix_i 并且递增，现在就是要最小化截距。

要维护一个下凸包，将已知斜率的一次函数与下凸包相切，就是最小的截距了。

维护下凸包可以用单调队列维护一个斜率递增的区间，当队首的斜率小于 xix_i 时就已经没用了，因为后面的斜率递增，不可能再碰到队首了。

入队时只需要判断一下 队尾与队尾前一个点的斜率 和 (yi,fi−1)(y_i,f_{i-1}) 与队尾的斜率 哪个大。

这个画图模拟一下就很好理解了，大概就是一个在一次象限的下凸包和斜率为负的一函数。

注意斜率是负的。

Code 
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
#include <bits/stdc++.h>
#define ll long long
#define db double

using namespace std;

const int N = 5e4 + 5;
int n;
struct node
{
    ll x, y;
    friend bool operator < (node a, node b)
    {
        return a.y == b.y ? a.x > b.x : a.y > b.y;
    }
}a[N];
int cnt, l, r, q[N];
db k[N];
ll f[N];

db slope(int i, int j)
{
    return (db)(f[j - 1] - f[i - 1]) / (db)(a[i].y - a[j].y);
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i].x, &a[i].y);
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++)
        if(a[cnt].x < a[i].x) a[++cnt] = a[i];

    l = 1, r = 0;
    for(int i = 1; i <= cnt; i++)
    {
        while(l < r && k[r - 1] >= slope(q[r], i)) r--;
        k[r] = slope(q[r], i), q[++r] = i;
        while(l < r && k[l] <= a[i].x) l++;
        f[i] = f[q[l] - 1] + a[i].x * a[q[l]].y;
    }

    printf("%lld\n", f[cnt]);
    return 0;
}

USACO17FEB Why Did the Cow Cross the Road III G

看到这题第一反应就是树状数组，然后试了试，过了样例，写完就过了（？

其实就是求每个数两次出现的位置间有多少个数出现了一次。

用树状数组维护前缀和，如果 aa 是第一次出现，直接 +1+1，否则将答案加上两次出现位置中间的和。

其实就是中间出现了一次的数的个数。

Code 
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
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 5;
int n, a[N], pos[N];
ll c[N], ans;

void add(int x, int y)
{
    for(; x <= n; x += x & -x)
        c[x] += y;
}

ll qry(int x)
{
    ll res = 0;
    for(; x; x -= x & -x)
        res += c[x];
    return res;
}

int main()
{
    scanf("%d", &n);
    n <<= 1;
    for(int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        if(!pos[a]) add(i, 1), pos[a] = i;
        else add(pos[a], -1), ans += qry(i) - qry(pos[a]);
    }
    printf("%lld\n", ans);
    return 0;
}

USACO13JAN Seating G

比较套路的线段树题

维护区间最长连续 11 的个数

分别维护最左边，最右边最长的长度，然后合并一下。

在查询时先找左边，再找中间（将两边合并起来），最后找右边。

Code 
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
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;
int n, m, ans;

namespace seg
{
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)

    int mx[N << 2], lmx[N << 2], rmx[N << 2];
    int tag[N << 2], len[N << 2];

    void pushup(int rt)
    {
        lmx[rt] = lmx[ls];
        rmx[rt] = rmx[rs];

        if(lmx[rt] == len[ls]) lmx[rt] += lmx[rs];
        if(rmx[rt] == len[rs]) rmx[rt] += rmx[ls];

        mx[rt] = max(max(mx[ls], mx[rs]), rmx[ls] + lmx[rs]);
    }

    void build(int l, int r, int rt)
    {
        len[rt] = r - l + 1; 
        tag[rt] = -1;
        mx[rt] = lmx[rt] = rmx[rt] = len[rt];
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, ls);
        build(mid + 1, r, rs);
    }

    void pushdown(int rt)
    {
        if(tag[rt] != -1)
        {
            mx[ls] = lmx[ls] = rmx[ls] = tag[rt] ? len[ls] : 0;
            mx[rs] = lmx[rs] = rmx[rs] = tag[rt] ? len[rs] : 0;
            tag[ls] = tag[rs] = tag[rt];
            tag[rt] = -1;
        }
    }

    void update(int L, int R, int v, int l, int r, int rt)
    {
        if(l > R || r < L) return;
        if(L <= l && r <= R)
        {
            mx[rt] = lmx[rt] = rmx[rt] = v ? len[rt] : 0;
            tag[rt] = v;
            return;
        }
        pushdown(rt);
        int mid = (l + r) >> 1;
        update(L, R, v, l, mid, ls);
        update(L, R, v, mid + 1, r, rs);
        pushup(rt);
    }

    int query(int p, int l, int r, int rt)
    {
        if(l == r) return l;
        pushdown(rt);
        int mid = (l + r) >> 1;
        if(mx[ls] >= p) return query(p, l, mid, ls);
        if(rmx[ls] + lmx[rs] >= p) return mid - rmx[ls] + 1;
        return query(p, mid + 1, r, rs);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    seg :: build(1, n, 1);
    while(m--)
    {
        char op[5];
        scanf("%s", op);
        if(op[0] == 'A')
        {
            int p;
            scanf("%d", &p);
            if(seg :: mx[1] < p)
            {
                ans++;
                continue;
            }
            int l = seg :: query(p, 1, n, 1);
            seg :: update(l, l + p - 1, 0, 1, n, 1);
        }
        else
        {
            int a, b;
            scanf("%d%d", &a, &b);
            seg :: update(a, b, 1, 1, n, 1);
        }
    }
    printf("%d\n", ans);
    return 0;
}