厦门旅游集团网站建设,网站浏览器兼容性通用,个人小白用织梦好还是wordpress好,网页制作的毕业设计论文C模板大全 基本模板快读快写快读快写火车头缺省源 基本算法暴力枚举模拟贪心二分三分尺取法分治前缀和差分递推递归倍增排序sort冒泡排序桶排序选择排序插入排序希尔排序归并排序快速排序堆排序计数排序基数排序 基础数据结构栈队列哈希链表单向链表双向链表 单调栈单调队列 高… C模板大全 基本模板快读快写快读快写火车头缺省源 基本算法暴力枚举模拟贪心二分三分尺取法分治前缀和差分递推递归倍增排序sort冒泡排序桶排序选择排序插入排序希尔排序归并排序快速排序堆排序计数排序基数排序 基础数据结构栈队列哈希链表单向链表双向链表 单调栈单调队列 高级数据结构树树的储存求二叉树深度求二叉树先序遍历求二叉树中序遍历求二叉树后序遍历求二叉树层序遍历哈弗曼树的创建哈夫曼编码 树状数组单修区查区修单查区修区查 线段树单修区查区修单查 区间加法区间乘法区间根号 并查集普通并查集路径压缩按秩合并 树上问题树的直径树的重心 LCA(最近公共祖先) 基本模板
快读
namespace IN{const int MAX_INPUT1000000;#define getc()(p1p2(p2(p1buf)inbuf-sgetn(buf,MAX_INPUT),p1p2)?EOF:*p1)char buf[MAX_INPUT],*p1,*p2;templatetypename Tinline bool read(Tx){static std::streambuf*inbufcin.rdbuf();x0;register int f0,flagfalse;register char chgetc();while(!isdigit(ch)){if(ch-){f1;}chgetc();}if(isdigit(ch)){xx*10ch-0;chgetc();flagtrue;}while(isdigit(ch)){xx*10ch-48;chgetc();}xf?-x:x;return flag;}templatetypename T,typename ...Argsinline bool read(Ta,Args ...args){return read(a)read(args...);}#undef getc
}
using namespace IN;快写
namespace OUT{templatetypename Tinline void put(T x){static std::streambuf *outbufcout.rdbuf();static char stack[21];static int top0;if(x0){outbuf-sputc(-);x-x;}if(!x){outbuf-sputc(0);outbuf-sputc(\n);return;}while(x){stack[top]x%100;x/10;}while(top){outbuf-sputc(stack[top]);--top;}outbuf-sputc(\n);}inline void putc(const char ch){static std::streambuf *outbufcout.rdbuf();outbuf-sputc(ch);}inline void putstr(string s){for(register int i0;is.length();i) putc(s[i]);}templatetypename Tinline void put(const char ch,T x){static std::streambuf *outbufcout.rdbuf();static char stack[21];static int top 0;if(x0){outbuf-sputc(-);x-x;}if(!x){outbuf-sputc(0);outbuf-sputc(ch);return;}while(x){stack[top]x%100;x/10;}while(top){outbuf-sputc(stack[top]);--top;}outbuf-sputc(ch);}templatetypename T,typename ...Args inline void put(T a,Args ...args){put(a);put(args...);}templatetypename 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_INPUT1000000;#define getc()(p1p2(p2(p1buf)inbuf-sgetn(buf,MAX_INPUT),p1p2)?EOF:*p1)char buf[MAX_INPUT],*p1,*p2;templatetypename Tinline bool read(Tx){static std::streambuf*inbufcin.rdbuf();x0;register int f0,flagfalse;register char chgetc();while(!isdigit(ch)){if(ch-){f1;}chgetc();}if(isdigit(ch)){xx*10ch-0;chgetc();flagtrue;}while(isdigit(ch)){xx*10ch-48;chgetc();}xf?-x:x;return flag;}templatetypename T,typename ...Argsinline bool read(Ta,Args ...args){return read(a)read(args...);}#undef getc
}
namespace OUT{templatetypename Tinline void put(T x){static std::streambuf *outbufcout.rdbuf();static char stack[21];static int top0;if(x0){outbuf-sputc(-);x-x;}if(!x){outbuf-sputc(0);outbuf-sputc(\n);return;}while(x){stack[top]x%100;x/10;}while(top){outbuf-sputc(stack[top]);--top;}outbuf-sputc(\n);}inline void putc(const char ch){static std::streambuf *outbufcout.rdbuf();outbuf-sputc(ch);}inline void putstr(string s){for(register int i0;is.length();i) putc(s[i]);}templatetypename Tinline void put(const char ch,T x){static std::streambuf *outbufcout.rdbuf();static char stack[21];static int top 0;if(x0){outbuf-sputc(-);x-x;}if(!x){outbuf-sputc(0);outbuf-sputc(ch);return;}while(x){stack[top]x%100;x/10;}while(top){outbuf-sputc(stack[top]);--top;}outbuf-sputc(ch);}templatetypename T,typename ...Args inline void put(T a,Args ...args){put(a);put(args...);}templatetypename 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)
#includebits/stdc.h
#define int long long
#define ofr(x,y,z) for(int xy;xz;x)
#define rfr(x,y,z) for(int xy;xz;x--)
using namespace std;
namespace IN{const int MAX_INPUT1000000;#define getc()(p1p2(p2(p1buf)inbuf-sgetn(buf,MAX_INPUT),p1p2)?EOF:*p1)char buf[MAX_INPUT],*p1,*p2;templatetypename Tinline bool read(Tx){static std::streambuf*inbufcin.rdbuf();x0;register int f0,flagfalse;register char chgetc();while(!isdigit(ch)){if(ch-){f1;}chgetc();}if(isdigit(ch)){xx*10ch-0;chgetc();flagtrue;}while(isdigit(ch)){xx*10ch-48;chgetc();}xf?-x:x;return flag;}templatetypename T,typename ...Argsinline bool read(Ta,Args ...args){return read(a)read(args...);}#undef getc
}
namespace OUT{templatetypename Tinline void put(T x){static std::streambuf *outbufcout.rdbuf();static char stack[21];static int top0;if(x0){outbuf-sputc(-);x-x;}if(!x){outbuf-sputc(0);outbuf-sputc(\n);return;}while(x){stack[top]x%100;x/10;}while(top){outbuf-sputc(stack[top]);--top;}outbuf-sputc(\n);}inline void putc(const char ch){static std::streambuf *outbufcout.rdbuf();outbuf-sputc(ch);}inline void putstr(string s){for(register int i0;is.length();i){putc(s[i]);}}templatetypename Tinline void put(const char ch,T x){static std::streambuf *outbufcout.rdbuf();static char stack[21];static int top0;if(x0){outbuf-sputc(-);x-x;}if(!x){outbuf-sputc(0);outbuf-sputc(ch);return;}while(x){stack[top]x%100;x/10;}while(top){outbuf-sputc(stack[top]);--top;}outbuf-sputc(ch);}templatetypename T,typename ...Args inline void put(T a,Args ...args){put(a);put(args...);}templatetypename 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 jlower_bound(a1,an1,m)-a;
int kupper_bound(a1,an1,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(a1,an1,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;NodeT* next;Node(T data) {this-data data;next nullptr;}
};
// 链表类
template typename T
class LinkedList {
private:NodeT* head;NodeT* tail;int size;
public:LinkedList() {head nullptr;tail nullptr;size 0;}void add(T data) {NodeT* new_node new NodeT(data);if (size 0) {head new_node;tail new_node;} else {tail-next new_node;tail new_node;}size;}void remove(T data) {NodeT* prev nullptr;NodeT* 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() {NodeT* curr head;while (curr ! nullptr) {cout curr-data ;curr curr-next;}cout endl;}
};双向链表
// 节点类
template typename T
class Node {
public:T data;NodeT* prev;NodeT* next;Node(T data) {this-data data;prev nullptr;next nullptr;}
};
// 链表类
template typename T
class DoublyLinkedList {
private:NodeT* head;NodeT* tail;int size;
public:DoublyLinkedList() {head nullptr;tail nullptr;size 0;}void add(T data) {NodeT* new_node new NodeT(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) {NodeT* prev nullptr;NodeT* 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() {NodeT* 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 i1;in;i) {cinchildfather;a[child].parentfather;a[father].children.push_back(child);
}求二叉树深度
void dfs(int x,int deep) {dmax(d,deep);if(a[x].left) {dfs(a[x].left,deep1);}if(a[x].right) {dfs(a[x].right,deep1);}
}求二叉树先序遍历
void recursion(struct BinaryNode *root) {if(rootNULL) {return;}printf(%c\n,root-ch);recursion(root-lChild);recursion(root-rChild);
}求二叉树中序遍历
void recursion(struct BinaryNode *root) {if(rootNULL) {return;}recursion(root-lChild);printf(%c\n,root-ch);recursion(root-rChild);
}求二叉树后序遍历
void recursion(struct BinaryNode *root) {if(rootNULL) {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 q q 是优先队列.
int huffman(int x) {int res0;for (int i0;in-1;i) {int xq.top();q.pop();int yq.top();q.pop();int addxy;resadd;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);}}
}树状数组
单修区查
#includebits/stdc.h
using namespace std;
int const maxn500005;
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 iu;in;ilowbit(i)) {c[i]v;}
}
long long sum(int u) {int ans0;for (int iu;i0;i-lowbit(i)) {ansc[i];}return ans;
}
int main() {cinnm;for (int i1;in;i) {cina;add(i,a);}for (int i1;im;i) {cinpxy;if(p1) {add(x,y);}if(p2) {coutsum(y)-sum(x-1)endl;}}return 0;
}区修单查
#includebits/stdc.h
using namespace std;
#define lowbit(x) x(-x)
using lllong long;
long long n,q,f,a[1000005],l,r,x,p,b[1000005];
long long c[1000005];
int main() {cinnq;for (int i1;in;i) {cina[i];b[i]a[i]-a[i-1];for (int ji;jn;jlowbit(j)) {c[j]b[i];}}for (int i1;iq;i) {cinf;if(f1) {cinlrx;for (int jl;jn;jlowbit(j)) {c[j]x;}for (int jr1;jn;jlowbit(j)) {c[j]-x;}} else {cinp;long long ans0;for (int jp;j1;j-lowbit(j)) {ansc[j];}coutansendl;}}return 0;
}区修区查
#includebits/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 ix;in;ilowbit(i)) {c1[i]k,c2[i]k*(x-1);}
}
long long getsum(long long x) {long long ans0;for (long long ix;i1;i-lowbit(i)) {ans(c1[i]*x-c2[i]);}return ans;
}
int main() {cinnm;for (long long i1;in;i) {cina[i];ba[i]-a[i-1];update(i,b);}for (long long i1;im;i) {cinflr;if(f1) {cinx;update(l,x);update(r1,-x);} else {coutgetsum(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) aread()
#define REP(i,k,n) for (long long ik;in;i)
#define DREP(i,k,n) for (long long ik;in;i--)
#define cl(a) memset(a,0,sizeof(a))
inline long long read() {long long x0,f1;char chgetchar();for (;!isdigit(ch);chgetchar()) if(ch-) f-1;for (;isdigit(ch);chgetchar()) xx*10ch-0;return x*f;
}
inline void out(long long x) {if(x0) putchar(-),x-x;if(x9) out(x/10);putchar(x%100);
}
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].ll;tree[i].rr;tree[i].mlz1;if(lr) {tree[i].suminput[l]%p;return ;}long long mid(lr)1;build(i1,l,mid);build(i1|1,mid1,r);tree[i].sum(tree[i1].sumtree[i1|1].sum)%p;return ;
}
inline void pushdown(long long i) {long long k1tree[i].mlz,k2tree[i].plz;tree[i1].sum(tree[i1].sum*k1k2*(tree[i1].r-tree[i1].l1))%p;tree[i1|1].sum(tree[i1|1].sum*k1k2*(tree[i1|1].r-tree[i1|1].l1))%p;tree[i1].mlz(tree[i1].mlz*k1)%p;tree[i1|1].mlz(tree[i1|1].mlz*k1)%p;tree[i1].plz(tree[i1].plz*k1k2)%p;tree[i1|1].plz(tree[i1|1].plz*k1k2)%p;tree[i].plz0;tree[i].mlz1;return ;
}
inline void mul(long long i,long long l,long long r,long long k) {if(tree[i].rl || tree[i].lr) return ;if(tree[i].ll tree[i].rr) {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[i1].rl) mul(i1,l,r,k);if(tree[i1|1].lr) mul(i1|1,l,r,k);tree[i].sum(tree[i1].sumtree[i1|1].sum)%p;return ;
}
inline void add(long long i,long long l,long long r,long long k) {if(tree[i].rl || tree[i].lr) return ;if(tree[i].ll tree[i].rr) {tree[i].sum((tree[i].r-tree[i].l1)*k)%p;tree[i].plz(tree[i].plzk)%p;return ;}pushdown(i);if(tree[i1].rl) add(i1,l,r,k);if(tree[i1|1].lr) add(i1|1,l,r,k);tree[i].sum(tree[i1].sumtree[i1|1].sum)%p;return ;
}
inline long long search(long long i,long long l,long long r) {if(tree[i].rl || tree[i].lr) return 0;if(tree[i].ll tree[i].rr)return tree[i].sum;pushdown(i);long long sum0;if(tree[i1].rl) sumsearch(i1,l,r)%p;if(tree[i1|1].lr) sumsearch(i1|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(fl1) {in(a);in(b);in(c);c%p;mul(1,a,b,c);}if(fl2) {in(a);in(b);in(c);c%p;add(1,a,b,c);}if(fl3) {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].num0;tree[index].leftleft;tree[index].rightright;if(leftright)return ;int mid(rightleft)/2;build(left,mid,index*2);build(mid1,right,index*21);
}
void pls(int index,int l,int r,int k) {if(tree[index].leftl tree[index].rightr) {tree[index].numk;return ;}if(tree[index*2].rightl)pls(index*2,l,r,k);if(tree[index*21].leftr)pls(index*21,l,r,k);
}
void search(int index,int dis) {anstree[index].num;if(tree[index].lefttree[index].right)return ;if(distree[index*2].right)search(index*2,dis);if(distree[index*21].left)search(index*21,dis);
}
int main() {int n,m;cinnm;build(1,n,1);for (int i1;in;i)scanf(%d,input[i]);for (int i1;im;i) {int a;scanf(%d,a);if(a1) {int x,y,z;scanf(%d%d%d,x,y,z);pls(1,x,y,z);}if(a2) {ans0;int x;scanf(%d,x);search(1,x);printf(%d\n,ansinput[x]);}}
}区间加法
#includebits/stdc.h
using namespace std;
typedef long long ll;
const ll N1e67;
const ll mod2147483647;
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].lz0;//初始化的时候肯定都是0tree[i].ll;tree[i].rr;if(lr) {tree[i].sumarr[l];//到达底部单节点才把输入的值赋给你return ;}ll mid(lr)/2;build(i*2,l,mid,arr);build(i*21,mid1,r,arr);tree[i].sumtree[i*2].sumtree[i*21].sum;//树已经全部建完了再从下往上使得上层的树都有了值return ;
}
inline void push_down(ll i) {if(tree[i].lz!0) {tree[i*2].lztree[i].lz;tree[i*21].lztree[i].lz;ll mid(tree[i].ltree[i].r)/2;tree[i*2].sumtree[i].lz*(mid-tree[i*2].l1);tree[i*21].sumtree[i].lz*(tree[i*21].r-mid);tree[i].lz0;}return ;
}
inline void add(ll i,ll l,ll r,ll k) {if(tree[i].lltree[i].rr) {tree[i].sumk*(tree[i].r-tree[i].l1);tree[i].lzk;return ;}push_down(i);if(tree[i*2].rl)add(i*2,l,r,k);if(tree[i*21].lr)add(i*21,l,r,k);tree[i].sumtree[i*2].sumtree[i*21].sum;return ;
}
inline ll searchs(ll i,ll l, ll r) {if(tree[i].lltree[i].rr)return tree[i].sum;push_down(i);ll num0;if(tree[i*2].rl)numsearchs(i*2,l,r);if(tree[i*21].lr)numsearchs(i*21,l,r);return num;
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnm;for (int i1;in;i)cinarr[i];build(1,1,n,arr);//从根节点开始建树for (int i1;im;i) {ll tmp;cintmp;if(tmp1) {ll a,b,c;cinabc;add(1,a,b,c);//每次修改都是从编号为1开始的因为编号1是树的顶端往下分叉}if(tmp2) {ll a,b;cinab;printf(%lld\n,searchs(1,a,b));//编号i的话每次都是从1开始}}return 0;
}区间乘法
#includebits/stdc.h
using namespace std;
typedef long long ll;
const ll N1e67;
templatetypename Tvoid read(T x) {x0;char chgetchar();ll f1;while(!isdigit(ch)) {if(ch-)f-1;chgetchar();}while(isdigit(ch)) {x(x1)(x3)(ch^48);chgetchar();}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].ll;tree[i].rr;tree[i].mul1;if(lr) {tree[i].sumarr[l]%mod;return ;}ll mid(lr)1;build(i*2,l,mid);build(i*21,mid1,r);tree[i].sum(tree[i*2].sumtree[i*21].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].l1)*tree[i].add)%mod)%mod;tree[i*21].sum(ll)(tree[i].mul*tree[i*21].sum((tree[i*21].r-tree[i*21].l1)*tree[i].add)%mod)%mod;tree[i*2].mul(ll)(tree[i*2].mul*tree[i].mul)%mod;tree[i*21].mul(ll)(tree[i*21].mul*tree[i].mul)%mod;tree[i*2].add(ll)(tree[i*2].add*tree[i].multree[i].add)%mod;tree[i*21].add(ll)(tree[i*21].add*tree[i].multree[i].add)%mod;tree[i].mul1;tree[i].add0;
}
inline void add(ll i,ll l,ll r,ll k) {if(tree[i].lltree[i].rr) {tree[i].add(ll)(tree[i].addk)%mod;tree[i].sum(ll)(tree[i].sumk*(tree[i].r-tree[i].l1))%mod;return ;}push_down(i);if(tree[i*2].rl)add(i*2,l,r,k);if(tree[i*21].lr)add(i*21,l,r,k);//ll mid(tree[i].ltree[i].r)1;//if(lmid)add(i*2,l,r,k);//if(midr)add(i*21,l,r,k);tree[i].sum(tree[i*2].sumtree[i*21].sum)%mod;
}
inline void mult(ll i,ll l,ll r,ll k) {if(tree[i].lltree[i].rr) {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].rl)mult(i*2,l,r,k);if(tree[i*21].lr)mult(i*21,l,r,k);//ll mid(tree[i].ltree[i].r)1;//if(lmid)mult(i*2,l,r,k);//if(midr)mult(i*21,l,r,k);tree[i].sum(tree[i*2].sumtree[i*21].sum)%mod;
}
inline ll query(ll i,ll l,ll r) {if(tree[i].lltree[i].rr)return tree[i].sum;push_down(i);ll num0;if(tree[i*2].rl)num(numquery(i*2,l,r))%mod;if(tree[i*21].lr)num(numquery(i*21,l,r))%mod;return num;//ll val0;//ll mid(tree[i].ltree[i].r)1;//if(lmid)val(valquery(i*2,l,r))%mod;//if(midr)val(valquery(i*21,l,r))%mod;//return val;
}
int main() {read(n),read(m),read(mod);for (int i1;in;i)read(arr[i]);build(1,1,n);for (int i1;im;i) {read(flag);if(flag1) {read(cn),read(cm),read(cw);mult(1,cn,cm,cw);} else if(flag2) {read(cn),read(cm),read(cw);add(1,cn,cm,cw);} else {read(cn),read(cm);coutquery(1,cn,cm)endl;}}
}区间根号
#includebits/stdc.h
#define MAXN 1000010
#define REP(i,k,n) for (int ik;in;i)
#define in(a) aread()
using namespace std;
int read() {int x0,f1;char chgetchar();for (;!isdigit(ch);chgetchar())if(ch-)f-1;for (;isdigit(ch);chgetchar())xx*10ch-0;return x*f;
}
struct node {int l,r;long long lz,sum,maxx,minn;
}
tree[MAXN2];
int n,m,input[MAXN];
inline void build(int i,int l,int r) {tree[i].ll;tree[i].rr;if(lr) {tree[i].sumtree[i].minntree[i].maxxinput[l];return ;}int mid(lr)1;build(i*2,l,mid);build(i*21,mid1,r);tree[i].sumtree[i*2].sumtree[i*21].sum;tree[i].minnmin(tree[i*2].minn,tree[i*21].minn);tree[i].maxxmax(tree[i*2].maxx,tree[i*21].maxx);return ;
}
inline void push_down(int i) {if(!tree[i].lz) return ;long long ktree[i].lz;tree[i*2].lzk;tree[i*21].lzk;tree[i*2].sum-(tree[i*2].r-tree[i*2].l1)*k;tree[i*21].sum-(tree[i*21].r-tree[i*21].l1)*k;tree[i*2].minn-k;tree[i*21].minn-k;tree[i*2].maxx-k;tree[i*21].maxx-k;tree[i].lz0;return ;
}
inline void Sqrt(int i,int l,int r) {if(tree[i].ll tree[i].rr (tree[i].minn-(long long)sqrt(tree[i].minn))(tree[i].maxx-(long long)sqrt(tree[i].maxx))) {long long utree[i].minn-(long long)sqrt(tree[i].minn);tree[i].lzu;tree[i].sum-(tree[i].r-tree[i].l1)*u;tree[i].minn-u;tree[i].maxx-u;//coutii tree[i].sumendl;return ;}if(tree[i].rl || tree[i].lr) return ;push_down(i);if(tree[i*2].rl) Sqrt(i*2,l,r);if(tree[i*21].lr) Sqrt(i*21,l,r);tree[i].sumtree[i*2].sumtree[i*21].sum;tree[i].minnmin(tree[i*2].minn,tree[i*21].minn);tree[i].maxxmax(tree[i*2].maxx,tree[i*21].maxx);//coutii tree[i].sumendl;return ;
}
inline long long search(int i,int l,int r) {if(tree[i].ll tree[i].rr)return tree[i].sum;if(tree[i].rl || tree[i].lr) return 0;push_down(i);long long s0;if(tree[i*2].rl) ssearch(i*2,l,r);if(tree[i*21].lr) ssearch(i*21,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(a1)printf(%lld\n,search(1,b,c));if(a2) {Sqrt(1,b,c);//for(int i1;i7;i)// couttree[i].sum ;// coutendl;}}
}并查集
普通并查集
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 xxfind(x);int yyfind(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];
vectorint 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];
vectorint 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::vectorint v[MXN];
std::vectorint 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那么 xy 就都是它们自己的祖先。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;
}目前先整理到这了,下次整理剩下的
