2022.11.18 模拟赛小结

2022.11.18 模拟赛小结更好的阅读体验戳此进入赛时思路T1CodeT2CodeT3CodeT4Code正解T1CodeCodeT2CodeT3T4UPD

成天写ODT，然后T2想了半天怎么维护，死活没往ODT上想，身败名裂了身败名裂了身败名裂了。。

更好的阅读体验戳此进入

赛时思路

T1

原题 LG-P1136 迎接仪式。

存在仅包含 jz $k$ 次每次交换任意位置的两个字符，最大化最终串里 jz 子串的数量，求最大值。

$80\%$ 以上的点，然后因为我写挂了。。。一遍过大样例就没拍，赛后测了一下，如果对拍一下把贪心调成我预期的贪心是应该能过一大半的。。

$80\texttt{pts} \rightarrow 10\texttt{pts}$ 。

Code


xxxxxxxxxx
120
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
// using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
int N, K;
27
int cntj(0), cntz(0);
28
int cnt2j(0), cnt2z(0);
29
int ans(0);
30
// string S;
31
basic_string < char > a, b;
32

33
int main(){
34
    freopen("string.in", "r", stdin);
35
    freopen("string.out", "w", stdout);
36
    N = read(), K = read();
37
    if(N == 1)printf("0\n"), exit(0);
38
    for(int i = 1; i <= N; ++i){
39
        char c = getchar(); while(c != 'j' && c != 'z')c = getchar();
40
        a += c;
41
    }
42
    for(auto it = a.begin(); it != a.end(); ++it){
43
        if(it == prev(a.end())){b += *it; continue;}
44
        // if(*it == 'j' && *next(it) == 'j')++cntj;
45
        // else if(*it == 'z' && *next(it) == 'z')++cntz;
46
        // else if(*it == 'z' && *next(it) == 'j')++cntz;
47
        // else
48
        if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), b += '*';
49
        else b += *it;
50
    }a.clear(); a.swap(b);
51
    for(auto it = a.begin(); it != a.end(); ++it){
52
        if(it == prev(a.end())){*it == 'j' ? ++cntj : ++cntz; continue;}
53
        if(*it == 'j' && *next(it) == 'j')++cnt2j, advance(it, 1);
54
        else if(*it == 'z' && *next(it) == 'z')++cnt2z, advance(it, 1);
55
        else if(*it == 'z' && *next(it) == 'j')++cntz;
56
        else if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1);
57
    }
58
    while(K && cnt2j && cnt2z)--cnt2j, --cnt2z, --K, ans += 2;
59
    cntj += cnt2j * 2, cntz += cnt2z * 2;
60
    ans += min({cntj, cntz, K});
61
    // for(auto it = a.begin(); it != a.end(); ++it){
62
    //     if(it == prev(a.end())){b += *it; continue;}
63
    //     // if(*it == 'j' && *next(it) == 'j')++cntj;
64
    //     // else if(*it == 'z' && *next(it) == 'z')++cntz;
65
    //     // else if(*it == 'z' && *next(it) == 'j')++cntz;
66
    //     // else
67
    //     if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), --cntj, --cntz;
68
    //     else b += *it;
69
    //     a.clear();
70
    //     a.swap(b);
71
    // }
72
    // while(K && cntj >= 1 && cntz >= 1){
73
    //     for(auto it = a.begin(); it != a.end(); ++it){
74
    //         if(it == prev(a.end())){b += *it; continue;}
75
    //         // if(*it == 'j' && *next(it) == 'j')++cntj;
76
    //         // else if(*it == 'z' && *next(it) == 'z')++cntz;
77
    //         // else if(*it == 'z' && *next(it) == 'j')++cntz;
78
    //         // else
79
    //         if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), --cntj, --cntz;
80
    //         else b += *it;
81
    //         a.clear();
82
    //         a.swap(b);
83
    //     }
84
    // }
85
    // cin >> S; 
86
    // auto lst = S.begin();
87
    // for(auto cur = next(S.begin()); cur != S.end(); ++cur, ++lst){
88
    //     if(*lst == 'j' && *cur == 'j')++cntj;
89
    //     else if(*lst == 'z' && *cur == 'z')++cntz;
90
    //     else if(*lst == 'z' && *cur == 'j')++cntz;
91
    //     else if(*lst == 'j' && *cur == 'z'){
92
    //         ++ans;
93
    //         advance(lst, 1), advance(cur, 1);
94
    //         if(cur == S.end() || lst == S.end())break;
95
    //     }
96
    // }
97
    // if(!(*prev(S.end()) == 'z' && *prev(S.end(), 2) == 'j'))
98
    //     *prev(S.end()) == 'j' ? ++cntj : ++cntz;
99
    // printf("before : %d\n", ans);
100
    // ans += min({cntj, cntz, K});
101
    printf("%d\n", ans);
102
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
103
    return 0;
104
}
105

106
template < typename T >
107
inline T read(void){
108
    T ret(0);
109
    int flag(1);
110
    char c = getchar();
111
    while(c != '-' && !isdigit(c))c = getchar();
112
    if(c == '-')flag = -1, c = getchar();
113
    while(isdigit(c)){
114
        ret *= 10;
115
        ret += int(c - '0');
116
        c = getchar();
117
    }
118
    ret *= flag;
119
    return ret;
120
}

T2

原题 51nod-2014 小朋友的笑话。

$n$ $m$ $[l, r]$ $[x - l, x + l]$ $l$ 的笑话，如果其以前听过则不继续笑，没听过则开始笑。

ODT没看出来，线段树部分分写一半发现这部分分直接暴力就能水过去，于是暴力跑路。

Code


xxxxxxxxxx
131
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
// using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MAXN (110000)
24

25
template< typename T = int >
26
inline T read(void);
27

28
int N, M;
29
bitset < 11000 > vis[11000];
30
bool laugh[11000];
31

32
// class SegTree{
33
// private:
34
//     unordered_map < int, int > tr[MAXN << 2];
35
//     int v[MAXN << 2];
36
//     basic_string < int > lz[MAXN << 2];
37
//     #define LS (p << 1)
38
//     #define RS (LS | 1)
39
//     #define MID ((gl + gr) >> 1)
40
// public:
41
//     void Pushup(int p){
42
//         for(auto son : tr[LS])tr[p][son.first] += son.second;
43
//         for(auto son : tr[RS])tr[p][son.first] += son.second;
44
//         v[p] = v[LS] + v[RS];
45
//     }
46
//     void Pushdown(int p){
47
//         lz[LS] += lz[p], lz[RS] += lz[p];
48
//         for(auto modf : lz[p]){
49
//             v[LS] -= tr[LS][modf], tr[LS][modf] = 0;
50

51
//         }
52
//     }
53
// }
54

55
int main(){
56
    freopen("child.in", "r", stdin);
57
    freopen("child.out", "w", stdout);
58
    N = read(), M = read();
59
    while(M--){
60
        int opt = read();
61
        if(opt == 1){
62
            int x = read(), idx = read(), dis = read();
63
            for(int i = max(1, x - dis); i <= min(N, x + dis); ++i){
64
                if(!vis[i][idx])vis[i][idx] = true, laugh[i] = true;
65
                else laugh[i] = false;
66
            }
67
        }else{
68
            int l = read(), r = read();
69
            int cnt(0);
70
            for(int i = l; i <= r; ++i)if(laugh[i])++cnt;
71
            printf("%d\n", cnt);
72
        }
73
    }
74
    // if(N <= 20000){
75
    //     while(M--){
76
    //         int opt = read();
77
    //         if(opt == 1){
78
    //             int x = read(), idx = read(), dis = read();
79
    //             for(int i = max(1, x - dis); i <= min(N, x + dis); ++i){
80
    //                 if(!vis[i][idx])vis[i][idx] = true, laugh[i] = true;
81
    //                 else laugh[i] = false;
82
    //             }
83
    //         }else{
84
    //             int l = read(), r = read();
85
    //             int cnt(0);
86
    //             for(int i = l; i <= r; ++i)if(laugh[i])++cnt;
87
    //             printf("%d\n", cnt);
88
    //         }
89
    //     }
90
    // }else{
91
    //     printf("qwq\n");
92
    //     exit(0);
93
    // }
94
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
95
    return 0;
96
}
97

98

99

100
template < typename T >
101
inline T read(void){
102
    T ret(0);
103
    int flag(1);
104
    char c = getchar();
105
    while(c != '-' && !isdigit(c))c = getchar();
106
    if(c == '-')flag = -1, c = getchar();
107
    while(isdigit(c)){
108
        ret *= 10;
109
        ret += int(c - '0');
110
        c = getchar();
111
    }
112
    ret *= flag;
113
    return ret;
114
}
115
/*
116
10 14
117
1 3 11 0
118
2 3 3
119
1 3 11 2
120
2 1 5
121
1 5 12 1
122
2 4 6
123
1 8 13 2
124
2 6 10
125
1 7 11 2
126
2 5 9
127
1 10 12 1
128
2 9 10
129
1 9 12 0
130
2 1 10
131
*/

T3

原题 51nod-3188 字符王国。

$10\texttt{pts}$ 的链部分分。

Code


xxxxxxxxxx
98
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template< typename T = int >
26
inline T read(void);
27

28
int N, Q;
29

30
struct Edge{
31
    Edge* nxt;
32
    int to;
33
    OPNEW;
34
}ed[210000];
35
ROPNEW(ed);
36
Edge* head[110000];
37

38
bool vis[110000];
39
basic_string < int > vised;
40

41
int main(){
42
    freopen("tree.in", "r", stdin);
43
    freopen("tree.out", "w", stdout);
44
    N = read();
45
    for(int i = 1; i <= N - 1; ++i){
46
        int s = read(), t = read();
47
        head[s] = new Edge{head[s], t};
48
        head[t] = new Edge{head[t], s};
49
    }Q = read();
50
    while(Q--){
51
        int K = read();
52
        bool flag(true);
53
        for(int k = 1; k <= K; ++k){
54
            int p = read();
55
            vis[p] = true;
56
            vised += p;
57
            for(auto i = head[p]; i; i = i->nxt)
58
                if(vis[SON]){flag = false; break;}
59
        }
60
        printf("%d\n", flag ? K - 1 : -1);
61
        for(auto p : vised)vis[p] = false;
62
        vised.clear();
63
    }
64

65
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
66
    return 0;
67
}
68

69

70

71
template < typename T >
72
inline T read(void){
73
    T ret(0);
74
    int flag(1);
75
    char c = getchar();
76
    while(c != '-' && !isdigit(c))c = getchar();
77
    if(c == '-')flag = -1, c = getchar();
78
    while(isdigit(c)){
79
        ret *= 10;
80
        ret += int(c - '0');
81
        c = getchar();
82
    }
83
    ret *= flag;
84
    return ret;
85
}
86

87
/*
88
4
89
1 3
90
2 3
91
4 3
92
4
93
2 1 2
94
3 2 3 4
95
3 1 2 4
96
4 1 2 3 4
97

98
*/

T4

原题 CF555E-Case of Computer Network。

$n$ $m$ $q$ $(s, t)$ $s$ $t$ 的无向图中每条边的定向方案。

Yes $70\texttt{pts}$ 。

Code


xxxxxxxxxx
54
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
// using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template< typename T = int >
26
inline T read(void);
27

28

29

30
int main(){
31
    freopen("network.in", "r", stdin);
32
    freopen("network.out", "w", stdout);
33
    puts(rnddd(70) ? "Yes" : "No");
34
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
35
    return 0;
36
}
37

38

39

40
template < typename T >
41
inline T read(void){
42
    T ret(0);
43
    int flag(1);
44
    char c = getchar();
45
    while(c != '-' && !isdigit(c))c = getchar();
46
    if(c == '-')flag = -1, c = getchar();
47
    while(isdigit(c)){
48
        ret *= 10;
49
        ret += int(c - '0');
50
        c = getchar();
51
    }
52
    ret *= flag;
53
    return ret;
54
}

正解

T1

$80\texttt{pts}$ 的贪心。

Code


xxxxxxxxxx
128
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
// using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
int N, K;
27
int cntj(0), cntz(0);
28
int cnt2j(0), cnt2z(0);
29
int ans(0);
30
// string S;
31
basic_string < char > a, b;
32

33
int main(){
34
    // freopen("string.in", "r", stdin);
35
    // freopen("string.out", "w", stdout);
36
    N = read(), K = read();
37
    if(N == 1)printf("0\n"), exit(0);
38
    for(int i = 1; i <= N; ++i){
39
        char c = getchar(); while(c != 'j' && c != 'z')c = getchar();
40
        a += c;
41
    }
42
    for(auto it = a.begin(); it != a.end(); ++it){
43
        if(it == prev(a.end())){b += *it; continue;}
44
        // if(*it == 'j' && *next(it) == 'j')++cntj;
45
        // else if(*it == 'z' && *next(it) == 'z')++cntz;
46
        // else if(*it == 'z' && *next(it) == 'j')++cntz;
47
        // else
48
        if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), b += '*';
49
        else b += *it;
50
    }a.clear(); a.swap(b);
51
    printf("%d %d %d %d\n", cntj, cntz, cnt2j, cnt2z);
52
    printf("curans : %d\n", ans);
53
    for(auto c : a)printf("%c", c);
54
    printf("\n");
55
    for(auto it = a.begin(); it != a.end(); ++it){
56
        if(it == prev(a.end())){*it == 'j' ? ++cntj : (*it == 'z' ? ++cntz : 0); continue;}
57
        if(*it == 'j' && *next(it) == 'j')++cnt2j, advance(it, 1);
58
        else if(*it == 'z' && *next(it) == 'z')++cnt2z, advance(it, 1);
59
        else if(*it == 'z' && *next(it) == 'j')++cntz;
60
        else if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1);
61
        else if(*it == 'j' && *next(it) == '*')++cntj, advance(it, 1);
62
        else if(*it == 'z' && *next(it) == '*')++cntz, advance(it, 1);
63
        // printf("%d %d %d %d\n", cntj, cntz, cnt2j, cnt2z);
64
    }
65
    printf("%d %d %d %d\n", cntj, cntz, cnt2j, cnt2z);
66
    while(K && cnt2j && cnt2z)--cnt2j, --cnt2z, --K, ans += 2;
67
    cntj += cnt2j * 2, cntz += cnt2z * 2;
68
    ans += min({cntj, cntz, K});
69
    // for(auto it = a.begin(); it != a.end(); ++it){
70
    //     if(it == prev(a.end())){b += *it; continue;}
71
    //     // if(*it == 'j' && *next(it) == 'j')++cntj;
72
    //     // else if(*it == 'z' && *next(it) == 'z')++cntz;
73
    //     // else if(*it == 'z' && *next(it) == 'j')++cntz;
74
    //     // else
75
    //     if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), --cntj, --cntz;
76
    //     else b += *it;
77
    //     a.clear();
78
    //     a.swap(b);
79
    // }
80
    // while(K && cntj >= 1 && cntz >= 1){
81
    //     for(auto it = a.begin(); it != a.end(); ++it){
82
    //         if(it == prev(a.end())){b += *it; continue;}
83
    //         // if(*it == 'j' && *next(it) == 'j')++cntj;
84
    //         // else if(*it == 'z' && *next(it) == 'z')++cntz;
85
    //         // else if(*it == 'z' && *next(it) == 'j')++cntz;
86
    //         // else
87
    //         if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), --cntj, --cntz;
88
    //         else b += *it;
89
    //         a.clear();
90
    //         a.swap(b);
91
    //     }
92
    // }
93
    // cin >> S; 
94
    // auto lst = S.begin();
95
    // for(auto cur = next(S.begin()); cur != S.end(); ++cur, ++lst){
96
    //     if(*lst == 'j' && *cur == 'j')++cntj;
97
    //     else if(*lst == 'z' && *cur == 'z')++cntz;
98
    //     else if(*lst == 'z' && *cur == 'j')++cntz;
99
    //     else if(*lst == 'j' && *cur == 'z'){
100
    //         ++ans;
101
    //         advance(lst, 1), advance(cur, 1);
102
    //         if(cur == S.end() || lst == S.end())break;
103
    //     }
104
    // }
105
    // if(!(*prev(S.end()) == 'z' && *prev(S.end(), 2) == 'j'))
106
    //     *prev(S.end()) == 'j' ? ++cntj : ++cntz;
107
    // printf("before : %d\n", ans);
108
    // ans += min({cntj, cntz, K});
109
    printf("%d\n", ans);
110
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
111
    return 0;
112
}
113

114
template < typename T >
115
inline T read(void){
116
    T ret(0);
117
    int flag(1);
118
    char c = getchar();
119
    while(c != '-' && !isdigit(c))c = getchar();
120
    if(c == '-')flag = -1, c = getchar();
121
    while(isdigit(c)){
122
        ret *= 10;
123
        ret += int(c - '0');
124
        c = getchar();
125
    }
126
    ret *= flag;
127
    return ret;
128
}

AC 做法：

$dp(i, j, k, 0/1)$ $i$ $j$ j $k$ 个 z，最后一位是 j 或 z，然后转移一下即可。。

Code


xxxxxxxxxx
66
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
int N, K;
27
string S;
28
int dp[510][110][110][2];
29

30
int main(){
31
    memset(dp, 0xc0, sizeof dp);
32
    dp[0][0][0][1] = 0;
33
    N = read(), K = read();
34
    cin >> S;
35
    for(int i = 1; i <= N; ++i)
36
        for(int j = 0; j <= K; ++j)
37
            for(int k = 0; k <= K; ++k)
38
                if(S.at(i - 1) == 'j'){
39
                    dp[i][j][k][0] = max(dp[i - 1][j][k][0], dp[i - 1][j][k][1]);
40
                    if(j)dp[i][j][k][1] = max(dp[i - 1][j - 1][k][0] + 1, dp[i - 1][j - 1][k][1]);
41
                }else{
42
                    dp[i][j][k][1] = max(dp[i - 1][j][k][0] + 1, dp[i - 1][j][k][1]);
43
                    if(k)dp[i][j][k][0] = max(dp[i - 1][j][k - 1][0], dp[i - 1][j][k - 1][1]);
44
                }
45
    int ans(0);
46
    for(int i = 1; i <= K; ++i)ans = max({ans, dp[N][i][i][0], dp[N][i][i][1]});
47
    printf("%d\n", ans);
48
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49
    return 0;
50
}
51

52
template < typename T >
53
inline T read(void){
54
    T ret(0);
55
    int flag(1);
56
    char c = getchar();
57
    while(c != '-' && !isdigit(c))c = getchar();
58
    if(c == '-')flag = -1, c = getchar();
59
    while(isdigit(c)){
60
        ret *= 10;
61
        ret += int(c - '0');
62
        c = getchar();
63
    }
64
    ret *= flag;
65
    return ret;
66
}

T2

两只 ODT，一只维护颜色状态，一只维护小朋友状态，随便写写就过了。

Code


xxxxxxxxxx
119
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template< typename T = int >
23
inline T read(void);
24

25
int N, M;
26

27
struct Node{
28
    int l, r;
29
    mutable bool val;
30
    friend const bool operator < (const Node &a, const Node &b){
31
        return a.l < b.l;
32
    }
33
};
34

35
class ODT{
36
private:
37
    #define SIZ(it) (it->r - it->l + 1)
38
    set < Node > tr;
39
public:
40
    pair < set < Node >::iterator, bool > Insert(Node x){return tr.insert(x);}
41
    set < Node >::iterator Split(int p){
42
        auto it = tr.lower_bound(Node{p});
43
        if(it != tr.end() && it->l == p)return it;
44
        --it;
45
        int l = it->l, r = it->r;
46
        bool val = it->val;
47
        tr.erase(it);
48
        Insert(Node{l, p - 1, val});
49
        return Insert(Node{p, r, val}).first;
50
    }
51
    void Assign(int l, int r, bool val){
52
        auto itR = Split(r + 1), itL = Split(l);
53
        tr.erase(itL, itR);
54
        Insert(Node{l, r, val});
55
    }
56
    int Query(int l, int r){
57
        int ret(0);
58
        auto itR = Split(r + 1), itL = Split(l);
59
        for(auto it = itL; it != itR; ++it)ret += SIZ(it) * it->val;
60
        return ret;
61
    }
62
}odt;
63

64
class ODT_COL{
65
private:
66
    set < Node > tr;
67
public:
68
    pair < set < Node >::iterator, bool > Insert(Node x){return tr.insert(x);}
69
    set < Node >::iterator Split(int p){
70
        auto it = tr.lower_bound(Node{p});
71
        if(it != tr.end() && it->l == p)return it;
72
        --it;
73
        int l = it->l, r = it->r;
74
        bool val = it->val;
75
        tr.erase(it);
76
        Insert(Node{l, p - 1, val});
77
        return Insert(Node{p, r, val}).first;
78
    }
79
    void Modify(int l, int r){
80
        auto itR = Split(r + 1), itL = Split(l);
81
        for(auto it = itL; it != itR; ++it){
82
            if(!it->val)it->val = true, odt.Assign(it->l, it->r, true);
83
            else odt.Assign(it->l, it->r, false);
84
        }
85
    }
86
}odt_col[110000];
87

88
int main(){
89
    N = read(), M = read();
90
    odt.Insert(Node{1, N, false});
91
    for(int i = 1; i <= 101000; ++i)odt_col[i].Insert(Node{1, N, false});
92
    while(M--){
93
        int opt = read();
94
        if(opt == 1){
95
            int x = read(), idx = read(), dis = read();
96
            odt_col[idx].Modify(max(1, x - dis), min(N, x + dis));
97
        }else{
98
            int l = read(), r = read();
99
            printf("%d\n", odt.Query(l, r));
100
        }
101
    }
102
    return 0;
103
}
104

105
template < typename T >
106
inline T read(void){
107
    T ret(0);
108
    int flag(1);
109
    char c = getchar();
110
    while(c != '-' && !isdigit(c))c = getchar();
111
    if(c == '-')flag = -1, c = getchar();
112
    while(isdigit(c)){
113
        ret *= 10;
114
        ret += int(c - '0');
115
        c = getchar();
116
    }
117
    ret *= flag;
118
    return ret;
119
}

T3

咕咕咕。

T4

感觉可以做一做，题还挺有意思的，这两天要是有时间就来补一下，没时间的话就 NOIP 没退役回来补。

UPD

update-2022_11_18 初稿