以下摘要由GPT-4o生成:
题目一涉及操作一个数列，允许对元素进行修改和求子数列的和。输入包括数列的长度和操作次数，数列本身，以及每个操作的具体细节。题目要求在操作类型为求和时输出对应的结果。题目二则关注星星的坐标，定义了星星的等级为其左下方（包括正左和正下）星星的数量。输入给出星星的数量和各自的坐标，要求统计每个等级的星星数量，并按级别输出结果。这两个题目的数据范围较大，需要有效的算法处理。

题目一

给定 n个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b][a,b] 的连续和。

输入格式

第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。

第二行包含 n 个整数，表示完整数列。

接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b][a,b]的和；k=1，表示第 a个数加 b）。

数列从 11 开始计数。

输出格式

输出若干行数字，表示 k=0 时，对应的子数列 [a,b][a,b] 的连续和。

数据范围

1≤n≤100000
1≤m≤100000
1≤a≤b≤n
数据保证在任何时候，数列中所有元素之和均在 int 范围内。

输入样例：

1
2
3
4
5
6
7
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

输出样例：

1
2
3
11
30
35
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<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n, m;
int a[N], tr[N];

int lowbit(int x){
    return x & ( -x);
}
void add(int x, int v){
    
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int query(int x){
    int res = 0;
    for(int i = x; i > 0; i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]); //读取a[i]数组;
    for(int i = 1; i <= n; i++) add(i, a[i]);//第i个位置加上某个数;tr[n]树状数组初始化
    
    while(m--){
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        if(k == 0) printf("%d\n", query(y) - query(x - 1));
        else add(x, y); 
    }
    return 0;
}

线段树解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
struct Node {
    int l, r;
    int sum;
}tr[N * 4];

int w[N];
int n, m;
void pushup(int u){
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r){
    if (l == r) tr[u] = {l, r, w[r]};//
    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(1, l, mid);
        build(1, mid + 1, r);
        pushup(u);//求父节点;
    }
}
int query(int u, int l, int r){
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;//查询区间在节点区间内，直接返回;
    
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);//查询节点区间左边与查询区间交集;左子树
    if (r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}
void modify(int u,int x, int v){
    if (tr[u].l == tr[u].r) tr[u].sum += v;//叶子节点加一构建后求父节点;
    else {
        
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);//左子树;
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}


int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n; i++) scanf("%d", &w[i]);
    build(1, 1, n);
    
    int a, b, k;
    while (m--) {
        scanf("%d%d%d",&k, &a, &b);
        if(k == 0) printf("%d\n", query(1, a, b));//查询区间a到b
        else modify(1, a, b);//修改a点 + b
    }
    
    return 0;
}

题目二

天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。

本题采用数学上的平面直角坐标系，即 xx 轴向右为正方向，y 轴向上为正方向。

如果一个星星的左下方（包含正左和正下）有 k 颗星星，就说这颗星星是 k 级的。

1.png

例如，上图中星星 55 是 33 级的（1,2,4 在它左下），星星 2,4是 1 级的。

例图中有 1 个 0 级，2 个 1 级，1 个 2 级，1 个 3 级的星星。

给定星星的位置，输出各级星星的数目。

换句话说，给定 N 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

输入格式

第一行一个整数 N，表示星星的数目；

接下来 N行给出每颗星星的坐标，坐标用两个整数 x,y表示；

不会有星星重叠。星星按 y 坐标增序给出，y 坐标相同的按 x 坐标增序给出。

输出格式

N行，每行一个整数，分别是 0 级，1 级，2级，……，N−1 级的星星的数目。

数据范围

1≤N≤15000
0≤x,y≤320000

输入样例：

1
2
3
4
5
6
5
1 1
5 1
7 1
3 3
5 5

输出样例：

1
2
3
4
5
1
2
1
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int n;
const int N = 32010;
int tr[N], level[N];

int lowbit(int x){
    return x & -x;
}
void add(int x){
    for(int i = x; i < N; i += lowbit(i)) tr[i] ++;
}
int sum (int x){
    int res = 0;
    for(int i = x; i > 0; i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        x++;
        level[sum(x)]++;//第几层星星增加;sum里面没有当前星星;
        add(x);//再加x这个坐标后，星星总数;
    }
    
    for(int i = 0; i < n; i++) cout << level[i] << endl;
    
    return 0;
}