[TOC]

9.23

P2032 扫描

单调队列求滑动窗口最大值

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
deque<pair<int, int>> q;
const int maxn = 2e6 + 10;
int a[maxn];
void pu(int i){
    if(a[i] >= q.front().first){
        q.clear();
        q.push_front({a[i], i});
    }
    else{
        while(a[i] >= q.back().first) q.pop_back();
        q.push_back({a[i], i});
    }
}
signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    int n, k;
    cin >> n >> k;
    fors(i, 1, n){
        cin >> a[i];
    }
    q.push_front({a[1], 1});
    fors(i, 2, k){
        pu(i);
    }
    cout << q.front().first << endl;
    fors(i, k + 1, n){
        while(q.front().second < 1 - k + i){
            q.pop_front(); 
        }
        pu(i);
        cout << q.front().first << endl;
    }
    return 0;
}

P1440 求m区间内的最小值

单调队列の双倍经验

注意要卡常（不开LL，用快读，printf）

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
// #define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
deque<pair<int, int>> q;
const int maxn = 2e6 + 10;
int a[maxn];
void pu(int i){
    if(q.empty()){
        q.push_front({a[i], i});
        return;
    }
    if(a[i] <= q.front().first){
        q.clear();
        q.push_front({a[i], i});
    }
    else{
        while(a[i] <= q.back().first) q.pop_back();
        q.push_back({a[i], i});
    }
}
inline int rd()
{
    int data = 0;
    int f = 1;
    char ch = getchar();
    while(ch < '0'||ch > '9')
    {
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0'&&ch <= '9')
    {
        data = (data<<3) + (data<<1) + ch - '0';
        ch = getchar();
    }
    return f * data; 
}
signed main()
{
    // DDLC_ESCAPE_PLAN_FAILED;
    int n, k;
    n = rd(), k = rd();
    fors(i, 1, n){
        a[i] = rd();
    }
    printf("0\n");
    q.push_front({a[1], 1});
    printf("%d\n", q.front().first);
    fors(i, 2, n - 1){
        while(!q.empty() && q.front().second < 1 - k + i){
            q.pop_front(); 
        }
        pu(i);
        printf("%d\n", q.front().first);
    }
    return 0;
}

P1886 滑动窗口

三倍经验，滑动窗口也可以写得更简洁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int a[maxn];
deque<pair<int, int>> mx, mn;
vector<int> x, y;
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i){
        while(!mx.empty() && a[i] >= mx.back().first) mx.pop_back();
        while(!mx.empty() && mx.front().second < i - k + 1) mx.pop_front();
        mx.push_back({a[i], i});
        while(!mn.empty() && a[i] <= mn.back().first) mn.pop_back();
        while(!mn.empty() && mn.front().second < i - k + 1) mn.pop_front();
        mn.push_back({a[i], i});
        if(i >= k) x.push_back(mx.front().first), y.push_back(mn.front().first);
    }
    for(int i = 0; i < x.size(); ++i) printf("%d ", y[i]); printf("\n");
    for(int i = 0; i < y.size(); ++i) printf("%d ", x[i]); printf("\n");
    return 0;
}

P3143 [USACO16OPEN]Diamond Collector S

双指针，注意题目要求两个区间不能重叠，故要左右分别枚举，再遍历更新答案。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50005;
int a[maxn];
int L[maxn] = {0}, R[maxn] = {0};
int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);
    int r = 0, l = n - 1;
    for(int i = 0; i < n; ++i){
        while(r < n && a[r] - a[i] <= k) r++;
        R[i] = r - i;
    }
    for(int i = n - 1; i >= 0; --i){
        while(l >= 0 && a[i] - a[l] <= k) l--;
        L[i] = i - l;
    }
    int ans = 0, lmax = 0;
    for(int i = 0; i < n; ++i){
        ans = max(ans, lmax + R[i]);
        lmax = max(L[i], lmax);
    }
    cout << ans << endl;
    return 0;
}

9.25

打了网络赛才发现，自己的数学就是一坨⑩，让人完全看不下去。学！

P1143 进制转换

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;    

signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    int t;
    t = 1;
    while(t--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int to;
        cin >> to;
        int ans = 0;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] >= 'A' && s[i] <= 'Z'){
                ans = ans * n + s[i] - 'A' + 10;
            }
            else ans = ans * n + s[i] - '0';
        }
        string fin;
        while(ans){
            int res = ans % to;
            if(res >= 10) res = res - 10 + 'A';
            else res += '0';
            fin += res;
            ans /= to;
        }
        reverse(fin.begin(), fin.end());
        cout << fin << endl;
    }
    return 0;
}

P1469 找筷子

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d", &n);
    int x, ans = 0;
    while(n--) scanf("%d", &x), ans ^= x;
    printf("%d", ans);
    return 0;
}

P1100 高低位交换

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main()
{
    unsigned int x;
    cin >> x;
    cout << (x << 16) + (x >> 16) << endl; 
    return 0;
}

P1017 [NOIP2000 提高组] 进制转换

余数可能出现负数，将其加上进制数，将商减去进制数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x, to;
    scanf("%d%d", &x, &to);
    string ans;
    int r = x;
    while(x){
        int res = x % to;
        if(res < 0) res -= to, x += to;
        if(res >= 10) res = res - 10 + 'A';
        else res = res + '0';
        ans += res;
        x /= to;
    }
    reverse(ans.begin(), ans.end());
    printf("%d=%s(base%d)", r, ans.c_str(), to);
}

P1866 编号 - 洛谷

高中最简单的排列组合方法之一——优限法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 55;
int m[maxn];
signed main()
{
    int N;
    scanf("%lld", &N);
    for(int i = 1; i <= N; ++i) scanf("%lld", &m[i]);
    sort(m + 1, m + 1 + N);
    int ans = 1;
    for(int i = 1; i <= N; ++i){
        ans = (ans * (m[i] - i + 1)) % mod;
    }
    printf("%d", ans);
}

P2822 [NOIP2016 提高组] 组合数问题

二维前缀和

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, k;
const int maxn = 2005;
int c[maxn][maxn] = {0};
int pre[maxn][maxn] = {0};
void prework()
{
    c[0][0] = 1;
    pre[0][0] = 0;
    for(int i = 1; i <= 2000; ++i){
        c[i][0] = 1;
        pre[i][0] = (1 % k == 0);
        for(int j = 1; j <= 2000; ++j){
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            c[i][j] %= k;
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + (j <= i && c[i][j] == 0);
        }
    }
}
signed main()
{
    cin >> t >> k;
    prework();
    while(t--)
    {
        int n, m;
        cin >> n >> m;
        if(n < m) m = n;
        cout << pre[n][m] << endl;
    }
    return 0;
}

P2789 直线交点数

注意构造好的搜索方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define int long long
using namespace std;
bool f[100005] = {0};
int ans = 0;
void dfs(int p, int r){
    if(p == 0){
        if(!f[r]) f[r] = 1, ans++;
        return;
    }
    for(int s = p; s; --s){
        dfs(p - s, r + (p - s) * s);
    }
}
signed main()
{
    int n;
    cin >> n;
    dfs(n, 0);
    cout << ans << endl;
    return 0;
}

P3913 车的攻击

容斥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k;
const int maxn = 1e6 + 10;
unordered_map<int, bool> r, c;
signed main()
{
    scanf("%d%d", &n, &k);
    for(int i = 0; i < k; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        r[x] = 1, c[y] = 1;
    }
    cout << (r.size() + c.size()) * n - r.size() * c.size() << endl;
    return 0;
}

P2638 安全系统

组合数学只会瞎搞

隔板法，请

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
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n, a, b;
const int maxn = 55;
int c[maxn][maxn] = {0};
void prework()
{
    c[1][0] = c[1][1] = 1;
    c[0][1] = 0;
    for(int i = 2; i <= 50; ++i){
        c[i][0] = 1;
        for(int j = 1; j <= i; ++j){
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
}
signed main()
{
    int ans = 0;
    prework();
    cin >> n >> a >> b;
    for(int i = 0; i <= a; ++i){
        for(int j = 0; j <= b; ++j){
            ans += c[n + i - 1][n - 1] * c[n + j - 1][n - 1];
        }
    }
    cout << ans << endl;
    return 0;
}

9.26

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int x, y;
    cin >> x >> y;
    // 找x*y的因子
    int ans = 0;
    int u = x * y;
    for(int i = 2; i * i <= u; ++i){
        if(u % i) continue;
        int r1 = i, r2 = u / i;
        int p = __gcd(r1, r2);
        if(p != x || u / p != y) continue;
        if(r1 == r2) ans++;
        else ans += 2;
    }
    cout << ans << endl;
    return 0;
}

P1072 [NOIP2009 提高组] Hankson 的趣味题

菜

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
#include <bits/stdc++.h>
using namespace std;
// #define int long long
int gcd(int a,int b) {
    return b==0?a:gcd(b,a%b);
}
signed main()
{
    int a0, a1, b0, b1;
    int n;
    scanf("%d", &n);
    while(n--){
        scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
        int ans = 0;
        for(int i = 1; i * i <= b1; ++i){
            if(b1 % i) continue;
            if(i%a1==0&&gcd(i/a1,a0/a1)==1&&gcd(b1/b0,b1/i)==1) ans++;
            int y = b1 / i;
            if(i == y) continue;
            if(y%a1==0&&gcd(y/a1,a0/a1)==1&&gcd(b1/b0,b1/y)==1) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

P1908 逆序对

就多练

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 <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 10;
int a[maxn];
int tmp[maxn];
int ans = 0;
void merge(int l, int r){
    if(r == l) return;
    int mid = (l + r) >> 1;
    merge(l, mid), merge(mid + 1, r);
    int p1 = l, p2 = mid + 1, p3 = 0;
    while(p1 <= mid || p2 <= r){
        if((p1 > mid) || (p2 <= r && a[p1] > a[p2])) tmp[p3++] = a[p2++], ans += mid - p1 + 1;
        else tmp[p3++] = a[p1++];
    }
    for(int i = l; i <= r; ++i){
        a[i] = tmp[i - l];
    }
}
signed main()
{
    int n;
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    merge(1, n);
    printf("%lld", ans);
    return 0;
}

P1966 [NOIP2013 提高组] 火柴排队

先找出数学性质，知道可以让其中一组不动，另一组中每个火柴二分找到第一组中和自己最接近的高度的位置，然后按这个位置归并计数。

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
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e8 - 3;
int n;
const int maxn = 1e5 + 10;
struct node{
    int val, idx, midx;
    bool operator < (const node& x)const{
        return val < x.val;
    }
    bool operator ==(const int& x)const{
        return val == x;
    }
}a[maxn], b[maxn], tmp[maxn];
int bs(int x){
    int l = 1, r = n;
    while(l < r){
        int mid = (l + r) >> 1;
        if(a[mid].val >= x){
            r = mid;
        }
        else l = mid + 1;
    }
    return r;
}
int ans = 0;
void merge(int l, int r){
    if(r == l) return;
    int mid = (l + r) >> 1;
    merge(l, mid), merge(mid + 1, r);
    int p1 = l, p2 = mid + 1, p3 = 0;
    while(p1 <= mid || p2 <= r){
        if(p1 > mid || (p2 <= r && b[p2].midx < b[p1].midx)) tmp[p3++] = b[p2++], ans += mid - p1 + 1, ans %= mod;
        else tmp[p3++] = b[p1++];
    }
    for(int i = l; i <= r; ++i) b[i] = tmp[i - l];
}
signed main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i].idx = i;
    for(int i = 1; i <= n; ++i) scanf("%d", &b[i]), b[i].idx = i;
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; ++i){
        int r = bs(b[i].val);
        b[i].midx = a[r].idx;
    }
    merge(1, n);
    printf("%d", ans);
    return 0;
}

9.29

前两天满课太难受了…都在补CF的题，感觉补CF的题效率有点低，一补就是一晚上还补不到几题。

看到CDQ分治本来想直接学，但发现树状数组没学，再往前又发现倍增的思想也不熟……我的知识还是没成体系啊

P3374 【模板】树状数组 1

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
#include <bits/stdc++.h>
#define lowbit(x) x&(-(x))
using namespace std;
const int maxn = 5e5 + 10;
int a[maxn], c[maxn];
int n, m;
inline void add(int x, int k){ // 单点加k
    while(x <= n){
        c[x] += k;
        x += lowbit(x);
    }
}
void update(int x, int y, int n){
    for(int i = x; i <= n; i += lowbit(i)){
        c[i] += y;
    }
}
int sum(int x){ // sum of 1...x
    int ans = 0;
    while(x >= 1){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
int intsum(int l, int r)
{
    return sum(r) - sum(l - 1);
}
int main()
{
    scanf("%d%d", &n, &m);
    int z;
    for(int i = 1; i <= n; ++i){
        scanf("%d", &z);
        update(i, z, n);
    }
    int x, k;
    while(m--){
        scanf("%d%d%d", &z, &x, &k);
        if(z == 1){
            add(x, k);
        }
        else{
            printf("%d\n", intsum(x, k));
        }
    }
    return 0;
}

P3368 【模板】树状数组 2

差分一下，就能把单点修改+区间查询变成单点查询+区间修改

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 lowbit(x) x&(-(x))
using namespace std;
const int maxn = 5e5 + 10;
int a[maxn], b[maxn], c[maxn];
int n, m;
void add(int x, int k){
    while(x <= n){
        c[x] += k;
        x += lowbit(x);
    }
}
int sum(int x){
    int ans = 0;
    while(x >= 1){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
signed main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i) b[i] = a[i] - a[i - 1];
    for(int i = 1; i <= n; ++i) add(i, b[i]);
    while(m--)
    {
        int z, x, y, k;
        scanf("%d", &z);
        if(z == 1){
            scanf("%d%d%d", &x, &y, &k);
            add(x, k), add(y + 1, -k);
        }
        else{
            scanf("%d", &x);
            printf("%d\n", sum(x));
        }
    }
    return 0;
}

不过复习一下之后就回想起来，树状数组也确实很好理解，难怪是普及题啊

P2345 [USACO04OPEN]MooFest G

排序离散化后树状数组直接解，但是还没想清楚CDQ分治应该怎么做

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 <bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn = 2e4 + 10;
int n;
struct node{
    int v, x, id;
    bool operator < (const node& y)const{
        return x < y.x;
    }
}a[maxn];
bool cmp(const node& x, const node& y){
    return x.v < y.v;
}
int c[maxn], s[maxn];
void add(int x, int k){
    while(x <= n){
        c[x] += k;
        x += lowbit(x);
    }
}
void adds(int x, int k){
    while(x <= n){
        s[x] += k;
        x += lowbit(x);
    }
}
int sum(int x){
    int ans = 0;
    while(x >= 1){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
int sums(int x){
    int ans = 0;
    while(x >= 1){
        ans += s[x];
        x -= lowbit(x);
    }
    return ans;
}
signed main()
{
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%lld%lld", &a[i].v, &a[i].x);
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; ++i) a[i].id = i;
    sort(a + 1, a + 1 + n, cmp);
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        int cnt = sum(a[i].id - 1);
        ans += a[i].v * (cnt * a[i].x - sums(a[i].id - 1));
        cnt = sum(n) - sum(a[i].id);
        ans += a[i].v * (sums(n) - sums(a[i].id) - cnt * a[i].x);
        add(a[i].id, 1);
        adds(a[i].id, a[i].x);
    }
    printf("%lld\n", ans);
    return 0;
}

P2926 [USACO08DEC]Patting Heads S

题意讲反了，本来一点也不难吧

不过都一样，求因子复杂度$O(\sqrt n)$

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
#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e6 + 10;
int ans[100005];
int a[maxn];
int d[100005];
// vector<int> v[maxn];
int main()
{
    scanf("%d", &n);
    int x;
    for(int i = 1; i <= n; ++i){
        scanf("%d", &x);
        d[i] = x;
        // v[x].push_back(i);
        a[x]++;
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j * j <= d[i]; ++j){
            if(d[i] % j) continue;
            if(a[j]){
                ans[i] += a[j];
            }
            if(j == d[i]) ans[i]--;
            if(j == d[i] / j) continue;
            if(a[d[i] / j]){
                ans[i] += a[d[i] / j];
            }
            if(d[i] / j == d[i]) ans[i]--;
        }
    }
    for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;
}

10.1

国庆假期的学习计划：

目前需要学的知识点：

CDQ分治，主席树（可持久化线段树）

然后就是打牛客的国庆派对，补题，看看还有哪些可学的知识点

还有个任务就是上蓝名

10.4

P3810 【模板】三维偏序（陌上花开）

看cdq的概念解读，各种解释，OI wiki，总是不提怎么归并处理，怎么解决影响问题。真做了题，才算是祛魅，也不是多么复杂的算法嘛（CDQ套CDQ警告）

知乎上的洛谷日报对基础CDQ讲的很透彻，点赞。

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>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define pii pair<int, int>
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 10;
int z[maxn];
int n, m;
int cnt[maxn];
void add(int x, int k) {
	while(x <= m) {
		z[x] += k;
		x += lowbit(x);
	}
}
int sum(int x) {
	int ans = 0;
	while(x >= 1) {
		ans += z[x];
		x -= lowbit(x);
	}
	return ans;
}
struct node{
	int a, b, c, id;
	bool operator < (const node& x)const {
		if(a != x.a) return a < x.a;
		if(c != x.c) return c < x.c;
		return b < x.b;
	}
}s[maxn], tmp[maxn];
map< pair <pii, int>, int> mp;
int ans[maxn];

void pre() {
	fors(i, 1, n) {
		cnt[i] += mp[make_pair(make_pair(s[i].a, s[i].b), s[i].c)];
		ans[i] += cnt[i] - 1;
	}
}

void cdq(int l, int r) {
	if(r == l) return;
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	// 统计答案并按b排序
	// (c)建树状数组
	int p1 = l, p2 = mid + 1, p3 = 0;
	while (p1 <= mid || p2 <= r) {
		if (p1 > mid || (p2 <= r && s[p1].b > s[p2].b)) {
			ans[s[p2].id] += sum(s[p2].c);
			tmp[p3++] = s[p2++];
		}
		else {
			add(s[p1].c, cnt[s[p1].id]);
			// ans[s[p2].id] += sum(s[p2].c - 1);
			tmp[p3++] = s[p1++];
		}
	}
	for (int i = l; i <= mid; ++i) add(s[i].c, -cnt[s[i].id]);
	for (int i = l; i <= r; ++i) {
		s[i] = tmp[i - l];
	}
}
int f[maxn];
signed main()
{
	DDLC_ESCAPE_PLAN_FAILED;
	int t;
	t = 1;
	while (t--)
	{
		cin >> n >> m;
		int all = n;
		fors (i, 1, n) {
			cin >> s[i].a >> s[i].b >> s[i].c, s[i].id = i;
			mp[{{s[i].a, s[i].b}, s[i].c}]++;
			if (mp[{{s[i].a, s[i].b}, s[i].c}] > 1) {
				i--, n--;
			}
		}
		pre();
		sort (s + 1, s + 1 + n);
		cdq(1, n);
		fors (i, 1, n) {
			f[ans[i]] += cnt[i];
		}
		fors (i, 1, all) {
			cout << f[i - 1] << endl;
		}
	}
	return 0;
}

P2717 寒假作业

转化一下，求平均数$\geq k$的子段$\Lrarr$每个数减去$k$后求平均数$\geq 0$的子段。

再接着转化，把原数组改为前缀和数组，则求$(0,n)$内$pre[j]-pre[i]>=0$的点对，也即求$(0,n)$内的顺序对数目，和求逆序对一样分治即可。

所以不需要用cdq（（

如果cdq的话，貌似要尺取。

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 fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define pii pair<int, int>
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
int n, k;
const int maxn = 1e5 + 10;
int a[maxn], tmp[maxn];
int ans = 0;
void solve(int l, int r) {
	if(r == l) return;
	int mid = (l + r) >> 1;
	solve(l, mid); solve(mid + 1, r);
	int p1 = l, p2 = mid + 1, p3 = l;
	while(p1 <= mid || p2 <= r) {
		if(p1 > mid || (p2 <= r && a[p1] <= a[p2])) {
			ans += mid - p1 + 1;
			tmp[p3++] = a[p2++];
		}
		else {
			tmp[p3++] = a[p1++];
		}
	}
	for(int i = l; i <= r; ++i) a[i] = tmp[i];
}
signed main()
{
	DDLC_ESCAPE_PLAN_FAILED;
	cin >> n >> k;
	fors(i, 1, n) cin >> a[i], a[i] -= k;
	fors(i, 1, n) a[i] = a[i - 1] + a[i];
	solve(0, n);
	cout << ans << endl;
	return 0;
}

10.6

P3919 【模板】可持久化线段树 1（可持久化数组）

任务完成！我学会了CDQ和主席树！（至少模板题过了呜呜呜）

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
/**
  * @file    :deb.cpp
  * @brief   :
  * @date    :2021-10-06
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
// #define int long long
#define pii pair<int, int>
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
int n, m;
// 可持久化数组版
const int maxn = 1e6 + 1;
struct node {
    int rt, lc, rc, sum; // 区间和..
}a[maxn * 24];
int cnt; // 记录版本数
int x[maxn]; // 初始数组
void build(int &rt, int l, int r) {
    rt = ++cnt;
    if (l == r) {
        a[rt].sum = x[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(a[rt].lc, l, mid);
    build(a[rt].rc, mid + 1, r);
}
void update(int &rt, int f, int l, int r, int x, int val) { // 节点编号，来源版本，左边界，有边界，下标，要改的值
    rt = ++cnt;
    a[rt].lc = a[f].lc, a[rt].rc = a[f].rc, a[rt].sum = a[f].sum;
    if (l == r) {
        a[rt].sum = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        update(a[rt].lc, a[f].lc, l, mid, x, val);
    }
    else update(a[rt].rc, a[f].rc, mid + 1, r, x, val);
}
int query(int rt, int l, int r, int x) { // 节点编号，左右边界，要查的下标
    if (r == l) {
        return a[rt].sum;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) return query(a[rt].lc, l, mid, x);
    else return query(a[rt].rc, mid + 1, r, x);
}
signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    cin >> n >> m;
    fors (i, 1, n) cin >> x[i];
    build (a[0].rt, 1, n);
    fors (j, 1, m) {
        int v, loc, value, op;
        cin >> v >> op;
        if(op == 1) {
            cin >> loc >> value;
            update(a[j].rt, a[v].rt, 1, n, loc, value);
        }
        else {
            cin >> loc;
            cout << query(a[v].rt, 1, n, loc) << endl;
            a[j].rt = a[v].rt;
        }
    }
    return 0;
}

10.8

P3396 哈希冲突

根号算法，思想和分块高度重合，但个人认为不是分块（

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 150000 + 100;
int a[maxn];
int n, m;
int mp[1005][1005]; // 模i意义下第j个池的和
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j * j <= n; ++j) {
            int p = i % j;
            mp[j][p] += a[i];
        }
    }
    char cmd; int x, y;
    while (m--) {
        cin >> cmd >> x >> y;
        if(cmd == 'C') {
            for (int i = 1; i * i <= n; ++i) {
                int p = x % i;
                mp[i][p] -= a[x];
                mp[i][p] += y;
            }
            a[x] = y;
        }
        else {
            if (x * x <= n) {
                cout << mp[x][y] << endl;
            }
            else {
                int ans = 0;
                if (y >= x) {
                    cout << 0 << endl;
                    continue;
                }
                for (int i = y; i <= n; i += x) {
                    ans += a[i];
                }
                cout << ans << endl;
            }
        }
    }
    return 0;
}

10.11

P3379 【模板】最近公共祖先（LCA）

蒟蒻开始学倍增，赶快把不会的知识点都补了，希望未来几个月能组个正常的队（有腿抱最好了qwq，所以要加油）

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
// #define int long long
#define pii pair<int, int>
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
int n, m, s;
const int maxn = 5e6 + 10;
vector<int> e[maxn];
int dep[maxn];
int fa[maxn][31];
void dfs (int now, int f, int d) {
    for (auto &x : e[now]) {
        if(x != f) {
            fa[x][0] = now;
            dep[x] = d;
            dfs(x, now, d + 1);
        }
    }
}
int lg[maxn];
int fd (int x, int y) {
    for (int i = lg[n] + 1; i >= 0; --i) {
        if(fa[x][i] != fa[y][i]) {
            x = fa[x][i], y = fa[y][i];
        }
    }
    return fa[x][0];
}

int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

signed main() {
    // cin >> n >> m >> s;
    n = read(); m = read(); s = read();
    int x, y;
    int p = 1;
    for (int i = 2; i <= n; ++i) {
        if(i == (1 << p)) {
            p++;
            lg[i] = lg[i - 1] + 1;
        }
        else lg[i] = lg[i - 1];
    }
    for (int i = 1; i < n; ++i) {
        x = read(); y = read();
        e[x].pb(y), e[y].pb(x);
    }
    dfs(s, -1, 1);
    for (int i = 1; i <= lg[n] + 1; ++i) {
        for (int j = 1; j <= n; ++j) {
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
        }
    }
    for (int i = 1; i <= m; ++i) {
        x = read(); y = read();
        if (dep[x] < dep[y]) swap(x, y);
        while (dep[x] > dep[y]) {
            x = fa[x][(int)lg[dep[x] - dep[y]]];
        }
        if(x == y) cout << x << endl;
        else cout << fd(x, y) << endl;
    }
    return 0;
}

10.12

P1613 跑路

忘了C++11好像不支持堆变量自动初始化，害的白wa了好几次qwq

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
#include <bits/stdc++.h>
// #define int long long
using namespace std;
const int maxn = 55;
int n, m;
bool e[maxn][maxn][70];
int f[maxn][maxn];
signed main() {
    scanf("%d%d", &n, &m);
    int u, v;
    memset(e, 0, sizeof(e));
    memset(f, 10, sizeof(f));
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        e[u][v][0] = 1;
        f[u][v] = 1;
    }
    for (int j = 1; j <= 64; ++j) {
        for (int i = 1; i <= n; ++i) {
            for (int x = 1; x <= n; ++x) {
                if(!e[i][x][j - 1]) continue;
                for (int y = 1; y <= n; ++y) {
                    if (e[x][y][j - 1]) {
                        e[i][y][j] = 1;
                        f[i][y] = 1;
                    }
                }
            }
        }
    }
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
    printf("%d", f[1][n]);
    return 0;
}

P5002 专心OI - 找祖先

一道递归组合题，和LCA其实没关系

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 <bits/stdc++.h>
#define int long long
using namespace std;
int n, r, m;
const int maxn = 1e4 + 10;
const int mod = 1e9 + 7;
vector<int> e[maxn];
int sz[maxn]; // 以i为根节点的子树大小
int ans[maxn]; // 记忆答案
void dfs(int i, int f) {
    for (auto &x : e[i]) {
        if(x == f) continue;
        dfs(x, i);
        sz[i] += sz[x];
    }
    sz[i]++;
}
int fpow(int x, int y) {
    int ans = 1;
    while(y) {
        if(y & 1) ans = (ans * x) % mod;
        x = (x * x) % mod;
        y >>= 1ll;
    }
    return ans;
}
int get(int i) {
    int s = 0;
    int an = 0;
    for (auto &x : e[i]) {
        if(sz[x] > sz[i]) continue;
        an = (an + (s * sz[x]) % mod) % mod;
        s = (s + sz[x]) % mod;
    }
    an = (an * 2) % mod;
    an = (an + 2 * sz[i] - 1) % mod;
    ans[i] = an;
    return an;
}
signed main() {
    memset(ans, 0, sizeof(ans));
    scanf("%lld%lld%lld", &n, &r, &m);
    int a, b;
    for (int i = 1; i < n; ++i) {
        scanf("%lld%lld", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs(r, -1);
    while (m--) {
        scanf("%lld", &a);
        if(ans[a]) printf("%lld\n", ans[a]);
        else printf("%lld\n", get(a));
    }
    return 0;
}

P3402 可持久化并查集

按照题解写的启发式合并，貌似跑的飞快。。（$\leq 200ms$）

按秩合并应该更快吧

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
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int n, m;
const int maxn = 1e5 + 10;
struct node{
    int rt, lc, rc;
}a[maxn << 5];
int cnt = 0;
int dep[maxn << 5];
int fa[maxn << 5];
void build(int &rt, int l, int r) {
    rt = ++cnt;
    if(l == r) {
        fa[rt] = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(a[rt].lc, l, mid);
    build(a[rt].rc, mid + 1, r);
}
void join(int &rt, int x1, int x2, int l, int r, int f) { // 将x1的父亲修改为x2
    rt = ++cnt;
    if(l == r) {
        fa[rt] = x2;
        dep[rt] = dep[f];
        return;
    }
    a[rt].lc = a[f].lc, a[rt].rc = a[f].rc;
    int mid = (l + r) >> 1;
    if(x1 <= mid) join(a[rt].lc, x1, x2, l, mid, a[f].lc);
    else join(a[rt].rc, x1, x2, mid + 1, r, a[f].rc);
}
int query(int rt, int l, int r, int x) { // x的直属父亲
    if(l == r) {
        return rt;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) return query(a[rt].lc, l, mid, x);
    else return query(a[rt].rc, mid + 1, r, x);
}
void add(int rt, int l, int r, int x) {
    if(l == r) {
        dep[rt]++; return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) add(a[rt].lc, l, mid, x);
    else add(a[rt].rc, mid + 1, r, x);
}
int findfa(int i, int x) { // 版本i中x的祖先
    int fx = query(a[i].rt, 1, n, x);
    if(fa[fx] == x) return fx;
    return findfa(i, fa[fx]);
}
int main() {
    memset(dep, 0, sizeof(dep));
    scanf("%d%d", &n, &m);
    build(a[0].rt, 1, n);
    int opt, k, x, y;
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d%d", &x, &y);
            a[i].rt = a[i - 1].rt;
            int fx = findfa(i, x), fy = findfa(i, y);
            if(fa[fx] == fa[fy]) continue;
            if(dep[fx] > dep[fy]) swap(fx, fy);
            join(a[i].rt, fa[fx], fa[fy], 1, n, a[i - 1].rt);
            if(dep[fx] == dep[fy]) add(a[i].rt, 1, n, fa[fy]);
        }
        else if (opt == 2) {
            scanf("%d", &k);
            a[i].rt = a[k].rt;
        }
        else if (opt == 3) {
            scanf("%d%d", &x, &y);
            a[i].rt = a[i - 1].rt;
            int fx = findfa(i, x), fy = findfa(i, y);
            if(fa[fx] == fa[fy]) printf("1\n");
            else printf("0\n");
        }
    }
    return 0;
}

10.16

P2801 教主的魔法

再次说明我的大题coding能力就跟坨⑩一样。。

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
122
123
124
125
126
127
128
129
130
131
/**
  * @file    :debug.cpp
  * @brief   :
  * @date    :2021-10-16
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
// #define int long long
#define pii pair<int, int>
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e6 + 10;
int blc[maxn]; // i在第几块内
int rb[maxn / 1000 + 100] = {0}, lb[maxn / 1000 + 100] = {0};
int a[maxn];
int d[maxn]; // 排序后的
int n, q;
int sn;
int tag[maxn / 1000 + 100]; // 整块tag，用于整块操作的数据维护,表示整个区间都被加上了tag[i]
void add(int l, int r, int w) {
	if(blc[l] == blc[r]) {
		fors(i, l, r) a[i] += w;
		fors(i, l, r) d[i] = a[i];
		sort(d + lb[blc[l]], d + 1 + rb[blc[l]]);
		return;
	}
	fors(i, l, rb[blc[l]]) {
		a[i] += w;
	} fors(i, lb[blc[l]], rb[blc[l]]) d[i] = a[i];
	sort(d + lb[blc[l]], d + rb[blc[l]] + 1);
	fors(i, lb[blc[r]], r) {
		a[i] += w;
	} fors(i, lb[blc[r]], rb[blc[r]]) d[i] = a[i];
	sort(d + lb[blc[r]], d + rb[blc[r]] + 1);
	fors(i, blc[l] + 1, blc[r] - 1) {
		tag[i] += w;
	}
}
int lbound(int l, int r, int c, int i);
int query(int l, int r, int c) {
	int ans = 0;
	if(blc[l] == blc[r]) {
		fors(i, l, r) if(a[i] + tag[blc[i]] >= c) ans++;
		return ans;
	}
	fors(i, l, rb[blc[l]]) {
		if(a[i] + tag[blc[i]] >= c) ans++;
	}
	fors(i, lb[blc[r]], r) {
		if(a[i] + tag[blc[i]] >= c) ans++;
	}
	fors(i, blc[l] + 1, blc[r] - 1) {
		// int p = lower_bound(d + lb[i], d + rb[i] + 1, c - tag[i]) - d;

		ans += lbound(lb[i], rb[i], c, i);
	}
	return ans;
}
int lbound(int l, int r, int c, int i) {
	int ll = l, rr = r, ans = 0, mid;
	while(ll <= rr) {
		mid = (ll + rr) >> 1;
		if(d[mid] + tag[i] >= c) rr = mid - 1, ans = rb[i] - mid + 1;
		else ll = mid + 1;
	}
	return ans;
}
void cread(char &x)
{
    x = 0;
	while(x != 'M' &&x != 'A') x = getchar();
}
// 某个快读模板qwq
template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')){
        ch=getchar();
    }
    if(ch=='-'){
        fh=-1;ch=getchar();
    }else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    x*=fh;
}

signed main() {
	// freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
	read(n); read(q);
	fors(i, 1, n) { read(a[i]); d[i] = a[i]; }
	sn = sqrt(n);
	int bid;
	bid = n / sn;
	if(n % sn) bid++;
	fors(i ,1, n) {
		blc[i] = (i - 1) / sn + 1;
	}
	fors(i, 1, bid) {
		lb[i] = (i - 1) * sn + 1;
		rb[i] = i * sn;
	}
	rb[bid] = n;
	fors(i, 1, bid) {
		sort(d + lb[i], d + rb[i] + 1);
	}
	char x;
	int l, r, w;
	fors(i, 1, q) {
		cread(x);
		read(l);
		read(r);
		read(w);
		if(x == 'M') add(l, r, w);
		else printf("%d\n", query(l, r, w));
	}
	return 0;
}

P4135 作诗

分块+预处理

很好的紫题

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
#include <bits/stdc++.h>
using namespace std;
int n, c, m;
const int maxn = 1e5 + 10;
const int N = 355;
int a[maxn];
int f[N][N] = {0}; // 从i到j（块），有多少个数出现了偶数次
int s[N][maxn] = {0}; // 前i块中j出现了多少次
int blc[N];
int l[N], r[N];
int mp[maxn] = {0};
int main() {
    scanf("%d%d%d", &n, &c, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    int ll, rr;
    int sn = sqrt(n);
    int tot = n / sn; if(n % sn) tot++;
    for (int i = 1; i <= n; ++i) {
        blc[i] = (i - 1) / sn + 1;
    }
    for (int i = 1; i <= tot; ++i) {
        l[i] = (i - 1) * sn + 1;
        r[i] = i * sn;
    }
    r[tot] = n;
    for (int i = 1; i <= tot; ++i) {
        for (int j = 1; j <= c; ++j) s[i][j] = s[i - 1][j];
        for (int j = l[i]; j <= r[i]; ++j) {
            s[i][a[j]]++;
        }
    }
    for (int i = 1; i <= tot; ++i) {
        int ans = 0;
        // unordered_map<int, int> mp;
        for(int j = i; j <= tot; ++j) {
            for (int k = l[j]; k <= r[j]; ++k) {
                mp[a[k]]++;
                if (mp[a[k]] > 1 && (mp[a[k]] & 1)) ans--;
                else if (!(mp[a[k]] & 1)) ans++;
            }
            f[i][j] = ans;
        }
        for (int j = 1; j <= c; ++j) mp[j] = 0;
    }
    int aa = 0;
    for (int k = 1; k <= m; ++k) {
        scanf("%d%d", &ll, &rr);
        ll = (ll + aa) % n + 1;
        rr = (rr + aa) % n + 1;
        if (ll > rr) swap(ll, rr);
        // unordered_map<int, int> mp;
        int ans = 0;
        if (blc[ll] == blc[rr]) {
            for (int i = ll; i <= rr; ++i) {
                mp[a[i]]++;
                if (mp[a[i]] > 1 && (mp[a[i]] & 1)) ans--;
                else if (!(mp[a[i]] & 1)) ans++;
            }
            printf("%d\n", ans);
            aa = ans;
            for (int i = ll; i <= rr; ++i) mp[a[i]]--;
        }
        else {
            int ans = f[blc[ll] + 1][blc[rr] - 1];
            for (int i = ll; i <= r[blc[ll]]; ++i) {
                mp[a[i]]++;
                int res = (mp[a[i]] + s[blc[rr] - 1][a[i]] - s[blc[ll]][a[i]]);
                if(res > 1 && (res & 1)) ans--;
                else if(!(res & 1)) ans++;
            }
            for (int i = l[blc[rr]]; i <= rr; ++i) {
                mp[a[i]]++;
                int res = (mp[a[i]] + s[blc[rr] - 1][a[i]] - s[blc[ll]][a[i]]);
                if(res > 1 && (res & 1)) ans--;
                else if(!(res & 1)) ans++;
            }
            for (int i = ll; i <= r[blc[ll]]; ++i) mp[a[i]]--;
            for (int i = l[blc[rr]]; i <= rr; ++i) mp[a[i]]--;
            printf("%d\n", ans);
            aa = ans;
        }
    }
    return 0;
}

P4168 [Violet]蒲公英

区间众数问题

和上面的P4135一样也是个好题

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
122
123
124
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e4 + 10;
const int N = 205;
struct node {
    int val, id, des;
}Node[maxn];
int n, m;
bool cmp1(const node& x, const node& y) {
    return x.val == y.val ? x.id < y.id : x.val < y.val;
}
bool cmp2(const node &x, const node& y) {
    return x.id < y.id;
}
unordered_map<int, int> src;
int a[maxn];
void descrete() {
    sort(Node + 1, Node + 1 + n, cmp1);
    Node[1].des = 1;
    for (int i = 2; i <= n; ++i) {
        if(Node[i].val == Node[i - 1].val) Node[i].des = Node[i - 1].des;
        else Node[i].des = Node[i - 1].des + 1;
    }
    sort(Node + 1, Node + 1 + n, cmp2);
    for (int i = 1; i <= n; ++i) {
        if(!src.count(Node[i].des)) src[Node[i].des] = Node[i].val;
    }
    for (int i = 1; i <= n; ++i) a[i] = Node[i].des;
}
int blc[maxn];
int l[N], r[N];
int tot;
int d[N][N] = {0};
int f[N][maxn] = {0};
int mp[maxn] = {0};
void prework() {
    int sn = sqrt(n);
    tot = n / sn; if(n % sn) tot++;
    for (int i = 1; i <= n; ++i) blc[i] = (i - 1) / sn + 1;
    for (int i = 1; i <= tot; ++i) {
        l[i] = (i - 1) * sn + 1;
        r[i] = i * sn;
    }
    r[tot] = n;
    for (int i = 1; i <= tot; ++i) {
        int cnt = 0, ans;
        for(int j = i; j <= tot; ++j) {
            for(int k = l[j]; k <= r[j]; ++k) {
                mp[a[k]]++;
                // cnt = max(cnt, mp[a[k]]);
                if(mp[a[k]] > cnt) {
                    cnt = mp[a[k]];
                    ans = a[k];
                }
                else if(mp[a[k]] == cnt) ans = min(ans, a[k]);
            }
            d[i][j] = ans;
        }
        for (int j = 1; j <= n; ++j) mp[j] = 0;
    }
    for (int i = 1; i <= tot; ++i) {
        for (int j = 1; j <= n; ++j) f[i][j] = f[i - 1][j];
        for(int j = l[i]; j <= r[i]; ++j) {
            f[i][a[j]]++;
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &Node[i].val), Node[i].id = i;
    descrete();
    prework();
    int lans = 0;
    int ll, rr;
    for (int o = 1; o <= m; ++o) {
        scanf("%d%d", &ll, &rr);
        ll = (ll + lans - 1) % n + 1;
        rr = (rr + lans - 1) % n + 1;
        if(ll > rr) swap(ll, rr);
        int ans, cnt = 0;
        if(blc[ll] == blc[rr]) {
            for (int i = ll; i <= rr; ++i) {
                mp[a[i]]++;
                if(mp[a[i]] > cnt) {
                    cnt = mp[a[i]];
                    ans = a[i];
                }
                else if(mp[a[i]] == cnt) ans = min(ans, a[i]);
            }
            printf("%d\n", src[ans]);
            lans = src[ans];
            for (int i = ll; i <= rr; ++i) mp[a[i]]--;
        }
        else {
            ans = d[blc[ll] + 1][blc[rr] - 1];
            int cnt = f[blc[rr] - 1][ans] - f[blc[ll]][ans];
            for (int i = ll; i <= r[blc[ll]]; ++i) {
                mp[a[i]]++;
                int res = f[blc[rr] - 1][a[i]] - f[blc[ll]][a[i]] + mp[a[i]];
                // ans = max(ans, res);
                if(res > cnt) {
                    cnt = res;
                    ans = a[i];
                }
                else if(res == cnt) ans = min(ans, a[i]);
            }
            for (int i = l[blc[rr]]; i <= rr; ++i) {
                mp[a[i]]++;
                int res = f[blc[rr] - 1][a[i]] - f[blc[ll]][a[i]] + mp[a[i]];
                // ans = max(ans, res);
                if(res > cnt) {
                    cnt = res;
                    ans = a[i];
                }
                else if(res == cnt) ans = min(ans, a[i]);
            }
            printf("%d\n", src[ans]);
            lans = src[ans];
            for (int i = ll; i <= r[blc[ll]]; ++i) mp[a[i]]--;
            for (int i = l[blc[rr]]; i <= rr; ++i) mp[a[i]]--;
        }
    }
    return 0;
}

10.18

P4097 [HEOI2013]Segment

说是李超线段树，但感觉用一般的维护方法也可以写，只不过常数大了一点（还是老老实实抄记了一遍模板）

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
#include <bits/stdc++.h>
#define lson k<<1
#define rson k<<1|1
#define pdi pair<double, int>
using namespace std;
int n;
const int maxn = 1e5 + 10;
const int N = 39989;
const int mod = 1e9;
int a[maxn << 2];
int cnt;
double K[maxn], b[maxn];
void add(int x_, int y_, int x__, int y__) {
	++cnt;
	if (x_ == x__) {
		K[cnt] = 0, b[cnt] = max(y_, y__);
	}
	else {
		K[cnt] = 1.0 * (y__ - y_) / (x__ - x_);
		b[cnt] = y_ - K[cnt] * x_;
	}
}
double cal(int i, int x) {
	return x * K[i] + b[i]; 
}
void change(int k, int cl, int cr, int l, int r, int u) {
	int mid = (cl + cr) >> 1;
	int rr = a[k];
	if(r < cl || l > cr) return;
	double resu = cal(u, mid);
	double resv = cal(a[k], mid);
	if(l <= cl && r >= cr) {
		if(cl == cr) {
			if(resu > resv) a[k] = u; return;
		}
		if(K[a[k]] < K[u]) {
			if(resu > resv) {
				a[k] = u;
				// 修改可能区间
				change(lson, cl, mid, l, r, rr);
			}
			else change(rson, mid + 1, cr, l, r, u);
		} else if(K[a[k]] > K[u]) {
			if(resu > resv) {
				a[k] = u;
				change(rson, mid + 1, cr, l, r, rr);
			}
			else change(lson, cl, mid, l, r, u);
		}
		else {
			if(b[u] > b[a[k]]) a[k] = u;
		} return;
	}
	change(lson, cl, mid, l, r, u);
	change(rson, mid + 1, cr, l, r, u);
}
pdi Max(pdi x, pdi y) {
	if(x.first < y.first) return y;
	if(x.first > y.first) return x;
	return x.second < y.second ? x : y;
}
pdi query(int k, int l, int r, int d) {
	if(r < d || d < l) return {0, 0};
	int mid = (l + r) >> 1;
	double res = cal(a[k], d);
	if(l == r) return {res, a[k]};
	return Max({res, a[k]}, Max(query(lson, l, mid, d), query(rson, mid + 1, r, d))); 
}
int lans = 0;
inline int pro(int x, int b) {
	return (x + lans - 1 + b) % b + 1;
}
int main() {
	scanf("%d", &n);
	int op, x_, y_, x__, y__;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &op);
		if(op == 1) {
			scanf("%d%d%d%d", &x_, &y_, &x__, &y__);
			x_ = pro(x_, N);
			y_ = pro(y_, mod);
			x__ = pro(x__, N);
			y__ = pro(y__, mod);
			if(x_ > x__) {
				swap(x_, x__);
				swap(y_, y__);
			}
			add(x_, y_, x__, y__);
			change(1, 1, N, x_, x__, cnt);
		}
		else {
			scanf("%d", &x_);
			x_ = pro(x_, N);
			printf("%d\n", lans = query(1, 1, N, x_).second);
		}
	}
	return 0;
}

10.28

CF242E XOR on Segment

按位运算，分别维护每一位就可以维护整个异或和了，属于是白给紫题

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
#include <bits/stdc++.h>
#define lson k << 1
#define rson k << 1 | 1
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 10;
struct node {
    int l, r, tag; // 该区间是否异或过1
    ll s;
}a[25][maxn * 4];
int num[maxn];
inline void pushup(int k, int c) {
    a[c][k].s = a[c][lson].s + a[c][rson].s;
    a[c][k].tag = 0;
}
void build(int k, int c, int l, int r) {
    a[c][k].l = l, a[c][k].r = r;
    if(l == r) {
        a[c][k].s = (num[l] >> (c - 1ll)) & 1ll;
        return;
    }
    int mid = (l + r) >> 1ll;
    build(lson, c, l, mid);
    build(rson, c, mid + 1, r);
    pushup(k, c);
}
void pushdown(int k, int c) {
    if(!a[c][k].tag) return;
    a[c][lson].s = a[c][lson].r - a[c][lson].l + 1 - a[c][lson].s;
    a[c][rson].s = a[c][rson].r - a[c][rson].l + 1 - a[c][rson].s;
    a[c][lson].tag ^= 1, a[c][rson].tag ^= 1;
    a[c][k].tag = 0;
}
void add(int k, int c, int l, int r) {
    if(a[c][k].l > r || a[c][k].r < l) return;
    if(a[c][k].l >= l && a[c][k].r <= r) {
        a[c][k].s = a[c][k].r - a[c][k].l + 1 - a[c][k].s;
        a[c][k].tag ^= 1;
        return;
    }
    pushdown(k, c);
    add(lson, c, l, r);
    add(rson, c, l, r);
    pushup(k, c);
}
ll query(int k, int c, int l, int r) {
    if(a[c][k].l > r || a[c][k].r < l) return 0;
    if(a[c][k].l >= l && a[c][k].r <= r) return a[c][k].s;
    pushdown(k, c);
    return query(lson, c, l, r) + query(rson, c, l, r);
}
signed main () 
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &num[i]);
    for (int i = 1; i <= 24; ++i) build(1, i, 1, n);
    int op, l, r, k;
    int m;
    scanf("%d", &m);
    while (m--) {
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1) {
            ll ans = 0;
            for (int i = 1; i <= 24; ++i) ans += query(1, i, l, r) * (1ll << (i - 1));
            printf("%lld\n", ans);
        }
        else {
            scanf("%d", &k);
            if(k == 0) continue;
            for (int i = 1; i <= 24; ++i) {
                if(k & 1) add(1, i, l, r);
                k >>= 1;
                if(!k) break;
            }
        }
    }
}

11.4

P2122 还教室

维护区间方差与平均值，实际上维护区间的和以及平方和就可以了。

另：11-04 21:16:20 洛谷AC150题纪念。

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
#include <bits/stdc++.h>
#define int long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 1e5 + 10;
struct node {
    int l, r, sum, tag, sqr;
}a[maxn << 2];
int num[maxn];
inline void pushup(int k) {
    a[k].sum = a[lson].sum + a[rson].sum;
    a[k].sqr = a[lson].sqr + a[rson].sqr;
}
void build(int k, int l, int r) {
    a[k].l = l, a[k].r = r;
    a[k].tag = 0;
    if(l == r) {
        a[k].sum = num[l];
        a[k].sqr = num[l] * num[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    pushup(k);
}
void pushtag(int k, int x) {
    a[k].sqr += a[k].sum * 2 * x + x * x * (a[k].r - a[k].l + 1);
    a[k].sum += (a[k].r - a[k].l + 1) * x;
    a[k].tag += x;
}
void pushdown(int k) {
    if(a[k].tag) {
        pushtag(lson, a[k].tag);
        pushtag(rson, a[k].tag);
        a[k].tag = 0;
    }
}
void add(int k, int l, int r, int x) {
    if(a[k].l > r || a[k].r < l) return;
    if(a[k].l >= l && a[k].r <= r) {
        pushtag(k, x);
        return;
    }
    pushdown(k);
    add(lson, l, r, x);
    add(rson, l, r, x);
    pushup(k);
}
int querysum(int k, int l, int r) {
    if(a[k].l > r || a[k].r < l) return 0;
    if(a[k].l >= l && a[k].r <= r) return a[k].sum;
    pushdown(k);
    return querysum(lson, l, r) + querysum(rson, l, r);
}
int querysqr(int k, int l, int r) {
    if(a[k].l > r || a[k].r < l) return 0;
    if(a[k].l >= l && a[k].r <= r) return a[k].sqr;
    pushdown(k);
    return querysqr(lson, l, r) + querysqr(rson, l, r);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> num[i];
    build(1, 1, n);
    int op, l, r, d;

    while(m--) {
        cin >> op >> l >> r;
        if(op == 1) {
            cin >> d;
            add(1, l, r, d);
        }
        else if(op == 2) {
            int res = querysum(1, l, r);
            if(res == 0) {
                cout << "0/1" << endl;
                continue;
            }
            int ret = __gcd(res, r - l + 1);
            cout << res / ret << '/' << (r - l + 1) / ret << endl;
        }
        else {
            int res1 = querysum(1, l, r);
            int res2 = querysqr(1, l, r);
            int ret;
            int fz = res2 * (r - l + 1) - res1 * res1;
            int fm = (r - l + 1) * (r - l + 1);
            if(fz == 0) {
                cout << "0/1" << endl;
                continue;
            }
            ret = __gcd(fz, fm);
            cout << fz / ret << '/' << fm / ret << endl;
        }
    }
    return 0;
}

11.9

P4145 上帝造题的七分钟 2 / 花神游历各国

看上去好像没法维护平方根数据结构，实际上 $10^{12}$ 内的数最多开方不到10次就成1了，遇到全为1的区间时停止修改即可。记这个最大次数为 $X$, 用线段树/树状数组维护的复杂度都是$O(Xn\log m)$

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 <bits/stdc++.h>
#define int unsigned long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 1e5 + 10;
struct node {
    int l, r, sum;
}a[maxn << 2];
int num[maxn];
inline void pushup(int k) {
    a[k].sum = a[lson].sum + a[rson].sum;
}
void build(int k, int l, int r) {
    a[k].l = l, a[k].r = r;
    if(l == r) {
        a[k].sum = num[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    pushup(k);
}
void change(int k, int l, int r) {
    if(a[k].l > r || a[k].r < l) return;
    if(a[k].r - a[k].l + 1 == a[k].sum) return;
    if(a[k].l == a[k].r) {
        a[k].sum = sqrt(a[k].sum);
        return;
    }
    change(lson, l, r);
    change(rson, l, r);
    pushup(k);
}
int query(int k, int l, int r) {
    if(a[k].l > r || a[k].r < l) return 0;
    if(a[k].l >= l && a[k].r <= r) return a[k].sum;
    return query(lson, l, r) + query(rson, l, r);
}
signed main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> num[i];
    cin >> m;
    build(1, 1, n);
    int op, l, r;
    while(m--) {
        cin >> op >> l >> r;
        if(l > r) swap(l, r);
        if(op == 0) {
            change(1, l, r);
        }
        else {
            cout << query(1, l, r) << endl;
        }
    }
    return 0;
}

11.18

P3803 【模板】多项式乘法（FFT）

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
#include <bits/stdc++.h>
#define PI acos(-1.0)
using namespace std;
// op = 1 ? DFT : IDFT
const int maxn = 3e6 + 10;
complex <double> F[maxn], G[maxn];
void fft(complex<double> f[], int n, int op) {
    if(!n) return;
    complex <double> a[n], b[n];
    for (int k = 0; k < n; ++k) {
        a[k] = f[k << 1], b[k] = f[k << 1 | 1];
    }
    fft(a, n >> 1, op), fft(b, n >> 1, op);
    complex<double> wn(cos(PI / n), sin(PI / n) * op), w(1, 0);
    for (int k = 0; k < n; ++k, w *= wn) {
        f[k] = a[k] + w * b[k], f[k + n] = a[k] - w * b[k];
    }
}
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; ++i) {
        scanf("%lf", &F[i]);
    }
    for (int i = 0; i <= m; ++i) {
        scanf("%lf", &G[i]);
    }
    m += n, n = 1;
    while(n <= m) n <<= 1; // 补足系数，保证是2的幂次

    // DFT
    fft(F, n >> 1, 1);
    fft(G, n >> 1, 1);

    for (int i = 0; i < n; ++i) F[i] *= G[i];

    // IDFT
    fft(F, n >> 1, -1);
    for (int i = 0; i <= m; ++i) {
        printf("%.0f ", fabs(F[i].real()) / n);
    }
    return 0;
}

11.21的NTT写法

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 <bits/stdc++.h>
#define int long long
#define PI acos(-1.0)
using namespace std;
// op = 1 ? DFT : IDFT
const int maxn = 3e6 + 10;
int F[maxn], G[maxn];
int r[maxn];
const int mod = 998244353;
int fpow(int a, int p) {
    int ans = 1;
    while(p) {
        if(p & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        p >>= 1;
    }
    return ans;
}

void ntt(int f[], int n, int op) {
    if(!n) return;
    for (int i = 0; i < n; ++i) {
        if(i < r[i]) swap(f[i], f[r[i]]);
    }
    for (int mid = 1; mid < n; mid <<= 1) {
        int wn = fpow(op == 1 ? 3 : 332748118, (mod - 1) / (mid << 1));
        for (int j = 0; j < n; j += (mid << 1)) {
            int w = 1;
            for (int k = 0; k < mid; ++k, w = w * wn % mod) {
                int x = f[j + k], y = w * f[j + k + mid] % mod;
                f[j + k] = (x + y) % mod;
                f[j + k + mid] = ((x - y) % mod + mod) % mod;
            }
        }
    }
}
int n, m;
signed main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 0; i <= n; ++i) {
        scanf("%lld", &F[i]);
        F[i] = (F[i] + mod) % mod;
    }
    for (int i = 0; i <= m; ++i) {
        G[i] = (G[i] + mod) % mod;
        scanf("%lld", &G[i]);
    }
    m += n, n = 1;
    int cnt = 0;
    while(n <= m) n <<= 1, cnt++; // 补足系数，保证是2的幂次
    for (int i = 0; i < n; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (cnt - 1));
    // DFT
    ntt(F, n, 1), ntt(G, n, 1);

    for (int i = 0; i < n; ++i) F[i] = (F[i] * G[i]) % mod;

    // IDFT
    ntt(F, n, -1);
    int inv = fpow(n, mod - 2);
    for (int i = 0; i <= m; ++i) {
        printf("%lld ", (F[i] * inv) % mod);
    }
    return 0;
}

11.23

P3389 【模板】高斯消元法

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int maxn = 105;
int n;
double a[maxn][maxn];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n + 1; ++j) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        int mx = i;
        // 选出该列最大系数
        for (int j = i + 1; j <= n; ++j) {
            if(fabs(a[j][i]) > fabs(a[mx][i])) {
                mx = j;
            }
        }
        for (int j = 1; j <= n + 1; ++j) {
            swap(a[i][j], a[mx][j]);
        }
        if (!a[i][i]) {
            // Solution not 
            cout << "No Solution" << endl;
            return 0;
        }
        for (int j = 1; j <= n; ++j) {
            if(j != i) {
                double tmp = a[j][i] / a[i][i];
                for (int k = i + 1; k <= n + 1; ++k) {
                    a[j][k] -= a[i][k] * tmp;
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << a[i][n + 1] / a[i][i] << endl;
    }
    return 0;
}

11.25

CF438D The Child and Sequence

类似P4145，每个点被修改的次数有限，可以适当暴力

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
#include <bits/stdc++.h>
#define lson k << 1
#define rson k << 1 | 1
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
struct node {
    int l, r, sum, mx, add;
}a[maxn << 2];
int num[maxn];
inline void pushup(int k) {
    a[k].sum = a[lson].sum + a[rson].sum;
    a[k].mx = max(a[lson].mx, a[rson].mx);
}
void build(int k, int l, int r) {
    a[k].l = l, a[k].r = r;
    if(l == r) {
        a[k].sum = num[l];
        a[k].mx = num[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    pushup(k);
}
void pushdown(int k) {
    a[lson].sum += a[k].add;
    a[rson].sum += a[k].add;
    a[lson].mx += a[k].add;
    a[rson].mx += a[k].add;
    a[lson].add += a[k].add;
    a[rson].add += a[k].add;
    a[k].add = 0;
}
void mod(int k, int l, int r, int p) {
    if(a[k].l > r || a[k].r < l) return;
    if(a[k].mx < p) return;
    if(a[k].l == a[k].r) {
        a[k].sum %= p;
        a[k].mx = a[k].sum;
        return;
    }
    pushdown(k);
    mod(lson, l, r, p);
    mod(rson, l, r, p);
    pushup(k);
}
void change(int k, int l, int x) {
    if(a[k].l > l || a[k].r < l) return;
    if(a[k].l == a[k].r) {
        a[k].sum = x;
        a[k].mx = x;
        return;
    }
    pushdown(k);
    change(lson, l, x);
    change(rson, l, x);
    pushup(k);
}
int query(int k, int l, int r) {
    if(a[k].l > r || a[k].r < l) return 0;
    if(a[k].l >= l && a[k].r <= r) {
        return a[k].sum;
    }
    pushdown(k);
    return query(lson, l, r) + query(rson, l, r);
}
signed main()
{
    int n, m;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%lld", &num[i]);
    build(1, 1, n);
    int op, l, r, x;
    while(m--) {
        scanf("%lld%lld%lld", &op, &l, &r);
        if(op == 1) {
            printf("%lld\n", query(1, l, r));
        }
        else if(op == 2) {
            scanf("%lld", &x);
            mod(1, l, r, x);
        }
        else if(op == 3) {
            change(1, l, r);
        }
    }
    return 0;
}

CF1000F One Occurrence

卡常的道路越走越远（

又是用根号算法卡 $\log$ 的 std （逃

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
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#define rint register int
using namespace std;
const int maxn = 5e5 + 10;
int n, m;
struct query {
    int l, r;
    int idx, blc;
}q[maxn];
int a[maxn];
int mp[maxn];
int pos[maxn];
int stk[maxn];
int top = 1;
inline bool cmp(const query& x, const query& y) {
    if (x.blc == y.blc) if(x.blc & 1) return x.r < y.r; else return x.r > y.r;
    else return x.l < y.l;
}
int ans[maxn];
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
    x = 0;
	char c = gc();
	while(c<'0'||c>'9') c = gc();
	while(c>='0'&&c<='9'){
		x = (x<<3)+(x<<1)+(c^48);
		c = gc();
	}
}
int main()
{
    read(n);
    for (rint i = 1; i <= n; ++i) read(a[i]);
    read(m);
    int u = (int)sqrt(n);
    for (rint i = 1; i <= m; ++i) {
        read(q[i].l);
        read(q[i].r);
        q[i].idx = i;
        q[i].blc = (q[i].l - 1) / u + 1;
    }
    sort(q + 1, q + 1 + m, cmp);
    stk[0] = 0;
    rint l = 1, r = 0;
    for (rint i = 1; i <= m; ++i) {
        while(l > q[i].l) {
            l--;
            mp[a[l]]++;
            if(mp[a[l]] == 1) {
                stk[++top] = a[l];
                pos[a[l]] = top;
            }
            else if(mp[a[l]] == 2) {
                stk[pos[a[l]]] = stk[top];
                pos[stk[top]] = pos[a[l]];
                stk[top--] = pos[a[l]] = 0;
            }
        }
        while(r < q[i].r) {
            r++;
            mp[a[r]]++;
            if(mp[a[r]] == 1) {
                stk[++top] = a[r];
                pos[a[r]] = top;
            }
            else if(mp[a[r]] == 2) {
                stk[pos[a[r]]] = stk[top];
                pos[stk[top]] = pos[a[r]];
                stk[top--] = pos[a[r]] = 0;
            }
        }
        while(l < q[i].l) {
            mp[a[l]]--;
            if(mp[a[l]] == 1) {
                stk[++top] = a[l];
                pos[a[l]] = top;
            }
            else if(mp[a[l]] == 0) {
                stk[pos[a[l]]] = stk[top];
                pos[stk[top]] = pos[a[l]];
                stk[top--] = pos[a[l]] = 0;
            }
            l++;
        }
        while(r > q[i].r) {
            mp[a[r]]--;
            if(mp[a[r]] == 1) {
                stk[++top] = a[r];
                pos[a[r]] = top;
            }
            else if(mp[a[r]] == 0) {
                stk[pos[a[r]]] = stk[top];
                pos[stk[top]] = pos[a[r]];
                stk[top--] = pos[a[r]] = 0;
            }
            r--;
        }
        ans[q[i].idx] = stk[top];
    }
    for (rint i = 1; i <= m; ++i) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

P2184 贪婪大陆

一次过，今天码力在线qwq

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 lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 1e5 + 10;
struct node {
    int l, r;
    int pre, lst;
    int tp, tl;
}a[maxn << 2];
int num[maxn];
void build(int k, int l, int r) {
    a[k].l = l, a[k].r = r;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
}
void pushup(int k) {
    a[k].pre = a[lson].pre + a[rson].pre;
    a[k].lst = a[lson].lst + a[rson].lst;
}
void pushtag (int k, int x, int y) {
    a[k].tp += x;
    a[k].pre += x;
    a[k].lst += y;
    a[k].tl += y;
}
void pushdown(int k) {
    pushtag(lson, a[k].tp, a[k].tl);
    pushtag(rson, a[k].tp, a[k].tl);
    a[k].tp = a[k].tl = 0;
}
void add(int k, int l, int r, int type) {
    if(a[k].l > r || a[k].r < l) return;
    if(a[k].l >= l && a[k].r <= r) {
        if(type == 1) a[k].pre++, a[k].tp++;
        else a[k].lst++, a[k].tl++;
        return;
    }
    pushdown(k);
    add(lson, l, r, type);
    add(rson, l, r, type);
    pushup(k);
}
int query(int k, int x, int type) {
    if(a[k].l > x || a[k].r < x) return 0;
    if(a[k].l == a[k].r) {
        if(type == 1) return a[k].pre;
        else return a[k].lst;
    }
    pushdown(k);
    return query(lson, x, type) + query(rson, x, type);
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    build(1, 0, n);
    int q, l, r;
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &q, &l, &r);
        if(q == 1) {
            add(1, l, n, 1);
            add(1, r, n, 2);
        }
        else {
            int ans = query(1, r, 1);
            ans -= query(1, l - 1, 2);
            printf("%d\n", ans);
        }
    }
    return 0;
}

11.28

P1637 三元上升子序列

维护两个树状数组

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
#include <bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn = 3e4 + 10;
int a[maxn];
int c[maxn];
int d[maxn];
int b[maxn];
map<int, int> mp;
int n;
int pos;
void add(int k, int x) {
    while(k <= pos) {
        c[k] += x;
        k += lowbit(k);
    }
}
int query(int x) {
    int ans = 0;
    while(x >= 1) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
void add2(int k, int x) {
    while(k <= pos) {
        d[k] += x;
        k += lowbit(k);
    }
}
int query2(int x) {
    int ans = 0;
    while(x >= 1) {
        ans += d[x];
        x -= lowbit(x);
    }
    return ans;
}
signed main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + 1 + n);
    b[0] = -1;
    for (int i = 1; i <= n; ++i) {
        if(b[i] != b[i - 1]) {
            mp[b[i]] = ++pos;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) add2(mp[a[i]], 1);
    for (int i = 1; i <= n; ++i) {
        add2(mp[a[i]], -1);
        int r1 = query(mp[a[i]] - 1), r2 = query2(pos) - query2(mp[a[i]]);
        ans += r1 * r2;
        add(mp[a[i]], 1);
    }
    printf("%lld\n", ans);
    return 0;
}

12.9

回新手村练练手，希望重新找回A题的快感，停止自闭……手太生了，感觉特别差…….明明没有休整几天的说（也有十来天了吧喂！）。总之，必须快点重整旗鼓。

今日目标：刷完洛谷贪心题单（整个题单就没有难题啊喂！）。

P1803 凌乱的yyy / 线段覆盖

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 <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
struct node {
    int l, r;
    bool operator < (const node &x) {
        return r < x.r;
    }
}a[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].l >> a[i].r;
    sort (a + 1, a + 1 + n);
    int ans = 1;
    int now = a[1].r;
    for (int i = 2; i <= n; ++i) {
        if (a[i].l >= now) {
            ans++;
            now = a[i].r;
        }
    }
    cout << ans << endl;
    return 0;
}

P2240 【深基12.例1】部分背包问题

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
#include <bits/stdc++.h>
using namespace std;
double ans;
const int maxn = 105;
struct node {
    int weight;
    double x; // 单位价值
    bool operator < (const node &y) {
        return x > y.x;
    }
}a[maxn];
int main()
{
    int n, t;
    cin >> n >> t;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        a[i].weight = x;
        a[i].x = 1.0 * y / x;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; ++i) {
        if (a[i].weight > t) {
            ans += a[i].x * t;
            break;
        }
        ans += a[i].x * a[i].weight;
        t -= a[i].weight;
    }
    cout << fixed << setprecision(2) << ans << endl;
    return 0;
}

P1223 排队接水

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
#include <bits/stdc++.h>
using namespace std;
const int maxn =1005;
struct node {
    int x, id;
    bool operator < (const node & y) {
        return x < y.x;
    }
}a[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) a[i].id = i, cin >> a[i].x;
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; ++i) cout << a[i].id << " ";
    cout << endl;
    double ans = 0;
    for (int i = 1; i < n; ++i) {
        ans += (n - i) * a[i].x;
    }
    ans /= n;
    cout << fixed << setprecision(2) << ans << endl;
    return 0;
}

P3817 小A的糖果

不开long long见祖宗！

我怎么就是甜蜜的改不过来？？？？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 10;
int a[maxn];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, x;
    cin >> n >> x;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] + a[i - 1] > x) {
            ans += a[i] + a[i - 1] - x;
            a[i] = x - a[i - 1];
        }
    }
    cout << ans << endl;
    return 0;
}

P1106 删数问题

删峰即可。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 255;
bool v[maxn];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    int k;
    cin >> k;
    int l = 0;
    for (int i = 1; i <= k; ++i) {
        // 去前导0
        while (v[l] || s[l] == '0') l++;
        for (int j = l; j < s.size(); ) {
            while (j < s.size() && v[j]) j++;
            int p1 = j++;
            while (j < s.size() && v[j]) j++;
            if (p1 < s.size() && (j >= s.size() || s[p1] > s[j])) {
                v[p1] = 1;
                break;
            }
        }
    }
    for (int i = l; i < s.size(); ++i) if(!v[i]) cout << s[i];
    cout << endl;
    return 0;
}

P1478 陶陶摘苹果（升级版）

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
struct node 
{
    int x, y;
    bool operator < (const node &other) {
        return y < other.y;
    }
}a[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, s;
    cin >> n >> s;
    int u, v;
    cin >> u >> v;
    int ans = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;
    sort (a + 1, a + 1 + n);
    for (int i = 1; i <= n; ++i) {
        if (a[i].x <= u + v && a[i].y <= s) {
            s -= a[i].y;
            ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}

P4447 [AHOI2018初中组]分组

蒟蒻跪了orz

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 = 1e5 + 10;
map<int, priority_queue<int, vector<int>, greater<int>>> mp;
int a[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; ++i) {
        if (mp[a[i] - 1].empty()) {
            mp[a[i]].push(1);
        }
        else {
            int r = mp[a[i] - 1].top();
            mp[a[i] - 1].pop();
            mp[a[i]].push(r + 1);
        }
    }
    int ans = 0x3f3f3f3f;
    for (auto &x : mp) {
        if (x.second.empty()) continue;
        ans = min(ans, (int)x.second.top());
    }
    cout << ans << endl;
    return 0;
}

P1094 [NOIP2007 普及组] 纪念品分组

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
bool v[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int w;
    cin >> w;
    int n;
    cin >> n;
    // int cnt = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int l = 1, r = n;
    int ans = 0;
    while (l < r) {
        while (r > l && a[l] + a[r] > w) r--;
        if (r > l) {
            ans++;
            v[l] = 1;
            v[r] = 1;
            l++;
            r--;
        }
    }
    for (int i = 1; i <= n; ++i) if(!v[i]) ans++;
    cout << ans << endl;
    return 0;
}

12.14

P3369 【模板】普通平衡树

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int cnt;
int root;
// 注意按p是小根堆
struct node {
    int l, r, size, val, p;
}a[maxn];
void pushup(int k) {
    a[k].size = 1 + a[a[k].l].size + a[a[k].r].size;
}
void rrotate(int &k) {
    int tmp = a[k].l;
    a[k].l = a[tmp].r;
    a[tmp].r = k;
    a[tmp].size = a[k].size;
    pushup(k);
    k = tmp;
}
void lrotate(int &k) {
    int tmp = a[k].r;
    a[k].r = a[tmp].l;
    a[tmp].l = k;
    a[tmp].size = a[k].size;
    pushup(k);
    k = tmp;
}
void ins(int &k, int val) {
    if (k == 0) {
        k = ++cnt;
        a[k].val = val;
        a[k].p = rand();
        a[k].size = 1;
        return;
    }
    a[k].size++;
    if (val >= a[k].val) {
        ins(a[k].r, val);
    }
    else ins(a[k].l, val);
    if (a[k].l && a[k].p > a[a[k].l].p) {
        rrotate(k);
    }
    if (a[k].r && a[k].p > a[a[k].r].p) {
        lrotate(k);
    }
    pushup(k);
}
void del(int &k, int val) {
    a[k].size--;
    if (a[k].val == val) {
        if (!a[k].l && !a[k].r) {
            k = 0;
            return;
        }
        if (!a[k].l || !a[k].r) {
            k = a[k].l + a[k].r;
            return;
        }
        if (a[a[k].l].p < a[a[k].r].p) {
            rrotate(k);
            del(a[k].r, val); return;
        }
        else {
            lrotate(k);
            del(a[k].l, val); return;
        }
    }
    if (a[k].val >= val) {
        del(a[k].l, val);
    }
    else {
        del(a[k].r, val);
    }
    pushup(k);
}
int rk(int k, int val) {
    if (!k) return 0;
    if (val > a[k].val) {
        return a[a[k].l].size + rk(a[k].r, val) + 1;
    }
    return rk(a[k].l, val);
}
int find(int k, int rnk) {
    if (rnk == a[a[k].l].size + 1) return a[k].val;
    if (rnk > a[a[k].l].size + 1) return find(a[k].r, rnk - a[a[k].l].size - 1);
    return find(a[k].l, rnk);
}
int query_pre(int k, int val) {
    if (!k) return 0;
    if (a[k].val >= val) {
        return query_pre(a[k].l, val);
    }
    int tmp = query_pre(a[k].r, val);
    if (!tmp) return a[k].val;
    return tmp;
}
int query_suf(int k, int val) {
    if (!k) return 0;
    if (a[k].val <= val) {
        return query_suf(a[k].r, val);
    }
    int tmp = query_suf(a[k].l, val);
    if (!tmp) return a[k].val;
    return tmp;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int opt, x;
    for (int i = 1; i <= n; ++i) {
        cin >> opt >> x;
        if (opt == 1) {
            ins(root, x);
        }
        else if (opt == 2) {
            del(root, x);
        }
        else if (opt == 3) {
            cout << rk(root, x) + 1 << endl;
        }
        else if (opt == 4) {
            cout << find(root, x) << endl;
        }
        else if (opt == 5) {
            cout << query_pre(root, x) << endl;
        }
        else cout << query_suf(root, x) << endl;
    }
    return 0;
}

1.17

P1878 舞蹈课

康复训练，排序规则又不写完整。

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 <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
bool type[maxn];
struct mate {
    int l, r, c;
    bool operator < (const mate & another) const{
        if (c == another.c) return l > another.l;
        return c > another.c;
    }
};
vector<mate> ans;
priority_queue<mate> q;
bool v[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = '1' + s;
    for (int i = 1; i <= n; ++i) {
        type[i] = s[i] == 'B' ? 1 : 0;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i < n; ++i) {
        if (type[i] != type[i + 1]) {
            q.push({i, i + 1, abs(a[i] - a[i + 1])});
        }
    }
    while (!q.empty()) {
        while (v[q.top().l] || v[q.top().r]) {
            if (q.empty()) {
                break;
            }
            q.pop();
        } if (q.empty()) break;
        ans.push_back(q.top());
        int l = q.top().l, r = q.top().r;
        v[q.top().l] = v[q.top().r] = 1;
        while (v[l] && l >= 1) l--;
        while (v[r] && r <= n) r++;
        q.pop();
        if (l >= 1 && r <= n && type[l] != type[r]) q.push({l, r, abs(a[l] - a[r])});
    }
    cout << ans.size() << endl;
    for (auto & x : ans) {
        cout << x.l << ' ' << x.r << endl;
    }
    return 0;
}

1.19

P1040 [NOIP2003 提高组] 加分二叉树

区间DP.

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 <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
#define int long long
using namespace std;
const int maxn = 105;
int a[maxn];
int dp[maxn][maxn]; // 从i到j的子树答案
int rt[maxn][maxn]; // 根是谁
void dfs(int l, int r) {
    // 前序：根 左 右
    if (l > r) return;
    cout << rt[l][r] << " ";
    if (l == r) return;
    dfs(l, rt[l][r] - 1);
    dfs(rt[l][r] + 1, r);
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        dp[i][i] = a[i];
        rt[i][i] = i;
    }
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            // 枚举根
            for (int j = i; j <= i + len - 1; ++j) {
                // dp[i][i + len - 1] = max(dp[i][i + len - 1], max(1ll, dp[i][j - 1]) * max(1ll, dp[j + 1][i + len - 1]) + a[j]);
                int l = max(1ll, dp[i][j - 1]);
                int r = max(1ll, dp[j + 1][i + len - 1]);
                if (l * r + a[j] > dp[i][i + len - 1]) {
                    rt[i][i + len - 1] = j;
                    dp[i][i + len - 1] = l * r + a[j];
                }
            }
        }
    }
    cout << dp[1][n] << endl;
    dfs(1, n);
    return 0;
}

P5020 [NOIP2018 提高组] 货币系统

背包

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
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
#define int long long
using namespace std;
const int maxn = 105;
int a[maxn];
bool v[25005];
int dp[(int)3e6 + 10];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int x;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            v[a[i]] = 1;
        }
        sort(a + 1, a + 1 + n);
        int ans = 0;
        int mx = a[n];
        for (int i = 1; i <= a[n]; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i - a[j] < 0) break;
                if (dp[i - a[j]]) {
                    dp[i] = 1;
                }
            }
            if (v[i] && !dp[i]) {
                dp[i] = 1;
                ans++;
            }
        }
        cout << ans << endl;
        for (int i = 1; i <= n; ++i) v[a[i]] = 0;
        for (int i = 1; i <= a[n]; ++i) dp[i] = 0;
    }
    return 0;
}