基础查缺 归并排序+尺取法

归并排序

模板

优秀的nlg复杂度排序算法，记录目的并不是学会这个算法，分治的思想经常在题目中使用，直接给出模板，具体细节看模板。

int n, a[N], b[N]; //b为辅助数组
void merge_dfs(int l, int mid, int r)
{
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r)
    {
        b[k++] = (a[i] < a[j] ? a[i++] : a[j++]); //排序
    }
    while(i <= mid) b[k++] = a[i++];
    while(j <= r) b[k++] = a[j++];
    RE(i, l, r) a[i] = b[i]; //还原
}
void dfs(int l, int r)
{
    if(l == r) return;
    int mid = l + r >> 1;
    dfs(l, mid);
    dfs(mid + 1, r);
    merge_dfs(l, mid, r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

例题

1、Ultra-QuickSort

传送门
Des
求逆序对数量，这里就用归并写，里面直接可以看到交换次数，累加就是逆序对数量。树状数组已经写烂了
Code

#include 
#include 
#define RE(i, a, b) for(int i = a; i <= b; ++i)
#define int long long
using namespace std;
const int N = 5e5 + 100;
int n, a[N], b[N], ans;
void merge_dfs(int l, int mid, int r)
{
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++], ans += mid - i + 1; //在纸上模拟过程就懂了
    }
    while(i <= mid) b[k++] = a[i++];
    while(j <= r) b[k++] = a[j++];
    RE(i, l, r) a[i] = b[i];
}
void dfs(int l, int r)
{
    if(l == r) return;
    int mid = l + r >> 1;
    dfs(l, mid);
    dfs(mid + 1, r);
    merge_dfs(l, mid, r);
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    while(cin >> n && n)
    {
        RE(i, 1, n) cin >> a[i];
        ans = 0;
        dfs(1, n);
        cout << ans << "\n";
    }
    return 0;
}

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

尺取法

模板

当我们需要找到一个区间[L, R]符合某个性质的，且随着L的增大 ， R也呈现单增趋势（不一定严格) ，算法步骤很简单：
1、找到一段符合条件的区间[L, R]（一般从最左边开始）
2、更新左端点+1， 再去更新符合条件的R
3、直到找不到符合条件的区间，或者遍历结束，在里面更新答案最值

int ans = INF, l = 1, r = 1, cnt = 0;
for(; ;)
{
    while(r <= n && cnt < sum) cnt += a[r++]; //直到符合总数
    if(cnt < sum) break; //再也无法满足
    ans = min(ans, r - l); //更新答案
    cnt -= a[l++]; //尝试进步
}
1
2
3
4
5
6
7
8

例题

1、P4085 [USACO17DEC]Haybale Feast G

传送门
Des

Solution
简单来说，就是两个数组F, S, 大小为n，再给你一个sum，让你找到F数组里面某一段和>=sum, 对应S的段上最大值的最小值。最大值用线段树维护，找F数组符合条件的段直接尺取法。
Code

//restart
#include 
#include 
#define endl "\n"
#define int long long
#define RE(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N], b[N];
struct node
{
    int l, r, mn;
}t[N << 2];
void build(int rt, int l, int r)
{
    t[rt].l = l, t[rt].r = r;
    if(l == r)
    {
        t[rt].mn = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    t[rt].mn = max(t[rt << 1].mn, t[rt << 1 | 1].mn);
}
int query(int rt, int l, int r)
{
    if(t[rt].l >= l && t[rt].r <= r)
    {
        return t[rt].mn;
    }
    int mid = (t[rt].l + t[rt].r) >> 1;
    if(r <= mid) return query(rt << 1, l, r);
    else if(l > mid) return query(rt << 1 | 1, l, r);
    else return max(query(rt << 1, l, mid), query(rt << 1 | 1, mid + 1, r));
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    RE(i, 1, n) cin >> b[i] >> a[i];
    build(1, 1, n);
    int ans = 1e18, l = 1, r = 1, sum = 0;
    for(; ;)
    {
        while(r <= n && sum < m) sum += b[r++];
        if(sum < m) break;
        //cout << l << " " << r << " " << sum << endl;
        ans = min(ans, query(1, l, r - 1));
        sum -= b[l++];
    }
    cout << ans << endl;
    return 0;
}
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

2、Eggfruit Cake

传送门
Des
一个环形蛋糕，PE组成的字符串，求只有一个E和少于等于n个P的子串个数。
Solution
拉成两倍，然后预处理出E的位置，以E为符合条件字串的最后一个字符，尺取前面的长度。

#include 
#include 
#define int long long
#define RE(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;
const int N = 2e5 + 100;
char s[N];
int n, m, p[N], idx;
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> s + 1 >> m;
    n = strlen(s + 1);
    RE(i, 1, n) s[i + n] = s[i];
    RE(i, 1, 2 * n)
    if(s[i] == 'E') p[++idx] = i;
    if(idx == 0)
    {
        cout << "0\n";
        return 0;
    }
    int last = 1, ans = 0;
    RE(i, 1, n)
    {
        while(i > p[last] && last < idx) last++;
        if(last > idx) break;
        ans += max(0ll, m - (p[last] - i));
    }
    cout << ans;
    return 0;
}
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