基本模板

快读

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;

快写

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;

快读快写

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;

火车头

#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")

缺省源

#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<bits/stdc++.h>
#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;
}

emmm…下面开始回归正题了

基本算法

暴力枚举

抱歉,暴力枚举没有模板

模拟

抱歉,模拟没有模板.

贪心

抱歉,贪心没有模板

二分

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

while (l <= r) {mid = (l + r) >> 1;if (check(mid)) { //check为二分答案ans = mid;r = mid - 1;} else {l = mid + 1;}
}

另外,我们也可以使用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;

三分

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

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;}
}

尺取法

尺取法,也称双指针

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++;}
}

分治

抱歉,分治没有模板

前缀和

最简单的模板

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];
}

差分

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

递推

抱歉,递推没有模板.

递归

抱歉,递归没有模板.

倍增

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

排序

sort

这个都知道

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

冒泡排序

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}}
}

桶排序

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 << " ";}}
}

选择排序

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]);
}

插入排序

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;
}

希尔排序

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);

归并排序

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];
}

快速排序

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);

堆排序

// 最大堆化函数
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);}
}

计数排序

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);
}

基数排序

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);}
}

基础数据结构

栈

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;}
};

双向链表

// 节点类
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;}
};

单调栈

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

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

单调队列

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

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);
}

高级数据结构

树

树的储存

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

求二叉树深度

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);}
}

求二叉树先序遍历

void recursion(struct BinaryNode *root) {if(root==NULL) {return;}printf("%c\n",root->ch);recursion(root->lChild);recursion(root->rChild);
}

求二叉树中序遍历

void recursion(struct BinaryNode *root) {if(root==NULL) {return;}recursion(root->lChild);printf("%c\n",root->ch);recursion(root->rChild);
}

求二叉树后序遍历

void recursion(struct BinaryNode *root) {if(root==NULL) {return;}recursion(root->lChild);recursion(root->rChild);printf("%c\n",root->ch);
}

求二叉树层序遍历

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();//已经遍历过的节点出队列
}

哈弗曼树的创建

其中 $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;
}

哈夫曼编码

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);}}
}

树状数组

单修区查

#include<bits/stdc++.h>
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;
}

区修单查

#include<bits/stdc++.h>
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;
}

区修区查

#include<bits/stdc++.h>
#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;
}

线段树

单修区查

#include <bits/stdc++.h>
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;
}

区修单查

#include <bits/stdc++.h>
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]);}}
}

区间加法

#include<bits/stdc++.h>
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;//初始化的时候肯定都是0tree[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;
}

区间乘法

#include<bits/stdc++.h>
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<r)add(i*2+1,l,r,k);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<r)mult(i*2+1,l,r,k);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<r)val=(val+query(i*2+1,l,r))%mod;//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;}}
}

区间根号

#include<bits/stdc++.h>
#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"<<i<<" "<<tree[i].sum<<endl;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"<<i<<" "<<tree[i].sum<<endl;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<<tree[i].sum<<" ";// cout<<endl;}}
}

并查集

普通并查集

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

路径压缩

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

按秩合并

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]++;}}
}

树上问题

树的直径

有两种实现方法,一种是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;
}

然后是树形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 开始，即 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;}
}

LCA(最近公共祖先)

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

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

#include <bits/stdc++.h>
#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;
}

第二种是tarjan做法

#include <bits/stdc++.h>
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;
}

平衡树

Treap

旋转Treap

#include <algorithm>
#include <cstdio>
#include <iostream>
#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);} elsereturn 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]);elsereturn val[k];}void querypre(int k, int x) {if (!k) return;if (val[k] < x)ans = k, querypre(r[k], x);elsequerypre(l[k], x);}void querysub(int k, int x) {if (!k) return;if (val[k] > x)ans = k, querysub(l[k], x);elsequerysub(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;
}

无旋Treap

#include <bits/stdc++.h>
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.firstNode *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;}}
}