C++模板大全(持续更新,依不同网站整理而成)

基本模板

快读

namespace IN{
    const int MAX_INPUT=1000000;
    #define getc()(p1==p2&&(p2=(p1=buf)+inbuf->sgetn(buf,MAX_INPUT),p1==p2)?EOF:*p1++)
    char buf[MAX_INPUT],*p1,*p2;
    template<typename T>inline bool read(T&x){
        static std::streambuf*inbuf=cin.rdbuf();
        x=0;
        register int f=0,flag=false;
        register char ch=getc();
        while(!isdigit(ch)){
            if(ch=='-'){
                f=1;
            }
            ch=getc();
        }
        if(isdigit(ch)){
            x=x*10+ch-'0';
            ch=getc();
            flag=true;
        }
        while(isdigit(ch)){
            x=x*10+ch-48;
            ch=getc();
        }
        x=f?-x:x;
        return flag;
    }
    template<typename T,typename ...Args>inline bool read(T&a,Args& ...args){
       return read(a)&&read(args...);
    }
    #undef getc
}
using namespace IN;
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

快写

namespace OUT{
    template<typename T>inline void put(T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char stack[21];
        static int top=0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc('\n');
            return;
        }
        while(x){
            stack[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(stack[top]);
            --top;
        }
        outbuf->sputc('\n');
    }
    inline void putc(const char ch){
        static std::streambuf *outbuf=cout.rdbuf();
        outbuf->sputc(ch);
    }
    inline void putstr(string s){
        for(register int i=0;i<s.length();i++) putc(s[i]);
    }
    template<typename T>inline void put(const char ch,T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char stack[21];
        static int top = 0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc(ch);
            return;
        }
        while(x){
            stack[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(stack[top]);
            --top;
        }
        outbuf->sputc(ch);
    }
    template<typename T,typename ...Args> inline void put(T a,Args ...args){
        put(a);put(args...);
    }
    template<typename T,typename ...Args> inline void put(const char ch,T a,Args ...args){
        put(ch,a);put(ch,args...);
    }
}
using namespace OUT;
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

快读快写

namespace IN{
    const int MAX_INPUT=1000000;
    #define getc()(p1==p2&&(p2=(p1=buf)+inbuf->sgetn(buf,MAX_INPUT),p1==p2)?EOF:*p1++)
    char buf[MAX_INPUT],*p1,*p2;
    template<typename T>inline bool read(T&x){
        static std::streambuf*inbuf=cin.rdbuf();
        x=0;
        register int f=0,flag=false;
        register char ch=getc();
        while(!isdigit(ch)){
            if(ch=='-'){
                f=1;
            }
            ch=getc();
        }
        if(isdigit(ch)){
            x=x*10+ch-'0';
            ch=getc();
            flag=true;
        }
        while(isdigit(ch)){
            x=x*10+ch-48;
            ch=getc();
        }
        x=f?-x:x;
        return flag;
    }
    template<typename T,typename ...Args>inline bool read(T&a,Args& ...args){
       return read(a)&&read(args...);
    }
    #undef getc
}
namespace OUT{
    template<typename T>inline void put(T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char stack[21];
        static int top=0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc('\n');
            return;
        }
        while(x){
            stack[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(stack[top]);
            --top;
        }
        outbuf->sputc('\n');
    }
    inline void putc(const char ch){
        static std::streambuf *outbuf=cout.rdbuf();
        outbuf->sputc(ch);
    }
    inline void putstr(string s){
        for(register int i=0;i<s.length();i++) putc(s[i]);
    }
    template<typename T>inline void put(const char ch,T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char stack[21];
        static int top = 0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc(ch);
            return;
        }
        while(x){
            stack[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(stack[top]);
            --top;
        }
        outbuf->sputc(ch);
    }
    template<typename T,typename ...Args> inline void put(T a,Args ...args){
        put(a);put(args...);
    }
    template<typename T,typename ...Args> inline void put(const char ch,T a,Args ...args){
        put(ch,a);put(ch,args...);
    }
}
using namespace IN;
using namespace OUT;
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

火车头

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
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

缺省源

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include
#define int long long
#define ofr(x,y,z) for(int x=y;x<=z;x++)
#define rfr(x,y,z) for(int x=y;x>=z;x--)
using namespace std; 
namespace IN{
    const int MAX_INPUT=1000000;
    #define getc()(p1==p2&&(p2=(p1=buf)+inbuf->sgetn(buf,MAX_INPUT),p1==p2)?EOF:*p1++)
    char buf[MAX_INPUT],*p1,*p2;
    template<typename T>inline bool read(T&x){
        static std::streambuf*inbuf=cin.rdbuf();
        x=0;
        register int f=0,flag=false;
        register char ch=getc();
        while(!isdigit(ch)){
            if(ch=='-'){
                f=1;
            }
            ch=getc();
        }
        if(isdigit(ch)){
            x=x*10+ch-'0';
            ch=getc();
            flag=true;
        }
        while(isdigit(ch)){
            x=x*10+ch-48;
            ch=getc();
        }
        x=f?-x:x;
        return flag;
    }
    template<typename T,typename ...Args>inline bool read(T&a,Args& ...args){
       return read(a)&&read(args...);
    }
    #undef getc
}
namespace OUT{
    template<typename T>inline void put(T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char stack[21];
        static int top=0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc('\n');
            return;
        }
        while(x){
            stack[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(stack[top]);
            --top;
        }
        outbuf->sputc('\n');
    }
    inline void putc(const char ch){
        static std::streambuf *outbuf=cout.rdbuf();
        outbuf->sputc(ch);
    }
    inline void putstr(string s){
        for(register int i=0;i<s.length();i++){
            putc(s[i]);
        }
    }
    template<typename T>inline void put(const char ch,T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char stack[21];
        static int top=0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc(ch);
            return;
        }
        while(x){
            stack[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(stack[top]);
            --top;
        }
        outbuf->sputc(ch);
    }
    template<typename T,typename ...Args> inline void put(T a,Args ...args){
        put(a);
        put(args...);
    }
    template<typename T,typename ...Args> inline void put(const char ch,T a,Args ...args){
        put(ch,a);
        put(ch,args...);
    }
}
using namespace IN;
using namespace OUT;
void openfile(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    
    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
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

emmm…下面开始回归正题了

基本算法

暴力枚举

抱歉,暴力枚举没有模板

模拟

抱歉,模拟没有模板.

贪心

抱歉,贪心没有模板

二分

注意,使用二分前要注意该序列的单调性.

while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid)) { //check为二分答案
        ans = mid;
        r = mid - 1;
    } else {
        l = mid + 1;
    }
}
1
2
3
4
5
6
7
8
9

另外,我们也可以使用lower_bound和upper_bound.

int j=lower_bound(a+1,a+n+1,m)-a;
int k=upper_bound(a+1,a+n+1,m)-a;
1
2

三分

三分主要用来求单峰函数或单谷函数的极值点

double l = 0, r = 1000;
while (r - l > esp) {
    double k = (r - l) / 3;
    double mid1 = l + k, mid2 = r - k;
    if (check(mid1) <= check(mid2)) {
        r = mid2;
    } else {
        l = mid1;
    }
}
1
2
3
4
5
6
7
8
9
10

尺取法

尺取法,也称双指针

int l = 0, r = k;
while (n - l >= k) {
    int t = r - l - a[r] + a[l];
    if (t < k) {
        ans += (r - l - k + 1);
        r++;
    } else {
        l++;
    }
}
1
2
3
4
5
6
7
8
9
10

分治

抱歉,分治没有模板

前缀和

最简单的模板

cin >> a[1];
int b[i] = a[1];
for (int i = 2; i <= n; i++) {
    cin >> a[i];
    b[i] = b[i - 1] + a[i];
}
1
2
3
4
5
6

差分

就只需要把上面的反过来就行了,许多数据结构都要用的差分的概念,例:树状数组.

递推

抱歉,递推没有模板.

递归

抱歉,递归没有模板.

倍增

我们会在后面的快速幂和LCA中遇到.

排序

sort

这个都知道

sort(a+1,a+n+1,cmp)//cmp为自定义函数
1

冒泡排序

for (int i = 1; i <= n - 1; i++) {
    for (int j = 1; j <= n - i + 1; j++) {
        if (a[j - 1] < a[j]) {
            int temp;
            temp = a[j];
            a[j] = a[j - 1];
            a[j - 1] = temp;
            //交换，当然，也可以用swap
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

桶排序

for (int i = 1; i <= n; i++) {
    cin >> m;
    a[m]++;
}
for (int i = 1001; i >= 0; i--) {
    if (a[i] >= 1) {
        for (int j = 1; j <= a[i]; j++) {
            cout << i << " ";
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

选择排序

for (int i = 0; i < len - 1; i++) {
    int min = i;
    for (int j = i + 1; j < len; j++) {
        if (arr[j] < arr[min]) {
            min = j;
        }
    }
    swap(arr[min], arr[i]);
}
1
2
3
4
5
6
7
8
9

插入排序

int j, key;
for (int i = 1; i < len; i++) {
    key = arr[i];
    j = i - 1;
    while ((j >= 0) && (arr[j] > key)) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;
}
1
2
3
4
5
6
7
8
9
10

希尔排序

int inc = len;

do {
    // 确定分组的增量
    inc = inc / 3 + 1;
    for (int i = 0; i < inc; i++) {
        for (int j = i + inc; j < len; j += inc) {
            if (arr[j] < arr[j - inc]) {
                int temp = arr[j];
                for (int k = j - inc; k >= 0 && temp < arr[k]; k -= inc) {
                    arr[k + inc] = arr[k];
                }
                arr[k + inc] = temp;
            }
        }
    }
} while (inc > 1);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

归并排序

if (start >= end) {
    return;
}
int mid = (start + end) / 2;
MergeSort(arr, start, mid, temp);
MergeSort(arr, mid + 1, end, temp);
// 合并两个有序序列
int length = 0; // 表示辅助空间有多少个元素
int i_start = start;
int i_end = mid;
int j_start = mid + 1;
int j_end = end;
while (i_start <= i_end && j_start <= j_end) {
    if (arr[i_start] < arr[j_start]) {
        temp[length] = arr[i_start];
        length++;
        i_start++;
    } else {
        temp[length] = arr[j_start];
        length++;
        j_start++;
    }
}
while (i_start <= i_end) { // 把剩下数的合并
    temp[length] = arr[i_start];
    i_start++;
    length++;
}
while (j_start <= j_end) {
    temp[length] = arr[j_start];
    length++;
    j_start++;
}
// 把辅助空间的数据放到原空间
for (int i = 0; i < length; i++) {
    arr[start + i] = temp[i];
}
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

快速排序

if (start >= end) {
    return;
}
int i = start;
int j = end;
// 基准数
int baseval = arr[start];
while (i < j) {
    // 从右向左找比基准数小的数
    while (i < j && arr[j] >= baseval) {
        j--;
    }
    if (i < j) {
        arr[i] = arr[j];
        i++;
    }
    // 从左向右找比基准数大的数
    while (i < j && arr[i] < baseval) {
        i++;
    }
    if (i < j) {
        arr[j] = arr[i];
        j--;
    }
}
// 把基准数放到i的位置
arr[i] = baseval;
// 递归
QuickSort(arr, start, i - 1);
QuickSort(arr, i + 1, end);
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

堆排序

// 最大堆化函数
void max_heapify(int arr[], int start, int end) {
    // 建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { // 若子节点指标在范围內才做比较
        // 先比较两个子节点大小，选择最大的
        if (son + 1 <= end && arr[son] < arr[son + 1]) 
            son++;
        // 如果父节点大于子节点代表调整完毕，直接跳出函数
        if (arr[dad] > arr[son]) 
            return;
        else { // 否则交换父子內容再继续子节点和父节点比较
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
// 堆排序函数
void heap_sort(int arr[], int len) {
    int i;
    // 初始化，i从最后一个父节点开始调整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 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

计数排序

void counting_sort(int *ini_arr, int *sorted_arr, int n) {
    int *count_arr = (int *)malloc(sizeof(int) * 100);
    int i, j, k;
    for (int k = 0; k < 100; k++){
        count_arr[k] = 0;
    }
    for (int i = 0; i < n; i++){
        count_arr[ini_arr[i]]++;
	}
    for (int k = 1; k < 100; k++){
        count_arr[k] += count_arr[k - 1];
    }
    for (j = n; j > 0; j--){
        sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
    }
    free(count_arr);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

基数排序

void count_sort(int arr[], int n, int exp) {
    for (int i = 0; i < n; i++){
        count[(arr[i] / exp) % 10]++;
    }
    for (int i = 1; i < 10; i++){
        count[i] += count[i - 1];
    }
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (int i = 0; i < n; i++){
        arr[i] = output[i];
    }
}
void radix_sort(int arr[], int n) {
    int max_val = arr[0];
    for (int i = 1; i < n; i++){
        if (arr[i] > max_val){
            max_val = arr[i];
        }
    }
    for (int exp = 1; max_val / exp > 0; exp *= 10){
        count_sort(arr, n, exp);
    }
}
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

高精度

高精度嘛，就是模拟啊。。。

高精加

#include
using namespace std;
const int MAX=100005;
int a[MAX],b[MAX],c[MAX];
int lena,lenb,lenc,jinwei;
string s1,s2;
void rev(string s,int a[],int &len){
	len=s.size();
	for(int i=0;i<=len-1;i++)
		a[i]=s[len-i-1]-'0';}
void add(int a[],int b[],int c[]){
	lenc=max(lena,lenb),jinwei=0;
	for(int i=0;i<=lenc;i++){
		c[i]=(a[i]+b[i]+jinwei)%10;
		jinwei=(a[i]+b[i]+jinwei)/10;}}
int main(){
	ios::sync_with_stdio(false);
	cin>>s1>>s2;
	rev(s1,a,lena);
	rev(s2,b,lenb);
	add(a,b,c);
	while(c[lenc]==0&&lenc>0)lenc--;
	while(lenc>=0)cout<<c[lenc--];
	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

高精减

#include
using namespace std;
const int MAX=100005;
int a[MAX],b[MAX],c[MAX];
int lena,lenb,lenc,jinwei;
string s1,s2,s3;
void rev(string s,int a[],int &len){
	len=s.size();
	for(int i=0;i<=len-1;i++)
		a[i]=s[len-i-1]-'0';}
void add(int a[],int b[],int c[]){
	lenc=max(lena,lenb),jinwei=0;
	for(int i=0;i<=lenc-1;i++){
		int tmp=a[i]-b[i]-jinwei;
		if(tmp<0){
			c[i]=tmp+10;
			jinwei=1;
		}else{
			c[i]=tmp;
			jinwei=0;
		}
	}
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>s1>>s2;
	if(s1.size()==s2.size()&&s1<s2){
		s3=s1,s1=s2,s2=s3;
		cout<<"-";
	}else if(s1.size()<s2.size()){
		s3=s1,s1=s2,s2=s3;
		cout<<"-";
	}
	rev(s1,a,lena);
	rev(s2,b,lenb);
	add(a,b,c);
	//lenc=strlen(c);
	while(c[lenc]==0&&lenc>0)lenc--;
	//reverse(c,c+lenc);
	//cout<<"-";
	while(lenc>=0)cout<<c[lenc--];
	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

高精乘

#include
using namespace std;
const int MAX=100005;
int a[MAX],b[MAX],c[MAX];
int lena,lenb,lenc,jinwei;
string s1,s2;
void rev(string s,int a[],int &len){
	len=s.size();
	for(int i=0;i<=len-1;i++)
		a[i]=s[len-i-1]-'0';
}
void add(int a[],int b[],int c[]){
	lenc=max(lena,lenb),jinwei=0;
	for(int i=0;i<=lenc;i++){
		c[i]=(a[i]+b[i]+jinwei)%10;
		jinwei=(a[i]+b[i]+jinwei)/10;
	}
}
void mul(int a[],int b[],int c[]){
	lenc=lena+lenb;
	for(int i=0;i<lena;i++){
		jinwei=0;
		for(int j=0;j<lenb;j++){
			int tmp=(c[i+j]+(a[i]*b[j])+jinwei);
			c[i+j]=tmp%10;
			jinwei=tmp/10;
		}
	}
	c[lenc-1]=jinwei;
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>s1>>s2;
	rev(s1,a,lena);
	rev(s2,b,lenb);
	mul(a,b,c);
	while(c[lenc]==0&&lenc>0)lenc--;
	while(lenc>=0)cout<<c[lenc--];
	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

高精阶乘

#include
#define N 2000100
typedef long long ll；
int a[N];
int k = 1;
void cheng(int x){
	int ch = 0;
	for(int i = 1; i <= k; i++){
		a[i] = a[i] * x +ch;
		ch = a[i] / 10;
		a[i] = a[i] % 10;
	}
	while(ch > 0){
		a[k+1] = ch % 10;
		ch /= 10;
		k++;
	}
}
int main(){
	int n;
	scanf("%d",&n);
    printf("%d!=",n);
	a[1] = 1;
	for(int i = 1; i <= n; i++)
		cheng(i);
	for(int i = k; i >= 1; i--){
		printf("%d",a[i]);
	}
	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

基础数据结构

栈

STL容器:stack
具体操作用法上度娘

队列

STL容器:queue
具体操作方法上度娘

哈希

你想怎么哈希就怎么哈希,只要不保证冲突过多就行.

链表

单向链表

// 节点类
template <typename T>
class Node {
public:
    T data;
    Node<T>* next;
    Node(T data) {
        this->data = data;
        next = nullptr;
    }
};
// 链表类
template <typename T>
class LinkedList {
private:
    Node<T>* head;
    Node<T>* tail;
    int size;
public:
    LinkedList() {
        head = nullptr;
        tail = nullptr;
        size = 0;
    }
    void add(T data) {
        Node<T>* new_node = new Node<T>(data);
        if (size == 0) {
            head = new_node;
            tail = new_node;
        } else {
            tail->next = new_node;
            tail = new_node;
        }
        size++;
    }
    void remove(T data) {
        Node<T>* prev = nullptr;
        Node<T>* curr = head;
        while (curr != nullptr && curr->data != data) {
            prev = curr;
            curr = curr->next;
        }
        if (curr != nullptr) {
            if (prev == nullptr) {
                head = curr->next;
            } else {
                prev->next = curr->next;
            }
            delete curr;
            size--;
        }
    }
    void print() {
        Node<T>* curr = head;
        while (curr != nullptr) {
            cout << curr->data << " ";
            curr = curr->next;
        }
        cout << endl;
    }
};
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

双向链表

// 节点类
template <typename T>
class Node {
public:
    T data;
    Node<T>* prev;
    Node<T>* next;
    Node(T data) {
        this->data = data;
        prev = nullptr;
        next = nullptr;
    }
};
// 链表类
template <typename T>
class DoublyLinkedList {
private:
    Node<T>* head;
    Node<T>* tail;
    int size;
public:
    DoublyLinkedList() {
        head = nullptr;
        tail = nullptr;
        size = 0;
    }
    void add(T data) {
        Node<T>* new_node = new Node<T>(data);
        if (size == 0) {
            head = new_node;
            tail = new_node;
            new_node->prev = nullptr;
            new_node->next = nullptr;
        } else {
            new_node->prev = tail;
            new_node->next = nullptr;
            tail->next = new_node;
            tail = new_node;
        }
        size++;
    }
    void remove(T data) {
        Node<T>* prev = nullptr;
        Node<T>* curr = head;
        while (curr != nullptr && curr->data != data) {
            prev = curr;
            curr = curr->next;
        }
        if (curr != nullptr) {
            if (prev == nullptr) {
                head = curr->next;
                if (head != nullptr) {
                    head->prev = nullptr;
                }
            } else {
                prev->next = curr->next;
                if (curr->next != nullptr) {
                    curr->next->prev = prev;
                }
            }
            delete curr;
            size--;
        }
    }
    void print() {
        Node<T>* curr = head;
        while (curr != nullptr) {
            cout << curr->data << " ";
            curr = curr->next;
        }
        cout << endl;
    }
};
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

单调栈

同时也可以用数组来模拟单调栈

for(int i = 1; i <= a.size(); i++) {
    while(!s.empty() && a[i-1] > s.top()) {
        s.pop();
    }
    s.push(a[i-1]);
}
1
2
3
4
5
6

单调队列

同时也可以用数组来模拟单调队列

for (int i = k; i < n; ++i) {
	q.emplace(nums[i], i);
	while (q.top().second <= i - k) {
		q.pop();
	}
	ans.push_back(q.top().first);
}
1
2
3
4
5
6
7

高级数据结构

树

树的储存

for (int i=1;i<=n;i++) {
	cin>>child>>father;
	a[child].parent=father;
	a[father].children.push_back(child);
}
1
2
3
4
5

求二叉树深度

void dfs(int x,int deep) {
	d=max(d,deep);
	if(a[x].left) {
		dfs(a[x].left,deep+1);
	}
	if(a[x].right) {
		dfs(a[x].right,deep+1);
	}
}
1
2
3
4
5
6
7
8
9

求二叉树先序遍历

void recursion(struct BinaryNode *root) {
	if(root==NULL) {
		return;
	}
	printf("%c\n",root->ch);
	recursion(root->lChild);
	recursion(root->rChild);
}
1
2
3
4
5
6
7
8

求二叉树中序遍历

void recursion(struct BinaryNode *root) {
	if(root==NULL) {
		return;
	}
	recursion(root->lChild);
	printf("%c\n",root->ch);
	recursion(root->rChild);
}
1
2
3
4
5
6
7
8

求二叉树后序遍历

void recursion(struct BinaryNode *root) {
	if(root==NULL) {
		return;
	}
	recursion(root->lChild);
	recursion(root->rChild);
	printf("%c\n",root->ch);
}
1
2
3
4
5
6
7
8

求二叉树层序遍历

if (Tree != NULL) {
	q.push(Tree);
	//根节点进队列
}
while (q.empty() == false)  //队列不为空判断 {
	cout << q.front()->data << " → ";
	if (q.front()->leftPtr != NULL)   //如果有左孩子，leftChild入队列 {
		q.push(q.front()->leftPtr);
	}
	if (q.front()->rightPtr != NULL)   //如果有右孩子，rightChild入队列 {
		q.push(q.front()->rightPtr);
	}
	q.pop();
	//已经遍历过的节点出队列
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

哈弗曼树的创建

其中 $q$ 是优先队列.

int huffman(int x) {
	int res=0;
	for (int i=0;i<n-1;i++) {
		int x=q.top();
		q.pop();
		int y=q.top();
		q.pop();
		int add=x+y;
		res+=add;
		q.push(add);
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

哈夫曼编码

void huffmanCoding(Htree root, int len, int arr[]) {
	// 计算霍夫曼编码
	if (root != NULL) {
		if (root->lchild == NULL && root->rchild == NULL) {
			for (int i = 0; i < len; i++) printf("%d", arr[i]);
			printf("\n");
		} else {
			arr[len] = 0;
			huffmanCoding(root->lchild, len + 1, arr);
			arr[len] = 1;
			huffmanCoding(root->rchild, len + 1, arr);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

树状数组

单修区查

#include
using namespace std;
int const maxn=500005;
int n,m,p,x,y;
long long a,c[maxn];
long long lowbit(int x) {
	return x&-x;
}
void add(int u,int v) {
	for (int i=u;i<=n;i+=lowbit(i)) {
		c[i]+=v;
	}
}
long long sum(int u) {
	int ans=0;
	for (int i=u;i>0;i-=lowbit(i)) {
		ans+=c[i];
	}
	return ans;
}
int main() {
	cin>>n>>m;
	for (int i=1;i<=n;i++) {
		cin>>a;
		add(i,a);
	}
	for (int i=1;i<=m;i++) {
		cin>>p>>x>>y;
		if(p==1) {
			add(x,y);
		}
		if(p==2) {
			cout<<sum(y)-sum(x-1)<<endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

区修单查

#include
using namespace std;
#define lowbit(x) x&(-x)
using ll=long long;
long long n,q,f,a[1000005],l,r,x,p,b[1000005];
long long c[1000005];
int main() {
	cin>>n>>q;
	for (int i=1;i<=n;i++) {
		cin>>a[i];
		b[i]=a[i]-a[i-1];
		for (int j=i;j<=n;j+=lowbit(j)) {
			c[j]+=b[i];
		}
	}
	for (int i=1;i<=q;i++) {
		cin>>f;
		if(f==1) {
			cin>>l>>r>>x;
			for (int j=l;j<=n;j+=lowbit(j)) {
				c[j]+=x;
			}
			for (int j=r+1;j<=n;j+=lowbit(j)) {
				c[j]-=x;
			}
		} else {
			cin>>p;
			long long ans=0;
			for (int j=p;j>=1;j-=lowbit(j)) {
				ans+=c[j];
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

区修区查

#include
#define lowbit(x) x&(-x)
using namespace std;
long long n,m,f,l,r,x,a[1000005],b;
long long c1[1000005],c2[1000005];
void update(long long x,long long k) {
	for (long long i=x;i<=n;i+=lowbit(i)) {
		c1[i]+=k,c2[i]+=k*(x-1);
	}
}
long long getsum(long long x) {
	long long ans=0;
	for (long long i=x;i>=1;i-=lowbit(i)) {
		ans+=(c1[i]*x-c2[i]);
	}
	return ans;
}
int main() {
	cin>>n>>m;
	for (long long i=1;i<=n;i++) {
		cin>>a[i];
		b=a[i]-a[i-1];
		update(i,b);
	}
	for (long long i=1;i<=m;i++) {
		cin>>f>>l>>r;
		if(f==1) {
			cin>>x;
			update(l,x);
			update(r+1,-x);
		} else {
			cout<<getsum(r)-getsum(l-1)<<endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

线段树

单修区查

#include 
using namespace std;
#define MAXN 100010
#define INF 10000009
#define MOD 10000007
#define LL long long
#define in(a) a=read()
#define REP(i,k,n) for (long long i=k;i<=n;i++)
#define DREP(i,k,n) for (long long i=k;i>=n;i--)
#define cl(a) memset(a,0,sizeof(a))
inline long long read() {
	long long x=0,f=1;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}
inline void out(long long x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) out(x/10);
	putchar(x%10+'0');
}
long long n,m,p;
long long input[MAXN];
struct node {
	long long l,r;
	long long sum,mlz,plz;
}
tree[4*MAXN];
inline void build(long long i,long long l,long long r) {
	tree[i].l=l;
	tree[i].r=r;
	tree[i].mlz=1;
	if(l==r) {
		tree[i].sum=input[l]%p;
		return ;
	}
	long long mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
	return ;
}
inline void pushdown(long long i) {
	long long k1=tree[i].mlz,k2=tree[i].plz;
	tree[i<<1].sum=(tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;
	tree[i<<1|1].sum=(tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;
	tree[i<<1].mlz=(tree[i<<1].mlz*k1)%p;
	tree[i<<1|1].mlz=(tree[i<<1|1].mlz*k1)%p;
	tree[i<<1].plz=(tree[i<<1].plz*k1+k2)%p;
	tree[i<<1|1].plz=(tree[i<<1|1].plz*k1+k2)%p;
	tree[i].plz=0;
	tree[i].mlz=1;
	return ;
}
inline void mul(long long i,long long l,long long r,long long k) {
	if(tree[i].r<l || tree[i].l>r)  return ;
	if(tree[i].l>=l && tree[i].r<=r) {
		tree[i].sum=(tree[i].sum*k)%p;
		tree[i].mlz=(tree[i].mlz*k)%p;
		tree[i].plz=(tree[i].plz*k)%p;
		return ;
	}
	pushdown(i);
	if(tree[i<<1].r>=l)  mul(i<<1,l,r,k);
	if(tree[i<<1|1].l<=r)  mul(i<<1|1,l,r,k);
	tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
	return ;
}
inline void add(long long i,long long l,long long r,long long k) {
	if(tree[i].r<l || tree[i].l>r)  return ;
	if(tree[i].l>=l && tree[i].r<=r) {
		tree[i].sum+=((tree[i].r-tree[i].l+1)*k)%p;
		tree[i].plz=(tree[i].plz+k)%p;
		return ;
	}
	pushdown(i);
	if(tree[i<<1].r>=l)  add(i<<1,l,r,k);
	if(tree[i<<1|1].l<=r)  add(i<<1|1,l,r,k);
	tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
	return ;
}
inline long long search(long long i,long long l,long long r) {
	if(tree[i].r<l || tree[i].l>r)  return 0;
	if(tree[i].l>=l && tree[i].r<=r)
	        return tree[i].sum;
	pushdown(i);
	long long sum=0;
	if(tree[i<<1].r>=l)  sum+=search(i<<1,l,r)%p;
	if(tree[i<<1|1].l<=r)  sum+=search(i<<1|1,l,r)%p;
	return sum%p;
}
int main() {
	in(n);
	in(m);
	in(p);
	REP(i,1,n)  in(input[i]);
	build(1,1,n);
	REP(i,1,m) {
		long long fl,a,b,c;
		in(fl);
		if(fl==1) {
			in(a);
			in(b);
			in(c);
			c%=p;
			mul(1,a,b,c);
		}
		if(fl==2) {
			in(a);
			in(b);
			in(c);
			c%=p;
			add(1,a,b,c);
		}
		if(fl==3) {
			in(a);
			in(b);
			printf("%lld\n",search(1,a,b));
		}
	}
	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
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

区修单查

#include 
using namespace std;
int n,m;
int ans;
int input[500010];
struct node {
	int left,right;
	int num;
}
tree[2000010];
void build(int left,int right,int index) {
	tree[index].num=0;
	tree[index].left=left;
	tree[index].right=right;
	if(left==right)
	        return ;
	int mid=(right+left)/2;
	build(left,mid,index*2);
	build(mid+1,right,index*2+1);
}
void pls(int index,int l,int r,int k) {
	if(tree[index].left>=l && tree[index].right<=r) {
		tree[index].num+=k;
		return ;
	}
	if(tree[index*2].right>=l)
	       pls(index*2,l,r,k);
	if(tree[index*2+1].left<=r)
	       pls(index*2+1,l,r,k);
}
void search(int index,int dis) {
	ans+=tree[index].num;
	if(tree[index].left==tree[index].right)
	        return ;
	if(dis<=tree[index*2].right)
	        search(index*2,dis);
	if(dis>=tree[index*2+1].left)
	        search(index*2+1,dis);
}
int main() {
	int n,m;
	cin>>n>>m;
	build(1,n,1);
	for (int i=1;i<=n;i++)
	        scanf("%d",&input[i]);
	for (int i=1;i<=m;i++) {
		int a;
		scanf("%d",&a);
		if(a==1) {
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			pls(1,x,y,z);
		}
		if(a==2) {
			ans=0;
			int x;
			scanf("%d",&x);
			search(1,x);
			printf("%d\n",ans+input[x]);
		}
	}
}
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
using namespace std;
typedef long long ll;
const ll N=1e6+7;
const ll mod=2147483647;
ll n,m;
struct node {
	ll l,r,sum,lz;
}
tree[N];
ll arr[N];
void build(ll i,ll l,ll r,ll arr[]) {
	tree[i].lz=0;
	//初始化的时候肯定都是0
	tree[i].l=l;
	tree[i].r=r;
	if(l==r) {
		tree[i].sum=arr[l];
		//到达底部单节点才把输入的值赋给你
		return ;
	}
	ll mid=(l+r)/2;
	build(i*2,l,mid,arr);
	build(i*2+1,mid+1,r,arr);
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	//树已经全部建完了，再从下往上+++，使得上层的树都有了值
	return ;
}
inline void push_down(ll i) {
	if(tree[i].lz!=0) {
		tree[i*2].lz+=tree[i].lz;
		tree[i*2+1].lz+=tree[i].lz;
		ll mid=(tree[i].l+tree[i].r)/2;
		tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);
		tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
		tree[i].lz=0;
	}
	return ;
}
inline void add(ll i,ll l,ll r,ll k) {
	if(tree[i].l>=l&&tree[i].r<=r) {
		tree[i].sum+=k*(tree[i].r-tree[i].l+1);
		tree[i].lz+=k;
		return ;
	}
	push_down(i);
	if(tree[i*2].r>=l)
	        add(i*2,l,r,k);
	if(tree[i*2+1].l<=r)
	        add(i*2+1,l,r,k);
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	return ;
}
inline ll searchs(ll i,ll l, ll r) {
	if(tree[i].l>=l&&tree[i].r<=r)
	        return tree[i].sum;
	push_down(i);
	ll num=0;
	if(tree[i*2].r>=l)
	        num+=searchs(i*2,l,r);
	if(tree[i*2+1].l<=r)
	        num+=searchs(i*2+1,l,r);
	return num;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=n;++i)
	        cin>>arr[i];
	build(1,1,n,arr);
	//从根节点开始建树
	for (int i=1;i<=m;++i) {
		ll tmp;
		cin>>tmp;
		if(tmp==1) {
			ll a,b,c;
			cin>>a>>b>>c;
			add(1,a,b,c);
			//每次修改都是从编号为1开始的，因为编号1是树的顶端，往下分叉
		}
		if(tmp==2) {
			ll a,b;
			cin>>a>>b;
			printf("%lld\n",searchs(1,a,b));
			//编号i的话，每次都是从1开始
		}
	}
	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
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
using namespace std;
typedef long long ll;
const ll N=1e6+7;
template<typename T>void read(T &x) {
	x=0;
	char ch=getchar();
	ll f=1;
	while(!isdigit(ch)) {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)) {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=f;
}
ll n,m,arr[N],mod,flag,cn,cm,cw;
struct node {
	ll l,r,sum,mul,add;
	//有乘有加，先乘后加
}
tree[N];
inline void build(ll i,ll l,ll r) {
	tree[i].l=l;
	tree[i].r=r;
	tree[i].mul=1;
	if(l==r) {
		tree[i].sum=arr[l]%mod;
		return ;
	}
	ll mid=(l+r)>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
}
inline void push_down(ll i) {
	tree[i*2].sum=(ll)(tree[i].mul*tree[i*2].sum+((tree[i*2].r-tree[i*2].l+1)*tree[i].add)%mod)%mod;
	tree[i*2+1].sum=(ll)(tree[i].mul*tree[i*2+1].sum+((tree[i*2+1].r-tree[i*2+1].l+1)*tree[i].add)%mod)%mod;
	tree[i*2].mul=(ll)(tree[i*2].mul*tree[i].mul)%mod;
	tree[i*2+1].mul=(ll)(tree[i*2+1].mul*tree[i].mul)%mod;
	tree[i*2].add=(ll)(tree[i*2].add*tree[i].mul+tree[i].add)%mod;
	tree[i*2+1].add=(ll)(tree[i*2+1].add*tree[i].mul+tree[i].add)%mod;
	tree[i].mul=1;
	tree[i].add=0;
}
inline void add(ll i,ll l,ll r,ll k) {
	if(tree[i].l>=l&&tree[i].r<=r) {
		tree[i].add=(ll)(tree[i].add+k)%mod;
		tree[i].sum=(ll)(tree[i].sum+k*(tree[i].r-tree[i].l+1))%mod;
		return ;
	}
	push_down(i);
	if(tree[i*2].r>=l)
	        add(i*2,l,r,k);
	if(tree[i*2+1].l<=r)
	        add(i*2+1,l,r,k);
	//ll mid=(tree[i].l+tree[i].r)>>1;
	//if(l<=mid)add(i*2,l,r,k);
	//if(mid
	tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
}
inline void mult(ll i,ll l,ll r,ll k) {
	if(tree[i].l>=l&&tree[i].r<=r) {
		tree[i].mul=(tree[i].mul*k)%mod;
		tree[i].add=(tree[i].add*k)%mod;
		tree[i].sum=(tree[i].sum*k)%mod;
		return ;
	}
	push_down(i);
	if(tree[i*2].r>=l)
	        mult(i*2,l,r,k);
	if(tree[i*2+1].l<=r)
	        mult(i*2+1,l,r,k);
	//ll mid=(tree[i].l+tree[i].r)>>1;
	//if(l<=mid)mult(i*2,l,r,k);
	//if(mid
	tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
}
inline ll query(ll i,ll l,ll r) {
	if(tree[i].l>=l&&tree[i].r<=r)
	        return tree[i].sum;
	push_down(i);
	ll num=0;
	if(tree[i*2].r>=l)
	        num=(num+query(i*2,l,r))%mod;
	if(tree[i*2+1].l<=r)
	        num=(num+query(i*2+1,l,r))%mod;
	return num;
	//ll val=0;
	//ll mid=(tree[i].l+tree[i].r)>>1;
	//if(l<=mid)val=(val+query(i*2,l,r))%mod;
	//if(mid
	//return val;
}
int main() {
	read(n),read(m),read(mod);
	for (int i=1;i<=n;++i)
	        read(arr[i]);
	build(1,1,n);
	for (int i=1;i<=m;++i) {
		read(flag);
		if(flag==1) {
			read(cn),read(cm),read(cw);
			mult(1,cn,cm,cw);
		} else if(flag==2) {
			read(cn),read(cm),read(cw);
			add(1,cn,cm,cw);
		} else {
			read(cn),read(cm);
			cout<<query(1,cn,cm)<<endl;
		}
	}
}
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

区间根号

#include
#define MAXN 1000010
#define REP(i,k,n) for (int i=k;i<=n;i++)
#define in(a) a=read()
using namespace std;
int read() {
	int x=0,f=1;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar())
	        if(ch=='-')
	          f=-1;
	for (;isdigit(ch);ch=getchar())
	        x=x*10+ch-'0';
	return x*f;
}
struct node {
	int l,r;
	long long lz,sum,maxx,minn;
}
tree[MAXN<<2];
int n,m,input[MAXN];
inline void build(int i,int l,int r) {
	tree[i].l=l;
	tree[i].r=r;
	if(l==r) {
		tree[i].sum=tree[i].minn=tree[i].maxx=input[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);
	tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
	return ;
}
inline void push_down(int i) {
	if(!tree[i].lz)  return ;
	long long k=tree[i].lz;
	tree[i*2].lz+=k;
	tree[i*2+1].lz+=k;
	tree[i*2].sum-=(tree[i*2].r-tree[i*2].l+1)*k;
	tree[i*2+1].sum-=(tree[i*2+1].r-tree[i*2+1].l+1)*k;
	tree[i*2].minn-=k;
	tree[i*2+1].minn-=k;
	tree[i*2].maxx-=k;
	tree[i*2+1].maxx-=k;
	tree[i].lz=0;
	return ;
}
inline void Sqrt(int i,int l,int r) {
	if(tree[i].l>=l && tree[i].r<=r && (tree[i].minn-(long long)sqrt(tree[i].minn))==(tree[i].maxx-(long long)sqrt(tree[i].maxx))) {
		long long u=tree[i].minn-(long long)sqrt(tree[i].minn);
		tree[i].lz+=u;
		tree[i].sum-=(tree[i].r-tree[i].l+1)*u;
		tree[i].minn-=u;
		tree[i].maxx-=u;
		//cout<<"i"<
		return ;
	}
	if(tree[i].r<l || tree[i].l>r)  return ;
	push_down(i);
	if(tree[i*2].r>=l)  Sqrt(i*2,l,r);
	if(tree[i*2+1].l<=r)  Sqrt(i*2+1,l,r);
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);
	tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
	//cout<<"i"<
	return ;
}
inline long long search(int i,int l,int r) {
	if(tree[i].l>=l && tree[i].r<=r)
	        return tree[i].sum;
	if(tree[i].r<l || tree[i].l>r)  return 0;
	push_down(i);
	long long s=0;
	if(tree[i*2].r>=l)  s+=search(i*2,l,r);
	if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);
	return s;
}
int main() {
	in(n);
	REP(i,1,n)  in(input[i]);
	build(1,1,n);
	in(m);
	int a,b,c;
	REP(i,1,m) {
		in(a);
		in(b);
		in(c);
		if(a==1)
		            printf("%lld\n",search(1,b,c));
		if(a==2) {
			Sqrt(1,b,c);
			//for(int i=1;i<=7;i++)
			//    cout<
			// cout<
		}
	}
}
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

并查集

普通并查集

int find(int x) {
	return fa[x]==x?x:find(fa[x]);
}
1
2
3

路径压缩

int find(int x) {
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
1
2
3

按秩合并

void rank(int x,int y) {
	int xx=find(x);
	int yy=find(y);
	if(xx!=yy) {
		if(rk[xx]<rk[yy]) {
			fa[xx]=yy;
		} else if(rk[ry]<rk[rx]) {
			fa[yy]=xx;
		} else {
			fa[xx]=yy;
			rk[yy]++;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

树上问题

树的直径

有两种实现方法,一种是dfs,另一种是树形dp.

先放第一种dfs的.

const int N = 10000 + 10;
int n, c, d[N];
vector<int> E[N];
void dfs(int u, int fa) {
	for (int v : E[u]) {
		if (v == fa) continue;
		d[v] = d[u] + 1;
		if (d[v] > d[c]) c = v;
		dfs(v, u);
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		E[u].push_back(v), E[v].push_back(u);
	}
	dfs(1, 0);
	d[c] = 0, dfs(c, 0);
	printf("%d\n", d[c]);
	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

然后是树形dp

const int N = 10000 + 10;
int n, d = 0;
int d1[N], d2[N];
vector<int> E[N];
void dfs(int u, int fa) {
	d1[u] = d2[u] = 0;
	for (int v : E[u]) {
		if (v == fa) continue;
		dfs(v, u);
		int t = d1[v] + 1;
		if (t > d1[u])
		      d2[u] = d1[u], d1[u] = t; else if (t > d2[u])
		      d2[u] = t;
	}
	d = max(d, d1[u] + d2[u]);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		E[u].push_back(v), E[v].push_back(u);
	}
	dfs(1, 0);
	printf("%d\n", d);
	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

树的重心

// 这份代码默认节点编号从 1 开始，即 i ∈ [1,n]
int size[MAXN],  // 这个节点的「大小」（所有子树上节点数 + 该节点）
weight[MAXN],  // 这个节点的「重量」
centroid[2];
// 用于记录树的重心（存的是节点编号）
void GetCentroid(int cur, int fa) {
	// cur 表示当前节点 (current)
	size[cur] = 1;
	weight[cur] = 0;
	for (int i = head[cur]; i != -1; i = e[i].nxt) {
		if (e[i].to != fa) {
			// e[i].to 表示这条有向边所通向的节点。
			GetCentroid(e[i].to, cur);
			size[cur] += size[e[i].to];
			weight[cur] = max(weight[cur], size[e[i].to]);
		}
	}
	weight[cur] = max(weight[cur], n - size[cur]);
	if (weight[cur] <= n / 2) {
		// 依照树的重心的定义统计
		centroid[centroid[0] != 0] = cur;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

LCA(最近公共祖先)

求最近公共祖先有两种方法,一种是倍增,另一种是tarjan.

我们先放第一种倍增的做法.

#include 
#define MXN 50007
using namespace std;
std::vector<int> v[MXN];
std::vector<int> w[MXN];
int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;
// dfs，用来为 lca 算法做准备。接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int root, int fno) {
	// 初始化：第 2^0 = 1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
	fa[root][0] = fno;
	dep[root] = dep[fa[root][0]] + 1;
	// 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
	// 2^(i-1) 的祖先节点。
	for (int i = 1; i < 31; ++i) {
		fa[root][i] = fa[fa[root][i - 1]][i - 1];
		cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
	}
	// 遍历子节点来进行 dfs。
	int sz = v[root].size();
	for (int i = 0; i < sz; ++i) {
		if (v[root][i] == fno) continue;
		cost[v[root][i]][0] = w[root][i];
		dfs(v[root][i], root);
	}
}
// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x, int y) {
	// 令 y 比 x 深。
	if (dep[x] > dep[y]) swap(x, y);
	// 令 y 和 x 在一个深度。
	int tmp = dep[y] - dep[x], ans = 0;
	for (int j = 0; tmp; ++j, tmp >>= 1)
	    if (tmp & 1) ans += cost[y][j], y = fa[y][j];
	// 如果这个时候 y = x，那么 x，y 就都是它们自己的祖先。
	if (y == x) return ans;
	// 不然的话，找到第一个不是它们祖先的两个点。
	for (int j = 30; j >= 0 && y != x; --j) {
		if (fa[x][j] != fa[y][j]) {
			ans += cost[x][j] + cost[y][j];
			x = fa[x][j];
			y = fa[y][j];
		}
	}
	// 返回结果。
	ans += cost[x][0] + cost[y][0];
	return ans;
}
int main() {
	// 初始化表示祖先的数组 fa，代价 cost 和深度 dep。
	memset(fa, 0, sizeof(fa));
	memset(cost, 0, sizeof(cost));
	memset(dep, 0, sizeof(dep));
	// 读入树：节点数一共有 n 个。
	scanf("%d", &n);
	for (int i = 1; i < n; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		++a, ++b;
		v[a].push_back(b);
		v[b].push_back(a);
		w[a].push_back(c);
		w[b].push_back(c);
	}
	// 为了计算 lca 而使用 dfs。
	dfs(1, 0);
	// 查询 m 次，每一次查找两个节点的 lca 点。
	scanf("%d", &m);
	for (int i = 0; i < m; ++i) {
		scanf("%d %d", &a, &b);
		++a, ++b;
		printf("%d\n", lca(a, b));
	}
	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
62
63
64
65
66
67
68
69
70
71
72
73
74
75

第二种是tarjan做法

#include 
using namespace std;
class Edge {
	public:
	  int toVertex, fromVertex;
	int next;
	int LCA;
	Edge() : toVertex(-1), fromVertex(-1), next(-1), LCA(-1) {};
	Edge(int u, int v, int n) : fromVertex(u), toVertex(v), next(n), LCA(-1) {};
};
const int MAX = 100;
int head[MAX], queryHead[MAX];
Edge edge[MAX], queryEdge[MAX];
int parent[MAX], visited[MAX];
int vertexCount, edgeCount, queryCount;
void init() {
	for (int i = 0; i <= vertexCount; i++) {
		parent[i] = i;
	}
}
int find(int x) {
	if (parent[x] == x) {
		return x;
	} else {
		return find(parent[x]);
	}
}
void tarjan(int u) {
	parent[u] = u;
	visited[u] = 1;
	for (int i = head[u]; i != -1; i = edge[i].next) {
		Edge& e = edge[i];
		if (!visited[e.toVertex]) {
			tarjan(e.toVertex);
			parent[e.toVertex] = u;
		}
	}
	for (int i = queryHead[u]; i != -1; i = queryEdge[i].next) {
		Edge& e = queryEdge[i];
		if (visited[e.toVertex]) {
			queryEdge[i ^ 1].LCA = e.LCA = find(e.toVertex);
		}
	}
}
int main() {
	memset(head, 0xff, sizeof(head));
	memset(queryHead, 0xff, sizeof(queryHead));
	cin >> vertexCount >> edgeCount >> queryCount;
	int count = 0;
	for (int i = 0; i < edgeCount; i++) {
		int start = 0, end = 0;
		cin >> start >> end;
		edge[count] = Edge(start, end, head[start]);
		head[start] = count;
		count++;
		edge[count] = Edge(end, start, head[end]);
		head[end] = count;
		count++;
	}
	count = 0;
	for (int i = 0; i < queryCount; i++) {
		int start = 0, end = 0;
		cin >> start >> end;
		queryEdge[count] = Edge(start, end, queryHead[start]);
		queryHead[start] = count;
		count++;
		queryEdge[count] = Edge(end, start, queryHead[end]);
		queryHead[end] = count;
		count++;
	}
	init();
	tarjan(1);
	for (int i = 0; i < queryCount; i++) {
		Edge& e = queryEdge[i * 2];
		cout << "(" << e.fromVertex << "," << e.toVertex << ") " << e.LCA << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

平衡树

Treap

旋转Treap

#include 
#include 
#include 
#define maxn 100005
#define INF (1 << 30)
int n;
struct treap {  // 直接维护成数据结构，可以直接用
	int l[maxn], r[maxn], val[maxn], rnd[maxn], size_[maxn], w[maxn];
	int sz, ans, rt;

	void pushup(int x) {
		size_[x] = size_[l[x]] + size_[r[x]] + w[x];
	}
	void lrotate(int &k) {
		int t = r[k];
		r[k] = l[t];
		l[t] = k;
		size_[t] = size_[k];
		pushup(k);
		k = t;
	}
	void rrotate(int &k) {
		int t = l[k];
		l[k] = r[t];
		r[t] = k;
		size_[t] = size_[k];
		pushup(k);
		k = t;
	}
	void insert(int &k, int x) {  // 插入
		if (!k) {
			sz++;
			k = sz;
			size_[k] = 1;
			w[k] = 1;
			val[k] = x;
			rnd[k] = rand();
			return;
		}
		size_[k]++;
		if (val[k] == x) {
			w[k]++;
		} else if (val[k] < x) {
			insert(r[k], x);
			if (rnd[r[k]] < rnd[k]) lrotate(k);
		} else {
			insert(l[k], x);
			if (rnd[l[k]] < rnd[k]) rrotate(k);
		}
	}
	bool del(int &k, int x) {  // 删除节点
		if (!k) return false;
		if (val[k] == x) {
			if (w[k] > 1) {
				w[k]--;
				size_[k]--;
				return true;
			}
			if (l[k] == 0 || r[k] == 0) {
				k = l[k] + r[k];
				return true;
			} else if (rnd[l[k]] < rnd[r[k]]) {
				rrotate(k);
				return del(k, x);
			} else {
				lrotate(k);
				return del(k, x);
			}
		} else if (val[k] < x) {
			bool succ = del(r[k], x);
			if (succ) size_[k]--;
			return succ;
		} else {
			bool succ = del(l[k], x);
			if (succ) size_[k]--;
			return succ;
		}
	}
	int queryrank(int k, int x) {
		if (!k) return 0;
		if (val[k] == x)
			return size_[l[k]] + 1;
		else if (x > val[k]) {
			return size_[l[k]] + w[k] + queryrank(r[k], x);
		} else
			return queryrank(l[k], x);
	}
	int querynum(int k, int x) {
		if (!k) return 0;
		if (x <= size_[l[k]])
			return querynum(l[k], x);
		else if (x > size_[l[k]] + w[k])
			return querynum(r[k], x - size_[l[k]] - w[k]);
		else
			return val[k];
	}
	void querypre(int k, int x) {
		if (!k) return;
		if (val[k] < x)
			ans = k, querypre(r[k], x);
		else
			querypre(l[k], x);
	}
	void querysub(int k, int x) {
		if (!k) return;
		if (val[k] > x)
			ans = k, querysub(l[k], x);
		else
			querysub(r[k], x);
	}
} T;
int main() {
	srand(123);
	scanf("%d", &n);
	int opt, x;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &opt, &x);
		if (opt == 1)
			T.insert(T.rt, x);
		else if (opt == 2)
			T.del(T.rt, x);
		else if (opt == 3) {
			printf("%d\n", T.queryrank(T.rt, x));
		} else if (opt == 4) {
			printf("%d\n", T.querynum(T.rt, x));
		} else if (opt == 5) {
			T.ans = 0;
			T.querypre(T.rt, x);
			printf("%d\n", T.val[T.ans]);
		} else if (opt == 6) {
			T.ans = 0;
			T.querysub(T.rt, x);
			printf("%d\n", T.val[T.ans]);
		}
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
136
137
138

无旋Treap

#include 
using namespace std;
struct Node {
	Node *ch[2];
	int val, prio;
	int cnt;
	int siz;
	Node(int _val) : val(_val), cnt(1), siz(1) {
		ch[0] = ch[1] = nullptr;
		prio = rand();
	}
	Node(Node *_node) {
		val = _node->val, prio = _node->prio, cnt = _node->cnt, siz = _node->siz;
	}
	void upd_siz() {
		siz = cnt;
		if (ch[0] != nullptr) siz += ch[0]->siz;
		if (ch[1] != nullptr) siz += ch[1]->siz;
	}
};
struct none_rot_treap {
#define _3 second.second
#define _2 second.first
	Node *root;
	pair<Node *, Node *> split(Node *cur, int key) {
		if (cur == nullptr) return {nullptr, nullptr};
		if (cur->val <= key) {
			auto temp = split(cur->ch[1], key);
			cur->ch[1] = temp.first;
			cur->upd_siz();
			return {cur, temp.second};
		} else {
			auto temp = split(cur->ch[0], key);
			cur->ch[0] = temp.second;
			cur->upd_siz();
			return {temp.first, cur};
		}
	}
	tuple<Node *, Node *, Node *> split_by_rk(Node *cur, int rk) {
		if (cur == nullptr) return {nullptr, nullptr, nullptr};
		int ls_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
		if (rk <= ls_siz) {
			Node *l, *mid, *r;
			tie(l, mid, r) = split_by_rk(cur->ch[0], rk);
			cur->ch[0] = r;
			cur->upd_siz();
			return {l, mid, cur};
		} else if (rk <= ls_siz + cur->cnt) {
			Node *lt = cur->ch[0];
			Node *rt = cur->ch[1];
			cur->ch[0] = cur->ch[1] = nullptr;
			return {lt, cur, rt};
		} else {
			Node *l, *mid, *r;
			tie(l, mid, r) = split_by_rk(cur->ch[1], rk - ls_siz - cur->cnt);
			cur->ch[1] = l;
			cur->upd_siz();
			return {cur, mid, r};
		}
	}
	Node *merge(Node *u, Node *v) {
		if (u == nullptr && v == nullptr) return nullptr;
		if (u != nullptr && v == nullptr) return u;
		if (v != nullptr && u == nullptr) return v;
		if (u->prio < v->prio) {
			u->ch[1] = merge(u->ch[1], v);
			u->upd_siz();
			return u;
		} else {
			v->ch[0] = merge(u, v->ch[0]);
			v->upd_siz();
			return v;
		}
	}
	void insert(int val) {
		auto temp = split(root, val);
		auto l_tr = split(temp.first, val - 1);
		Node *new_node;
		if (l_tr.second == nullptr) {
			new_node = new Node(val);
		} else {
			l_tr.second->cnt++;
			l_tr.second->upd_siz();
		}
		Node *l_tr_combined =
		    merge(l_tr.first, l_tr.second == nullptr ? new_node : l_tr.second);
		root = merge(l_tr_combined, temp.second);
	}
	void del(int val) {
		auto temp = split(root, val);
		auto l_tr = split(temp.first, val - 1);
		if (l_tr.second->cnt > 1) {
			l_tr.second->cnt--;
			l_tr.second->upd_siz();
			l_tr.first = merge(l_tr.first, l_tr.second);
		} else {
			if (temp.first == l_tr.second) {
				temp.first = nullptr;
			}
			delete l_tr.second;
			l_tr.second = nullptr;
		}
		root = merge(l_tr.first, temp.second);
	}
	int qrank_by_val(Node *cur, int val) {
		auto temp = split(cur, val - 1);
		int ret = (temp.first == nullptr ? 0 : temp.first->siz) + 1;
		root = merge(temp.first, temp.second);
		return ret;
	}
	int qval_by_rank(Node *cur, int rk) {
		Node *l, *mid, *r;
		tie(l, mid, r) = split_by_rk(cur, rk);
		int ret = mid->val;
		root = merge(merge(l, mid), r);
		return ret;
	}
	int qprev(int val) {
		auto temp = split(root, val - 1);
		int ret = qval_by_rank(temp.first, temp.first->siz);
		root = merge(temp.first, temp.second);
		return ret;
	}
	int qnex(int val) {
		auto temp = split(root, val);
		int ret = qval_by_rank(temp.second, 1);
		root = merge(temp.first, temp.second);
		return ret;
	}
};
none_rot_treap tr;
int main() {
	srand(time(0));
	int t;
	scanf("%d", &t);
	while (t--) {
		int mode;
		int num;
		scanf("%d%d", &mode, &num);
		switch (mode) {
			case 1:
				tr.insert(num);
				break;
			case 2:
				tr.del(num);
				break;
			case 3:
				printf("%d\n", tr.qrank_by_val(tr.root, num));
				break;
			case 4:
				printf("%d\n", tr.qval_by_rank(tr.root, num));
				break;
			case 5:
				printf("%d\n", tr.qprev(num));
				break;
			case 6:
				printf("%d\n", tr.qnex(num));
				break;
		}
	}
}
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

其他

其他由于放不下了，详见here --洛谷博客