关于比赛#

本届 SCIE 1024 程序员节活动由 M&CS Club 和 SCIE MLxAI 两个社团联合举办，设有两条赛道，算法和机器学习。我参加了算法的比赛，AK并取得了第二的成绩~

此次比赛从周五下午的八点开始，持续两天。可以说时间非常充足了

比赛题目pdf可点击此处下载

题目思路#

以下是我的解题思路和对题目评价/吐槽（有些比较简单的就写得比较少）

Enjoy~

CR(字典序) : Alex Liu, Allen Xu, Alvin, CQR, Tiger Shu

A~D#

水题略

E (T5)#

结合了课内FDE Cycle的模拟题，让人眼前一亮。但测试样例有点少，对于循环次数和报错 CRASH 的说明不够清晰，debug到自闭😭

F (T6)#

一道搜索题。用双向BFS优化了下速度，写了个简单的哈希表来标记已访问的图


8 collapsed lines
1
#include<bits/stdc++.h>
2
using namespace std;
3

4
struct grid{
5
    int grid[3][3];
6
    bool side;
7
};
8

9
int prime[9] = {2,3,5,7,11,13,17,19,23}; // Hash
10
int hash_grid(grid x){
11
    unsigned long long res = 0;
12
    for(int i=0;i<3;i++){
13
        for(int j=0;j<3;j++){
14
            res += prime[i*3+j]*x.grid[i][j];
15
        }
16
    }
17
    return res % 114514;
18
}
98 collapsed lines
19

20
struct node{
21
    grid x;
22
    vector<int> o;
23
};
24

25
vector<node> visited[114514];
26
queue<node> ss, ee;
27

28
bool comp(grid a, grid b){
29
    bool res = false;
30
    for(int i=0;i<3;i++){
31
        for(int j=0;j<3;j++){
32
            if(a.grid[i][j] != b.grid[i][j])return false;
33
        }
34
    }
35
    return true;
36
}
37

38
bool searched(node x){
39
    int hashed = hash_grid(x.x);
40
    if(empty(visited[hashed]))return false;
41
    for(int i=0;i<visited[hashed].size();i++){
42
        if(comp(x.x, visited[hashed][i].x)){
43
            return true;
44
        }
45
    }
46
    return false;
47
}
48

49
node searched_grid(node x){
50
    int hashed = hash_grid(x.x);
51
    for(int i=0;i<visited[hashed].size();i++){
52
        if(comp(x.x, visited[hashed][i].x)){
53
            return visited[hashed][i];
54
        }
55
    }
56
}
57

58
void search(node x){
59
    visited[hash_grid(x.x)].push_back(x);
60
}
61

62
int step[4][2] = {{0,0},{0,1},{1,0},{1,1}};
63
node spin(node x, int opt){
64
    int i = step[opt][0];
65
    int j = step[opt][1];
66
    int cache = x.x.grid[i][j];
67
    x.x.grid[i][j] = x.x.grid[i+1][j];
68
    x.x.grid[i+1][j] = x.x.grid[i+1][j+1];
69
    x.x.grid[i+1][j+1] = x.x.grid[i][j+1];
70
    x.x.grid[i][j+1] = cache;
71
    return x;
72
}
73

74
node spinrev(node x, int opt){
75
    int i = step[opt][0];
76
    int j = step[opt][1];
77
    int cache = x.x.grid[i][j];
78
    x.x.grid[i][j] = x.x.grid[i][j+1];
79
    x.x.grid[i][j+1] = x.x.grid[i+1][j+1];
80
    x.x.grid[i+1][j+1] = x.x.grid[i+1][j];
81
    x.x.grid[i+1][j] = cache;
82
    return x;
83
}
84

85
void output_node(node x){
86
    cout<<x.x.side<<":";
87
    for(int i=0;i<x.o.size();i++)cout<<x.o[i]<<',';
88
    cout<<endl;
89
    for(int i=0;i<3;i++){
90
        for(int j=0;j<3;j++){
91
            cout<<x.x.grid[i][j]<<' ';
92
        }
93
        cout<<endl;
94
    }
95
    cout<<"-------"<<endl;
96
}
97

98
string code = "ABCDXXXXXX";
99
int main(){
100
    node start;
101
    for(int i=0;i<3;i++){
102
        for(int j=0;j<3;j++){
103
            start.x.grid[i][j] = i*3+j+1;
104
        }
105
    }
106
    start.x.side = true;
107

108
    node end;
109
    for(int i=0;i<3;i++){
110
        for(int j=0;j<3;j++){
111
            cin>>end.x.grid[i][j];
112
        }
113
    }
114
    end.x.side = false;
115
    ss.push(start);ee.push(end);
116

117
    vector<node> ans;
118
    bool STOP = false;
119
    int count = 0;
120

121
    while(!STOP){ // BFS
48 collapsed lines
122
        node s_top = ss.front(); // From the start
123
        ss.pop();
124
        for(int opt=0;opt<4;opt++){
125
            node cc = spin(s_top, opt);
126
            cc.o = s_top.o;
127
            cc.o.push_back(opt);
128

129
            if(searched(cc)){
130
                node awa = searched_grid(cc);
131
                if(awa.x.side == true){ // Same side
132
                    continue;
133
                }else{ /////ANSWER!!
134
                    ans.push_back(cc);
135
                    ans.push_back(awa);
136
                    STOP = true;
137
                    break;
138
                }
139
            }
140
            search(cc);
141
            ss.push(cc);
142
        }
143

144
        if(STOP)break;
145

146
        node e_top = ee.front(); // From the end
147
        ee.pop();
148

149
        for(int opt=0;opt<4;opt++){
150
            node cc = spinrev(e_top, opt); // Spin in reverse direction
151
            cc.o = e_top.o;
152
            cc.o.push_back(opt);
153

154
            if(searched(cc)){
155
                node awa = searched_grid(cc);
156
                if(awa.x.side == false){ // Same side
157
                    continue;
158
                }else{ /////ANSWER!!
159
                    ans.push_back(awa);
160
                    ans.push_back(cc);
161
                    STOP = true;
162
                    break;
163
                }
164
            }
165
            search(cc);
166
            ee.push(cc);
167
        }
168

169
        if(STOP)break;
170
    }
11 collapsed lines
171

172
    cout<<"YES"<<endl;
173
    for(int i=0;i<ans[0].o.size();i++){
174
        cout<<code[ans[0].o[i]];
175
    }
176
    for(int i=ans[1].o.size()-1;i>=0;i--){
177
        cout<<code[ans[1].o[i]];
178
    }
179
    cout<<endl;
180

181
    return 0;
182
}

G (T7)#

刚开始看到有图以为这也是一道搜索题，写了个深搜，TLE之后就去做别的题了。后面才发现其实有更巧妙的解法

考虑一个 $k$ ，使得所有边权包含 $2^k$ 的边可以让起点和终点联通（包含：指 $w\&2^k=1$ ）。那么，当 $k$ 取最大时，最终答案的路径一定取自这些包含 $2^k$ 的边。证明如下：

因为结果是按位与出来的，不连通就意味着按位与后为0，取不到这一位，所以答案一定不来自包含大于 $2^k$ 的边。而如果答案来自包含小于 $2^k$ 的边，那么它们所构成的答案肯定不包含 $2^k$ ，就会比我们用包含 $2^k$ 的边所构建出的答案更小，不满足最大化

所以，我们可以从最高位往下找 $k$ 。每次找到一个可以让起点和终点联通的边时，删除其他所有的边，只保留包含 $2^k$ 的边。记录一路上符合条件的 $2^k$ 的和，我们就可以得到最终的答案

判断是否联通的话可以使用并查集。每次初始化后添加没有被删除的边，然后就可以判断起点和终点是否被联通


51 collapsed lines
1
#include<bits/stdc++.h>
2
using namespace std;
3
#define MAX 200009
4
#define int long long
5

6
int n, m;
7
int valid[MAX];
8

9
struct line{
10
    int from;
11
    int to;
12
    int val;
13
}lines[MAX];
14
int lines_tot;
15

16

17
void pushline(int a, int b, int val){
18
    lines[lines_tot].from = a;
19
    lines[lines_tot].to = b;
20
    lines[lines_tot].val = val;
21
    valid[lines_tot] = true;
22
    lines_tot++;
23
}
24

25
int bcj[MAX];
26

27
void bcj_init(){
28
    for(int j=0;j<=n;j++){
29
        bcj[j] = j;
30
    }
31
}
32

33
int bcj_find(int k){
34
    if(bcj[k] == k)return k;
35
    bcj[k] = bcj_find(bcj[k]);
36
    return bcj[k];
37
}
38

39
void bcj_merge(int a, int b){
40
    a = bcj_find(a); b = bcj_find(b);
41
    bcj[a] = b;
42
}
43

44
signed main(){ // n>300
45
    cin>>n>>m;
46
    for(int i=0;i<m;i++){
47
        int a,b,val;
48
        cin>>a>>b>>val;
49
        pushline(a,b,val);
50
    }
51

52
    int ans = 0;
53
    for(int k=30;k>=0;k--){
54
        bcj_init();
55
        for(int i=0;i<lines_tot;i++){
56
            if(valid[i]&&(lines[i].val & (1<<k))){
57
                bcj_merge(lines[i].from, lines[i].to);
58
            }
59
        }
60
        if(bcj_find(1) == bcj_find(n)){ // If available
61
            ans += (1<<k);
62
            for(int i=0;i<lines_tot;i++){
63
                if(!(lines[i].val & (1<<k))){
64
                    valid[i] = false; // Disable the edge
65
                }
66
            }
67
        }
68
    }
69
    cout<<ans;
70
    return 0;
71
}

H (T8)#

一道很板子的树形dp

对于每棵子树，我们都可以分为两种情况：它的祖先没有进行翻转和进行了翻转（翻转：指操作2，翻转子树）（如果偶数个祖先都翻转了，则视为没有翻转，奇数同理）。所以我们可以在每个节点维护两个值 ans[0] 和 ans[1] ，分别代表在它的祖先不翻转和翻转的情况下，这棵子树需要多少次操作才能让这个子树都变为正常

也就是说：

对于叶子节点来说，如果祖先没有翻转 ans[0] ，那么当它被损坏时操作次数为1，否则为0. 如果祖先翻转了 ans[1] ，那么就反过来

对于非叶子节点来说，我们可以分类讨论一下

记我自身的状态为 status（损坏为0，正常为1）,也就是说我没被祖先翻转的操作次数为 !status ，被翻转后的操作次数为 status ，则

祖先没有翻转（求 ans[0] ）：
- 我不翻转，结果为我改变自己的操作次数 !status ，加上子节点们不翻转 ans[0] 的操作次数
- 我翻转，结果为我翻转后改变自己的操作次数 status ，加上子节点们翻转 ans[1] 的操作次数，再加上我翻转产生的操作次数1
- 最后， ans[0] 为两者的最小值
祖先翻转了（求 ans[1] ）：
- 我不翻转，结果为祖先翻转后我改变自己的操作次数 status ，加上子节点们翻转 ans[1] 的操作次数
- 我翻转，两个翻转产生的效果抵消，结果为我改变自己的操作次数 !status ，加上子节点们不翻转 ans[0] 的操作次数，再加上我翻转产生的操作次数1
- 最后， ans[1] 为两者的最小值

后序遍历整个树，从下到上更新每个节点的ans，最后的答案就为根节点不翻转 ans[0] 和根节点翻转 ans[1] 加1的最小值

Talk is cheap, show me the code.


9 collapsed lines
1
#include<bits/stdc++.h>
2
using namespace std;
3
#define MAX 100009
4

5
struct node{
6
    vector<int> sons;
7
    int ans[2];
8
}tree[MAX];
9

10
bool status[MAX];
11
void dp(int k){
12
    // Leaf
13
    if(tree[k].sons.empty()){
14
        tree[k].ans[0] = !status[k];
15
        tree[k].ans[1] = status[k];
16
        return;
17
    }
18
    // Not Leaf
19
    int tot = 0;
20
    int tot_inv = 0;
21
    for(int i = 0; i < tree[k].sons.size(); i ++){
22
        dp(tree[k].sons[i]);
23
        tot += tree[tree[k].sons[i]].ans[0];
24
        tot_inv += tree[tree[k].sons[i]].ans[1];
25
    }
26
    tree[k].ans[0] = min(!status[k] + tot, status[k] + tot_inv + 1);
27
    tree[k].ans[1] = min(status[k] + tot_inv, !status[k] + tot + 1);
28
}
13 collapsed lines
29

30
int main(){
31
    int n;
32
    cin>>n;
33
    for(int i = 1;i <= n; i++){
34
        cin>>status[i];
35
    }
36

37
    for(int i = 1; i < n; i ++){
38
        int a, b;
39
        cin>>a>>b;
40
        tree[a].sons.push_back(b);
41
    }
42

43
    dp(1);
44

45
    cout<<min(tree[1].ans[0], tree[1].ans[1]+1); // Answer
46
    return 0;
47
}

I (T9)#

3操作本质上是对x, y上的状态进行反转，总和不变

反转后原本的放置地雷变为删除地雷，删除地雷变为放置地雷。注意如果原本没有雷的情况下不能删除，有雷的情况下无法放置

而和的话，对于放置操作，则要添加这个雷周围的空位的数量，删除周围雷的数量（挡住了它的一个格子）。如果是删除的话，删除周围空位的数量后，也需要考虑周围雷的数量，重新加到和里面（释放一个格子给周围的雷）

对于雷的存储和查找，我维护了一个动态的二维数组。存储是线性复杂度，更常用的查找只有对数复杂度

注：erfen 指普通的二分，找不到返回-1。kind_erfen 指找到第一个大于此数的位置


68 collapsed lines
1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ull unsigned long long
4
int n, m;
5
int x, y;
6
bool inverted = false;
7
bool current = false;
8
ull ans;
9

10
vector<int> dataa[1000009];
11
vector<bool> exists[1000009];
12

13
short erfen(int val, int row){ // return -1 if not found
14
    int mid;
15
    int l = 0, r = dataa[row].size();
16

17
    while(l<r){
18
        mid = (l+r)>>1;
19
        if(dataa[row][mid] >= val){
20
            r = mid;
21
        }
22
        else{
23
            l = mid + 1;
24
        }
25
    }
26
    if(l >= dataa[row].size() || dataa[row][l] != val){
27
        return -1;
28
    }
29
    return l;
30
}
31

32
short kind_erfen(int val, int row){ // return value greater than
33
    int mid;
34
    int l = 0, r = dataa[row].size();
35

36
    while(l<r){
37
        mid = (l+r)>>1;
38
        if(dataa[row][mid] >= val){
39
            r = mid;
40
        }
41
        else{
42
            l = mid + 1;
43
        }
44
    }
45
    return l;
46
}
47

48

49
bool valid(int x, int y){
50
    if(x<0||y<0||x>=n||y>=n)return false;
51
    return true;
52
}
53

54
bool query(int x, int y){
55
    if(!valid(x, y)){
56
        return false;
57
    }
58
    int pos = erfen(y, x);
59
    if(pos == -1){
60
        return false;
61
    }
62
    if(exists[x][pos] == false){
63
        return false;
64
    }
65
    return true;
66

67
}
68

69
void push(int x, int y){
70
    short pos = kind_erfen(y, x);
71
    dataa[x].push_back(0);
72
    exists[x].push_back(false);
73
    for(int i = dataa[x].size()-1; i > pos ; i--){
74
        dataa[x][i] = dataa[x][i-1];
75
        exists[x][i] = exists[x][i-1];
76
    }
77
    dataa[x][pos] = y;
78
    exists[x][pos] = true;
79
}
80

81
void pop(int x, int y){
82
    int pos = erfen(y, x);
83
    exists[x][pos] = false;
84
}
85

86
short step[8][2] = {{1,-1},{1,0},{1,1},{0,-1},{0,1},{-1,-1},{-1,0},{-1,1}};
87
void contribute(int x, int y){
88
    for(int k=0;k<8;k++){
89
        x += step[k][0]; y += step[k][1];
90
        if(valid(x, y)){
91
            bool ouo = query(x, y);
92
            ans += (!query(x, y))*(current?-1:1) + (query(x, y))*(current?1:-1);
93
        }
94
        x -= step[k][0]; y -= step[k][1];
95
    }
96
}
62 collapsed lines
97

98
void rr(int x, int y){
99
    if(current){
100
        pop(x, y);
101
    }
102
    else{
103
        push(x, y);
104
    }
105
    contribute(x, y);
106
}
107

108
inline void add(int x, int y){
109
    current = query(x, y);
110
    if(inverted && !current || !inverted && current){
111
        return; // No change
112
    }
113
    rr(x, y);
114
}
115

116
inline void remove(int x, int y){
117
    current = query(x, y);
118
    if(inverted && current || !inverted && !current){
119
        return; // No change
120
    }
121
    rr(x, y);
122
}
123

124
inline void reverse(int x, int y){
125
    current = query(x, y);
126
    rr(x, y);
127
}
128

129
int main(){
130
    cin>>n>>m;
131
    while(m--){
132
        int opt;
133
        cin>>opt;
134
        switch (opt){
135
            case 1:{
136
                cin>>x>>y;
137
                x--;y--;
138
                add(x, y);
139
            }break;
140
            case 2:{
141
                cin>>x>>y;
142
                x--;y--;
143
                remove(x, y);
144
            }break;
145
            case 3:{
146
                cin>>x>>y;
147
                x--;y--;
148
                inverted = !inverted;
149
                reverse(x, y);
150
            }break;
151
            case 4:{
152
                cout<<ans<<endl;
153
            }break;
154
            default:break;
155
        }
156
    }
157
    return 0;
158
}

J (T10)#

博弈论，在 $m \geq 32$ 后开始以八行为一组循环。有一个20以后的组合比较难想，最后写了个模拟把这个爆出来了

不过多评价，这种题就要享受自己构建可行方案解题的乐趣（嗯嗯）

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
int remainder[9] = {0, 0, 0, 4, 4, 4, 6, 7};
5

6
signed main(){
7
    int T;
8
    cin>>T;
9
    while(T--){
10
        int a;
11
        cin>>a;
12
        cout<<(remainder[a%8] + (a / 8) * 4  - 2*(a%8==7&&a>10) - (a>=30&&a%8==6))<<endl;
13
    }
14
    return 0;
15
}

K (T11)#

从第 i 堆卡牌中进行 j 次抽取操作所贡献的能力值相当于求出从 1 到 j+1 的和并减去其中的最小值。所以我们可以预先计算出这个贡献的能力值 chooce[i][j]

从第一堆卡牌开始，考虑从第0堆到第 i 堆中抽取 card 个卡片可以取得的最大能力值 dp[i][card] 。我们在第 i 堆拿 num 个卡片，在第 0 到 i-1 堆拿 card-num 个卡片的话，所产生的能力值就为 dp[i-1][card-num] + choose[i][num]。从0到n-1动态规划，答案为 dp[n-1][...] 中的最大值


10 collapsed lines
1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int unsigned long long
4
int n, m, k;
5
int datas[300][3000];
6
int choose[300][3000];
7
int dp[300][3000];
8
signed main(){
9
    cin>>n>>m>>k;
10

11
    for(int i=0;i<n;i++){
12
        int min_val = 114514;
13
        int tot = 0;
14
        for(int j=0;j<m;j++){
15
            cin>>datas[i][j];
16
            min_val = min(datas[i][j], min_val);
17
            tot += datas[i][j];
18

19
            if(j>=1)
20
            choose[i][j] = tot - min_val;
21
            dp[i][j] = choose[i][j];
22
            if(j==m-1){
23
                choose[i][m] = tot;
24
                dp[i][m] = tot;
25
            }
26
        }
27
    }
28

29
    for(int i = 1; i < n;i++){
30
        for(int card = 0; card <= k; card ++){
31
            for(int num = 0; num <= card && num <= m; num ++){
32
                dp[i][card] = max(dp[i-1][card-num]+choose[i][num], dp[i][card]);
33
            }
34
        }
35
    }
8 collapsed lines
36

37
    int res=0;
38
    for(int i=0;i<=k;i++){
39
        res = max(res, dp[n-1][i]);
40
    }
41
    cout<<res<<endl;
42
    return 0;
43
}

L (T12)#

乍一看好像没什么头绪，我们可以一步一步分析

Step 1#

如果题目的数据都是单调递增的话就很好了，所有的类型2的结果都是0。但如果数据有一段递减的段落的话，我们希望它通过最少次数的翻倍操作达成单调不递减。那么它所达成的单调不递减序列中一个元素一定在前一个元素到其两倍的范围之内，也就是说 $a_{i-1} \leq a_{i} < 2a_{i-1}$ 。这样的数组称为平滑的

对于一个数组 a ，我们可以事先就构建出一个描述每个元素需要乘多少次2才能让整个数组 a 平滑的数组 b，之后每次查询的时候只用把每个元素所需要的次数 b[i] 相加就可以了

翻倍操作相当于减少这个元素所需要的翻倍次数，所以就把对应的 b 减去一

这是我刚开始的想法， ~~但第二个测试数据没过（。~~ 后来发现虽然平滑的序列一定单调不递减，但单调不递减的序列不一定平滑。换句话说，我们可以用比构造平滑序列更少的次数来让序列不递减

我们会发现，一个递增的序列（也就是 b 递减）不需要参与计算。也就是说，我们要刨除序列中 b 递减的部分，只保留增长的部分。于是，我们可以从头开始记录 b[l] 到 b[i] 的最小值。用当前的 b[i] 剪掉这个最小值，得到的差累加起来就是最终的答案。图形化表示就是这样的：

T12

我可能说的有一点绕（逃）。Anyway，在这里附上出题人 Allen 大佬更为严谨的证明过程 (=^^) /

为了方便计数，我们定义第 $i$ 个数乘2的次数为 $e_i \in \mathbb{Z}_{\geq 0}$

询问的目标是
$\min \sum^r_{i=l+1}e_i \quad \mathrm{s.t.} \quad a_i \times 2^{e_i} \leq a_{i+1} \times 2^{e_{i+1}} \quad (\forall i \in [l, r-1])$
把相邻约束用指数差线性化。定义
$c_i = \left\lceil \log_2 \frac{a_i}{a_{i-1}} \right\rceil \in \mathbb{Z} \quad (i \in [2, n])$
则
$a_i \times 2^{e_i} \leq a_{i+1} \times 2^{e_{i+1}} \Leftrightarrow e_{i+1} - e_i \geq c_i$
于是目标函数可被重写为
$\min \sum^r_{i=l+1} e_i \quad \mathrm{s.t.} \quad e_{i+1} - e_{i} \geq c_i, \quad e_i \geq 0$
令前缀和
$b_k = \sum^k_{i=1} c_i$
容易得到我们最后的结论
$\mathrm{Ans} (l, r) = \sum^r_{k=l+1} \left( b_k - \min_{t \in [l+1, k]} b_t \right)$
（略有改动）

他的结论最小值是从 l+1 开始算，而我的是从 l 开始算。~~不过我也懒得推为什么了大概意思差不多~~

总之！ 我们现在只需要算出每个元素 $b_i$ 减去它之前元素的最小值 $\min b_k, \enspace l\leq k<i$ 的和就可以了。

Step 2#

剩下的话，我开了一个线段树维护 $b$ 的从 $l$ 到 $r$ 的最小值 min，和 sumr 还有答案 summ ，类似于这样：

Step 2_1

~~（灵魂画手）~~

最小值和总和的线段树求解比较简单就不赘述了。summ 的意思是在此区间进行查询操作 2 所返回的结果

如果它的查询区间正好和线段树的区间重合，那就很简单了，直接返回 summ ，如果没有，我们需要把这些答案累加起来，并加上一个偏移

偏移为当区间左侧的最小值是 val 的时候本区间还需要加多少操作次数，由 bias() 这个函数求出。他会找到 val 与这个区间的交点，并用 (r-l+1)*val 的长方形剪掉 summ 和 sumr 的面积（也就是蓝色和橙色的面积），从而求得图中深蓝色的 bias

Step 2_2

查询操作或者 summ 的更新就是靠计算偏移来进行的。用左边区间的最小值给右边区间做偏移，最后汇总得到答案

求偏移的时间复杂度是一个 $\log$ ，再算上查询的 $\log$ ，总的时间复杂度为 $O(n\log^2 n)$

这道题算是这两年1024比赛最难的了（）非常考验选手对问题进行抽象概括，识别pattern，考虑边界情况，最终代码实现的能力（出题组太强了呜呜呜）

以及代码：


31 collapsed lines
1
#include<bits/stdc++.h>
2
using namespace std;
3

4
#define int long long
5
#define inf 9223372036854775807
6
#define ls treee[k].lson
7
#define rs treee[k].rson
8
#define mid ((l+r)>>1)
9
#define MAX 100009
10

11
int n,q,a[MAX];
12
int b[MAX];
13

14
struct node{
15
    int lson, rson;
16
    int minn, summ;
17
    int sumr;
18
}treee[2*MAX];
19
int ttop;
20

21

22
int inittree(int l, int r){
23
    ttop++;
24
    int k = ttop;
25
    if(l==r)return k;
26
    ls = inittree(l,mid);
27
    rs = inittree(mid+1, r);
28
    return k;
29
}
30

31

32
int bias(int k, int l, int r, int val){
33
    if(l==r){
34
        return (treee[k].minn >= val) ? (treee[k].minn - val) : 0;
35
    }
36
    if(treee[k].minn >= val){
37
        return (treee[k].sumr - treee[k].summ) - (r-l+1)*val;
38
    }
39
    if(treee[ls].minn <= val){
40
        int bb = bias(ls, l, mid, val);
41
        return bb ;
42
    }else{
43
        int aa = (treee[ls].sumr - treee[ls].summ) - (mid-l+1)*val + bias(rs, mid+1, r, val) - bias(rs, mid+1, r, treee[ls].minn);
44
        return aa;
45
    }
46
}
49 collapsed lines
47

48
void buildtree(int k, int l, int r){
49
    if(l==r){
50
        treee[k].minn = b[l];
51
        treee[k].sumr = b[l];
52
        return;
53
    }
54
    buildtree(ls, l, mid);
55
    buildtree(rs, mid+1, r);
56

57
    treee[k].minn = min(treee[ls].minn, treee[rs].minn);
58
    treee[k].summ = treee[ls].summ + treee[rs].summ;
59
    treee[k].sumr = treee[ls].sumr + treee[rs].sumr;
60
    treee[k].summ += bias(rs, mid+1, r, treee[ls].minn);
61
}
62

63
void printtree(int k, int l, int r){
64
    cout<<"---"<<endl;
65
    cout<<k<<','<<l<<','<<r<<endl;
66
    cout<<treee[k].minn<<','<<treee[k].sumr<<','<<treee[k].summ<<endl;
67
    cout<<"---"<<endl;
68
    if(l!=r){
69
        printtree(ls, l, mid);
70
        printtree(rs, mid+1, r);
71
    }
72
}
73

74
void minuss(int k, int l, int r, int pos){
75
    if(pos < l || pos > r){
76
        return;
77
    }
78
    if(l==r){
79
        treee[k].minn--;
80
        treee[k].sumr--;
81
        return;
82
    }
83
    minuss(treee[k].lson, l, mid, pos);
84
    minuss(treee[k].rson, mid+1, r, pos);
85

86
    treee[k].minn = min(treee[ls].minn, treee[rs].minn);
87
    treee[k].summ = treee[ls].summ + treee[rs].summ;
88
    treee[k].sumr = treee[ls].sumr + treee[rs].sumr;
89
    treee[k].summ += bias(rs, mid+1, r, treee[ls].minn);
90
}
91

92
struct query_node{
93
    int minn, summ;
94
};
95

96
query_node querysum(int k, int l, int r, int ll, int rr, int bb){
97
    if(l > rr || r < ll){
98
        query_node res;
99
        res.minn = bb;
100
        res.summ = 0;
101
        return res;
102
    }
103
    if(l >= ll && r <= rr){
104
        query_node res;
105
        res.minn = min(bb, treee[k].minn);
106
        res.summ = treee[k].summ;
107
        if(bb != inf){
108
            res.summ += bias(k, l, r, bb);
109
        }
110
        return res;
111
    }
112
    query_node lres = querysum(ls, l, mid, ll, rr, bb);
113
    query_node rres = querysum(rs, mid+1, r, ll, rr, min(bb, lres.minn));
114
    query_node res;
115
    res.minn = min(bb, rres.minn);
116
    res.minn = min(res.minn, lres.minn);
117
    res.summ = lres.summ + rres.summ;
118
    return res;
119
}
42 collapsed lines
120

121
signed main(){
122
    cin>>n>>q;
123
    inittree(1, n);
124
    for(int i=1;i<=n;i++){
125
        cin>>a[i];
126
    }
127

128
    b[1] = 0;
129
    for(int i=2;i<=n;i++){
130
        b[i] = b[i-1];
131
        if(a[i] > a[i-1]){
132
            int ovo = 0;
133
            while(a[i-1] * (1<<ovo) <= a[i]){ ovo++;}
134
            ovo--;
135
            b[i] -= ovo;
136
        }
137
        else if(a[i] < a[i-1]){
138
            int ovo = 0;
139
            while(a[i] * (1<<ovo) < a[i-1]) ovo++;
140
            b[i] += ovo;
141
        }
142
    }
143

144
    buildtree(1, 1, n);
145
    while(q--){
146
        int opt;
147
        cin>>opt;
148
        if(opt == 1){
149
            int pos;
150
            cin>>pos;
151
            minuss(1,1,n,pos);
152
        }else{
153
            int l, r;
154
            cin>>l>>r;
155
            query_node result = querysum(1,1,n,l,r,inf);
156
            cout<<result.summ<<endl;
157
        }
158
    }
159

160
    return 0;
161
}

从夯到拉#

最近从夯到拉的排名很火，于是：

题目排名

主要依据是题目的思维跳跃度/难易度，野榜，仅代表个人的偏好，不喜轻喷（

题外话#

2024的Coding Challenge活到了第二天的下午，这次第一名的大佬熬到第二天凌晨6点左右就完赛了，快进到2026年的1024比赛开赛当天就被AK

主播这次就比较摆了，磨蹭到结束前两个小时才写完

每次打OI竞赛的时候都很感慨自己当初为什么不在体制内继续学信息学奥赛（哭）

总之非常感谢出题组的付出，使这个活动延续下去，也提供了一个认识各位大佬的平台~