codebook

pq_vser.cpp

struct vser{
	bool operator()(INT a,INT b){
		return a.id>b.id;
	}
};
priority_queue<INT,vector<INT>,vser> pq;

basic.cpp

/*
[q]
[]
*/
//#ifndef eval
#include<bits/stdc++.h>
using namespace std;
#define INT long long int
#define endl "\n"
#define read(n) reader<n>()
#define DBG if(debug)
#define PII pair<INT,INT>
bool debug=0;
bool noTLE=1;
template<typename tpe>tpe reader(){
	tpe re;cin>>re;return re;
}

int main(int argc,char** argv){
	for(int i=0;i<argc;i++){
		string nwstr=argv[i];
		if(nwstr=="-Dev"){
			debug=1;
			noTLE=0;
		}else if(nwstr=="-TLE"){
			noTLE=0;
		}
	}
	if(noTLE && !debug)cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	DBG{
		cout<<"Temp by KagariET01"<<endl;
		cout<<"My Webpage: https://kagariet01.github.io/about"<<endl;
		cout<<"===DBG mod on==="<<endl;
		cout<<"Here's your CFG"<<endl;
		for(int i=0;i<argc;i++){
			string nwstr=argv[i];
			cout<<'['<<nwstr<<']'<<endl;
		}
		cout<<"===Code start==="<<endl;
	}
	INT t=read(int);
	while(t--){
	}
	return 0;
}
//#endif

DP

LCS_1.cpp

/*
[LCS]
[最長共用子序列]
string s,t;
INT dp[3001][3001];
bool debug=false;
/*fn定義*/
void lcs(INT n,INT m){
	for(INT i=1;i<=n;i++){
		for(INT j=1;j<=m;j++){
			if(s[i-1]==t[j-1]){
				dp[i][j]=dp[i-1][j-1]+1;
			}else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
}
void printdp(INT n,INT m){
	if(debug){
		for(INT i=0;i<=n;i++){
			for(INT j=0;j<=m;j++){
				cout<<dp[i][j]<<",";
			}
			cout<<endl;
		}
		cout<<endl;
	}
}
string backlcs(INT n,INT m){
	string re="";
	INT i=n,j=m;
	while(i && j){
		if(s[i-1]==t[j-1]){
			re.push_back(s[i-1]);
			i--;
			j--;
		}else{
			if(dp[i-1][j]>=dp[i][j-1]){
				i--;
			}else j--;
		}
	}
	reverse(re.begin(),re.end());
	return re;
}
/*main*/
int main(){
	/*IO加速*/
	if(!debug)> > > {cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);}
	/*CIN*/
	cin>>s>>t;
	/*solve*/
	INT ss=s.length(),ts=t.length();
	lcs(ss,ts);
	printdp(ss,ts);
	cout<<backlcs(ss,ts);
	return 0;
}

LIS_1.cpp

/*
[LIS]
[最長遞增子序列] 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//cin
	int num;
	vector<int> a;
	while (cin >> num){
		a.push_back(num);
	}
	//solve
	int N = (int) a.size();//計算DP大小
	int dp[N+1];//建立dp
	vector<int> v;//已走訪過的數字
	dp[0] = 1;//dp初始化
	v.push_back(a[0]);//v初始化

	int L = 1; //LIS length
	//L為長度
	for (int i=1; i<N; i++){
		if (a[i] > v.back()){//如果現在這個大於v最頂端的
			v.push_back(a[i]);//先將自己推進v
			L++;//長度增加
			dp[i] = L;
		} else {
			auto it = lower_bound(v.begin(), v.end(), a[i]);//尋找v裡面最第一個大於等於她的數
			*it = a[i];//將此數換成更小的數(自己)
			dp[i] = (int) (it - v.begin() + 1);//計算長度，因為此vector是遞增子序列，直接量他的size就可以了
		}
	}
	cout << L << "\n-\n";
	//尋找順序
	vector<int> ans;
	for (int i=N-1; i>=0; i--){//由後往前
		if (dp[i] == L){
			ans.push_back(a[i]);//找到的話就把元素塞進ans
			L--;
		}
	}
	reverse(ans.begin(), ans.end());//ans反向
	//輸出順序
	for (auto i: ans){
		cout << i << '\n';
	}
	return 0;
}

math

mod

Extended_Euclidean.cpp

/*
[擴展歐幾里得]https://zh.wikipedia.org/wiki/扩展欧几里得算法#算法和举例
*/

#include<iostream>
template<typename TPE>std::pair<TPE,std::pair<TPE,TPE>> Extended_Euclidean(TPE a,TPE b){
	TPE lst[3][3]={
		{a,1,0},
		{b,0,1},
		{0,0,0}
	};
	int i=2;
	for(i=2;lst[(i+2)%3][0];i=(i+1)%3){
		TPE q=lst[(i+1)%3][0]/lst[(i+2)%3][0];
		lst[i][0]=lst[(i+1)%3][0]-lst[(i+2)%3][0]*q;
		lst[i][1]=lst[(i+1)%3][1]-lst[(i+2)%3][1]*q;
		lst[i][2]=lst[(i+1)%3][2]-lst[(i+2)%3][2]*q;
	}
	i=(i+1)%3;
	std::pair<TPE,std::pair<TPE,TPE>> re={lst[i][0],{lst[i][1],lst[i][2]}};
	re=(re%b+b)%b
	return re;
}
int main(){
	int a,b;
	std::cin>>a>>b;
	std::pair<int,std::pair<int,int>> ans=Extended_Euclidean(a,b);
	std::cout<<ans.first<<" "<<ans.second.first<<" "<<ans.second.second<<std::endl;
}

Modular_multiplicative_inverse.cpp

/*
[求反模逆元 a^(-1) mod n]
*/

#include<iostream>

template<typename TPE>std::pair<TPE,std::pair<TPE,TPE>> Extended_Euclidean(TPE a,TPE b){//擴展歐幾里得
	TPE lst[3][3]={
		{a,1,0},
		{b,0,1},
		{0,0,0}
	};
	int i=2;
	for(i=2;lst[(i+2)%3][0];i=(i+1)%3){
		TPE q=lst[(i+1)%3][0]/lst[(i+2)%3][0];
		lst[i][0]=lst[(i+1)%3][0]-lst[(i+2)%3][0]*q;
		lst[i][1]=lst[(i+1)%3][1]-lst[(i+2)%3][1]*q;
		lst[i][2]=lst[(i+1)%3][2]-lst[(i+2)%3][2]*q;
	}
	i=(i+1)%3;
	std::pair<TPE,std::pair<TPE,TPE>> re={lst[i][0],{lst[i][1],lst[i][2]}};
	return re;
}

template<typename TPE>TPE Modular_multiplicative_inverse(TPE a,TPE n){//用擴展歐幾里得求模逆元
	std::pair<TPE,std::pair<TPE,TPE>> ans=Extended_Euclidean(a,n);
	TPE re=ans.second.first;
	re=(re%n+n)%n;
	if(ans.first==1)return re;
	else return -1;
}


int main(){
	int a,b;
	std::cin>>a>>b;
	int ans=Modular_multiplicative_inverse(a,b);
	std::cout<<ans<<std::endl;
}

Geometry.cpp

/*
[Q]
[]
*/
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
#define INT long long int
#define endl "\n"
#define read(n) reader<n>()
template<typename TPE>TPE reader(){
	TPE re;cin>>re;return re;
}
bool debug=0;


/*
	eps=浮點數誤差值
*/
const double eps=1e-9;//浮點數誤差

/*
	向量Vec
	也可當點使用
*/
struct Vec{//點、向量
	double x=0,y=0;
	void setv(const double &a,const double &b){
		x=a,y=b;
	}
};
Vec make_Vec(const double &a,const double &b){
	Vec re;
	re.x=a,re.y=b;
	return re;
}

struct Seg{//線段
	Vec p1,p2;
};

Seg make_Seg(Vec a,Vec b){//將兩點Vec合併成線段Seg
	Seg re;
	re.p1=a;
	re.p2=b;
	return re;
}

/*
	基本運算
*/
Vec operator-(const Vec &a,const Vec &b){
	Vec re;
	re.x=b.x-a.x;
	re.y=b.y-a.y;
	return re;
}
Vec operator+(const Vec &a,const Vec &b){
	Vec re;
	re.x=b.x+a.x;
	re.y=b.y+a.y;
	return re;
}
Vec operator*(const Vec &a,const double &n){
	return make_Vec(a.x*n,a.y*n);
}
Vec operator*(const double &n,const Vec &a){
	return a*n;
}
Vec operator/(const Vec &a,const double &n){
	return make_Vec(a.x/n,a.y/n);
}
Vec operator/(const double &n,const Vec &a){
	return a/n;
}
bool operator<(const Vec &a,const Vec &b){
	return (a.x*a.x+a.y*a.y)<(b.x*b.x+b.y*b.y);
}
bool operator<=(const Vec &a,const Vec &b){
	return (a.x*a.x+a.y*a.y)<=(b.x*b.x+b.y*b.y);
}
bool operator>(const Vec &a,const Vec &b){
	return (a.x*a.x+a.y*a.y)>(b.x*b.x+b.y*b.y);
}
bool operator>=(const Vec &a,const Vec &b){
	return (a.x*a.x+a.y*a.y)>=(b.x*b.x+b.y*b.y);
}
bool operator==(const Vec &a,const Vec &b){
	return (a.x==b.x && a.y==b.y);
}

/*
	內積*
	AB內積=A的長度*B的長度*cos(AB夾角)
	內積=0:兩向量垂直
	內積>0 夾角<90度
	內積<0 夾角>90度
*/
double Dot(const Vec &a,const Vec &b){
	return a.x*b.x+a.y*b.y;
}
double operator*(const Vec &a,const Vec &b){
	return Dot(a,b);
}

/*
	外積^
	AB外積=A的長度*B的長度*sin(AB夾角)=OAB三角形面積
	B的長度*sin(AB夾角)=OAB的高(底為OA)

	外積=0:兩向量平行
	外積>0 B 向量在 A 向量的逆時針方向
	外積<0 B 向量在 A 向量的順時針方向
*/
double cross(const Vec &a,const Vec &b){
	return a.x*b.y-a.y*b.x;
}
double operator^(const Vec &a,const Vec &b){
	return cross(a,b);
}

/*
	多邊形Polygon
	裡面存的是點
*/
struct Polygon{//建立多邊形Polygon
	vector<Vec> vec;
	void push_back(Vec a){
		vec.push_back(a);
	}
	void push_back(double x,double y){
		vec.push_back(make_Vec(x,y));
	}
	long long int size(){
		return vec.size();
	}
	Vec back(){
		return vec.back();
	}
	bool empty(){
		return vec.empty();
	}
	void pop_back(){
		vec.pop_back();
	}
	void pop_front(){
		vec.erase(vec.begin());
	}
	Vec front(){
		return vec.front();
	}
	vector<Vec>::iterator begin(){
		return vec.begin();
	}
	vector<Vec>::iterator end(){
		return vec.end();
	}
	Vec operator[](unsigned long long int n){
		return vec[n];
	}
};

/*
	面積Area
	將O(0,0)視為開始點
	連線向量O->P_1和O->P_2......
	對向量V1和V2計算三角形面積
	全部總和即為所求
*/
double Area(Polygon Pol){//對Polygon計算面積
	double re=0;
	long long int Polsz=Pol.size();
	if(Polsz==0)return 0;
	for(INT i=0;i<Polsz;i++){
		re+=Pol.vec[i]^Pol.vec[(i+1)%Polsz];
	}
	return fabs(re/2);
}

/*
	判斷方向ori
	第一行：值取絕對值之後，誤差小於eps就算是0
	o代表旋轉點，a代表點a,b代表點b
	判斷oa轉道ob要轉哪個方向
*/
int sign(double a){//對double簡化成-1,0,1
	if(fabs(a)<eps)return 0;
	else return a>0?1:-1;
}
int ori(const Vec &o,const Vec &a,const Vec &b){//判斷方向，0為同向or 180，1為逆時針，-1為順時針
	return sign((a-o)^(b-o));
}

/*
	點C是否在線AB上btw
	以c為中心點，a和b不在同個方向，那答案一定是False
	最後檢查角度，如果角度>90，那就一定是180，也就是C在AB上
	如果角度<90，那就一定是0，就代表C不在AB上
*/
bool btw(const Vec &pa,const Vec &pb,const Vec &pc){//檢測C是否在AB上
	if(ori(pc,pa,pb))return false;
	else return ((pa-pc)*(pb-pc))<=0;
}
bool btw(const Seg &la,const Vec &p){
	return btw(la.p1,la.p2,p);
}

/*
	檢測是否相交Banana
	考慮下面幾種情況

	    C
	    |
	  A-+-B
	    |
	    D

	  A---B
	    C
	    |
	    D

	我們可以發現，以A為中心，連到B,C,D
	可以發現C一定要在B的逆時針方向(or順時針)
	而D則在B的另一方向
	同理，其他點也一樣
	將方向改成數值表示
	一個一定會是-1
	另一個一定會是1
	相乘就是-1
	我們只要判斷相乘是不是<0即可
	
	另一種情況

	  A-C-B
	    |
	    D
	如果有一個點(C)在線上(AB)
	那另外一個點(D)在哪都行(可-1可1)
	對於剛剛的判斷式，只要把<0改成<=0即可
	那還有另一種情況如下

	  A-C=B-D
	
	

*/
bool havebanana(const Vec &pa,const Vec &pb,const Vec &pc,const Vec &pd){//檢測兩線段是否相交
	int a123=ori(pa,pb,pc);
	int a124=ori(pa,pb,pd);
	int a341=ori(pc,pd,pa);
	int a342=ori(pc,pd,pb);
	if(a123==0 && a124==0){
		return btw(pa,pb,pc)||btw(pa,pb,pd)||btw(pc,pd,pa)||btw(pc,pd,pb);
	}else return a123*a124<=0 && a341*a342<=0;
}
bool havebanana(const Seg &la,const Seg &lb){
	return havebanana(la.p1,la.p2,lb.p1,lb.p2);
}

/*
	取得交點getbanana
		考慮下面幾種情況

	    C
	   /|\
	  A-E-B
	   \|/
	    D
	求AB和CD交點
	AE:EB=CAD:CBD
	E=(A*CBD+B*CAD)/(CAD+CBD)
*/
pair<bool,Vec> getbanana(const Vec &pa,const Vec &pb,const Vec &pc,const Vec &pd){
	pair<bool,Vec> re;
	re.first=havebanana(pa,pb,pc,pd);
	if(!re.first)return re;
	double CBD=fabs((pc-pb)^(pd-pb));
	double CAD=fabs((pc-pa)^(pd-pa));
	re.second=(pa*CBD+pb*CAD)/(CAD+CBD);
	return re;
}
pair<bool,Vec> getbanana(const Seg &la,const Seg &lb){
	return getbanana(la.p1,la.p2,lb.p1,lb.p2);
}

/*
	角度弧度轉換器
	弧度沒單位
	2pi=360度
	(2pi是弧度)
	同理，pi=180度
	1=180/pi度
	pi/180=1度
*/
double deg_rad(double angle){//角度轉弧度
	return angle*M_PI/180;
}
double rad_deg(double angle){//弧度轉角度
	return angle*180/M_PI;
}

Vec abs(Vec P){//對向量取絕對值
	P.x=fabs(P.x);
	P.y=fabs(P.y);
	return P;
}
double lng(Vec P){
	P=abs(P);
	return sqrt(P.x*P.x+P.y*P.y);
}

/*
	點到線段距離
	考慮下面幾種情況
	C
	    A-B
	我們可以知道角BAC是鈍角時，C和AB的最短距離就是CA
	同理，當ABC為鈍角時，答案即為BC
*/
double Pnt_to_Lne(const Vec &P,const Vec &A,const Vec &B){//計算點到線最近距離
	int BAP=sign((B-A)*(P-A));
	int ABP=sign((A-B)*(P-B));
	if(sign(lng(A-B))==0)return lng(P-A);//如果A==B
	if(BAP>=0 && ABP>=0){
		return fabs(((A-P)^(B-P))/lng(A-B));
	}else return lng(min(abs(A-P),abs(B-P)));
}
double Pnt_to_Lne(const Vec &P,const Seg  la){
	return Pnt_to_Lne(P,la.p1,la.p2);
}

bool sorta(Vec a,Vec b){//先以x降序排序，再以y升序排序
	if(a.x==b.x)return a.y>b.y;
	else return a.x<b.x;
}
bool sortb(Vec a,Vec b){//先以x升序排序，再以y降序排序
	if(a.x==b.x)return a.y<b.y;
	else return a.x>b.x;
}

Polygon convex(Polygon Pol){
	Polygon re;
	sort(Pol.vec.begin(),Pol.vec.end(),sorta);
	re.vec.push_back(Pol.vec[0]);
	long long int n=Pol.vec.size();
	for(INT i=1;i<n;i++){
		if(re.vec.empty()){
			re.push_back(Pol.vec[i]);
			continue;
		}else if(re.vec.back()==Pol.vec[i]){
			continue;
		}
		while(re.vec.empty() || ori(re.vec.back(),*(re.vec.end()-1),Pol.vec[i])>=0){
			re.vec.pop_back();
		}
		re.vec.push_back(Pol.vec[i]);
	}
	sort(Pol.vec.begin(),Pol.vec.end(),sortb);
	for(INT i=0;i<n;i++){
		if(re.vec.empty()){
			re.vec.push_back(Pol.vec[i]);
			continue;
		}else if(re.vec.back()==Pol.vec[i]){
			continue;
		}
		while(re.vec.empty() || ori(re.vec.back(),*(re.vec.end()-1),Pol.vec[i])>=0){
			re.vec.pop_back();
		}
		re.push_back(Pol.vec[i]);
	}
	return re;
}

int main(){
	/*cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	INT t=read(INT);
	while(t--){
	}*/
	if(0){//測試Area
		Polygon Pol;
		Pol.push_back(1,2);
		Pol.push_back(1,3);
		Pol.push_back(2,1);
		cout<<Area(Pol)<<endl;
	}
	if(0){//測試sign
		cout<<sign(-1e-9)<<endl;
		cout<<sign(1e-9)<<endl;
		cout<<sign(-1e-10)<<endl;//誤差值內都會算做0
	}
	if(0){//測試ori
		Vec O=make_Vec(0,0);
		Vec A=make_Vec(5,0);
		Vec B=make_Vec(-5,0);
		cout<<ori(O,A,B)<<endl;//1為逆時針，-1為順時針，0為同向or 180
	}
	if(0){//測試btw
		Vec A=make_Vec(3,6);
		Vec B=make_Vec(7,8);
		Vec C=make_Vec(5,8);
		Seg Lne=make_Seg(A,B);
		if(btw(Lne,C)){
			cout<<"True"<<endl;
		}else{
			cout<<"False"<<endl;
		}
	}
	if(0){//測試banana
		Vec A=make_Vec(-1,3);
		Vec B=make_Vec(-5,4);
		Vec C=make_Vec(1,4);
		Vec D=make_Vec(5,2);
		Seg L1=make_Seg(A,B);
		Seg L2=make_Seg(C,D);
		pair<bool,Vec> re=getbanana(L1,L2);
		if(re.first){
			cout<<"Banana is:("<<re.second.x<<","<<re.second.y<<")"<<endl;
		}else{
			cout<<"No Banana"<<endl;
		}
	}
	if(0){//測試Pnt_to_Lne
		Vec P=make_Vec(-4,4);
		Vec A=make_Vec(-4,1);
		Vec B=make_Vec(-5,4);
		Seg L1=make_Seg(A,B);
		cout<<Pnt_to_Lne(P,L1)<<endl;
	}
	if(1){//測試convex
	      	Polygon pol;
		while(true){
			cout<<"enter point> ";
			long long int xx,yy;
			cin>>xx>>yy;
			if(xx==0 && yy==0)break;
			pol.vec.push_back(make_Vec(xx,yy));
		}
		cout<<"counting"<<endl;
		Polygon ans=convex(pol);
		cout<<"ans:"<<endl;
		for(Vec i:ans.vec){
			cout<<"("<<i.x<<","<<i.y<<")"<<endl;
		}
	}
	return 0;
}

string

z_value.cpp

/*
字串S[0:N-1]的Z-value
Z[i]=( 最大的K滿足S[0:K-1]=S[i:i+k-1] )
假設Z[i]值為n
*/
vector<INT> z_value(string s){
	INT n=s.size();
	INT l=0,r=0;
	vector<INT> z(n);
	for(INT i=1;i<n;i++){
		if(i<=r){
			z[i]=min(z[i-l],r-i+1);
		}
		while(
			i+z[i]<n &&
			s[z[i]]==s[i+z[i]]
		)z[i]++;
		if(i+z[i]-1>r){
			l=i,r=z[i]+i-1;
		}
	}
	return z;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int t=read(int);
	while(t--){
		string str=read(string);
		vector<INT> z=z_value(str);
		for(INT i:z){
			cout<<i<<" ";
		}
		cout<<endl;
	}
	return 0;
}
`trie.cpp`
```c++=
struct trie{
	trie* c[26];
	INT cnt;
	trie(): cnt(0){
		memset(c,0,sizeof(c));
	}
}

INT cha_int(char c){
	return c-'a';
}

void insert(char *ca,trie *root){
	while(*c){
		if(!(*root).c[cha_int(*ca)]){
			(*root).c[cha_int(*ca)]=new trie();
		}
		root=(*root).c[cha_int(*ca)];
		ca++;
	}
	(*root).cnt++;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int t=read(int);
	while(t--){
	}
	return 0;
}

KMP.cpp

vector<INT> getF(string str){
	INT n=str.size();
	vector<INT> re(n,-1);
	for(INT i=1;i<n;i++){
		if(re[i-1]==-1){//上一個位置沒找到F值
				if(str[i]==str[0]){
			re[i]=0;
				}else{
			re[i]=-1;
				}
		}else{
				INT k=re[i-1]+1;
				re[i]=k;
				while(k>=0 && str[k]!=str[i]){
			k=re[k];
			re[i]=k;
				}
		}
	}
	return re;
}

vector<INT> KMS(string s,string t){
	vector<INT> f=getF(s);
	INT ss=s.size();
	INT ts=t.size();
	vector<INT> re;
	INT p=-1;//表s的開頭要在t的哪裡
	for(INT i=0;i<ts;i++){
		while(p>=0 && s[p+1]!=t[i]){//重複移動p直到字元配對成功
			p=f[p];
		}
		if(s[p+1]==t[i]){
			p++;
		}
		if(p+1==ss){
			re.push_back(i-p);
			p=f[p];
		}
	}
	return re;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int t=read(int);
	while(t--){
		string s,t;
		cin>>s>>t;
		vector<INT> vec=KMS(s,t);
		for(INT i:vec){
			cout<<i<<" ";
		}
		cout<<"end"<<endl;
	}
	return 0;
}
//#endif

Failure.cpp

vector<INT> getF(string str){
    INT n=str.size();
    vector<INT> re(n,-1);
    for(INT i=1;i<n;i++){
	if(re[i-1]==-1){
	    if(str[i]==str[0]){
		re[i]=0;
	    }else{
		re[i]=-1;
	    }
	}else{
	    INT k=re[i-1]+1;
	    re[i]=k;
	    while(k>=0 && str[k]!=str[i]){
		k=re[k];
		re[i]=k;
	    }
	}
    }
    return re;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int t=read(int);
	while(t--){
	    string s;
	    cin>>s;
	    vector<INT> vec=getF(s);
	    for(INT i:vec){
		cout<<i<<" ";
	    }
	    cout<<endl;
	}
	return 0;
}
//#endif

tree

lca.cpp

/*
[LCA]最近共同祖先
[參考資料]https://yuihuang.com/lowest-common-ancestor/
*/

const INT mxn=1e5;

INT dep[mxn];//距離根節點的距離(根節點距離為1)
INT siz[mxn];//子樹節點數(包含自己)
INT p[mxn][35];//p[i][j]表i的第2^i祖先
vector<INT> v[mxn];

int dfs(int node=0 , int d){//計算深度及子樹節點數
	dep[node] = d + 1;//深度
	if (v[node].empty()){//如果沒有子節點
		siz[node] = 1;
		return 1;
	}
	int total = 1;//自己也是一個節點
	for (int i:v[node]){
		total += dfs(i, d+1);
	}
	siz[node] = total;
	return siz[node];
}

void build(INT n){//註1
	// 找出每個節點的 2^i 倍祖先
	// 2^20 = 1e6 > 200000
	for (int i = 1; i < 20; i++){
		for (int j = 1; j <= n; j++){
			p[j][i] = p[p[j][i-1]][i-1];
		}
	}
}


int lca(int a, int b){// 求a和b的LCA（利用倍增法）
    if (dep[b] < dep[a]) swap(a, b);
    if (dep[a] != dep[b]){//確保dep是相同的
        int dif = dep[b] - dep[a];
        for (int i = 0; i < 20; i++){//註2
            if (dif & 1) b = p[b][i];
            dif >>= 1;
        }
    }
    if (a == b) return a;//如果位置相同，那lca就是自己
    for (int i = 19; i >= 0; i--){//註3
        if (p[a][i] != p[b][i]){
            a = p[a][i];
            b = p[b][i];
        }
    }
    return p[a][0];
}


int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	return 0;
}

rmq.cpp

//區間最大值
const INT mxn=500000;
INT zipnum=600;
INT n;
INT origlst[mxn+1];
INT ziplst[mxn+1];
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	while(cin>>n){
		zipnum=sqrt(n);
		for(INT i=0;i<n;i++){
			cin>>origlst[i];
			if(i%zipnum==0){
				ziplst[i/zipnum]=origlst[i];
			}else{
				ziplst[i/zipnum]=max(ziplst[i/zipnum],origlst[i]);
			}
		}
		INT q;
		cin>>q;
		while(q--){
			INT l,r;
			cin>>l>>r;
			l--;
			r--;
			if(l>r)swap(l,r);
			INT ans=origlst[l];
			while(l%zipnum && l<=r){
				ans=max(ans,origlst[l]);
				l++;
			}
			while((l+zipnum)<r){
				ans=max(ans,ziplst[l/zipnum]);
				l+=zipnum;
			}
			while(l<=r){
				ans=max(ans,origlst[l]);
				l++;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

dijkstra.cpp

/*
[q]https://neoj.sprout.tw/problem/391/
[AC]
[求最短路]
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	INT t=read(int);
	while(t--){
		INT N,M,S,E,F;//輸入點數量，起點，終點
		cin>>N>>M>>S>>E>>F;
		INT lst[N+1];//紀錄S到i點的最近距離
		vector<pair<INT,INT>> edge[N+1];
		fill(lst,lst+N+1,1e16);
		bool visit[N+1];
		memset(visit,0,sizeof(visit));

		for(INT i=0;i<M;i++){//輸入點資訊
			INT A,B,C,D,C2;
			cin>>A>>B>>C>>D>>C2;
			INT V=min(F,D)*C+max((INT)0,F-D)*C2;
			edge[A].push_back(make_pair(B,V));
		}

		//do Dijkstra
		
		priority_queue<PII,vector<PII>,greater<PII>> pq;//將點以距離(對點1)排序
		pq.push(make_pair(0,S));
		lst[S]=0;

		while(!pq.empty()){
			INT nw=pq.top().second;
			pq.pop();
			if(visit[nw])continue;//如果那個點作過了，就不要再做一次了
			//可以證明每個點作的第一次都是最好的一次，之後就沒有了

			for(PII i:edge[nw]){
				INT nxt=i.first,V=i.second;
				if(lst[nw]+V<lst[nxt]){//發現更短的距離
					lst[nxt]=lst[nw]+V;
					pq.push(make_pair(lst[nxt],nxt));
				}
			}
			visit[nw]=1;
		}
		cout<<lst[E]<<endl;
	}
	return 0;
}
`最短路徑.cpp`
```c++=
/*
[zj]		[Q]https://zerojudge.tw/ShowProblem?problemid=c128
[AC]
[最短路徑]
這一題是在找
找出一條路
再找出這條路經過的數的最小值
盡可能讓這個值最大
該值即為所求
*/
/*num*/
bool debug=false;
bool iofast=true;
string s1,s2;
INT n,r;
INT id=1;
map<string,INT>stint;
const INT maxn=200;
INT mp[maxn+1][maxn+1];
INT season=0;
INT num1,num2;
INT h;
/*fn定義*/
INT find(string str){
	if(stint[str]==0){
		stint[str]=id;
		id++;
		return stint[str];
	}else return stint[str];
}
/*main*/
int main(){
	/*IO加速*/
	if(!debug&&iofast)what_the_fuck;
	while(cin>>n>>r){
		if(n==0&&r==0)break;
		/*re:0*/
		season++;
		stint.clear();
		s1.clear();
		s2.clear();
		id=1;
		num1=0;
		num2=0;
		h=0;
		for(INT i=0;i<=n;i++){
			for(INT j=0;j<=n;j++){
				mp[i][j]=-1;
			}
		}
		/*CIN*/
		for(INT i=0;i<r;i++){
			cin>>s1>>s2>>h;
			num1=find(s1);
			num2=find(s2);
			mp[num1][num2]=h;
			mp[num2][num1]=h;
		}
		cin>>s1>>s2;
		num1=find(s1);
		num2=find(s2);
		/*solve*/
		for(INT i=1;i<=n;i++){//中繼站
			for(INT j=1;j<=n;j++){//起點(或終點)
				for(INT k=j+1;k<=n;k++){//終點(或起點)
					INT tosen=min(mp[j][i],mp[i][k]);//j=>i=>k
					mp[j][k]=max(mp[j][k],tosen);//j=>k或者上面的，看哪個載重量比較大
					mp[k][j]=mp[j][k];
				}
			}
		}
		cout<<"Scenario #"<<season<<endl;
		cout<<mp[num1][num2]<<" tons"<<endl<<endl;
	}
	return 0;
}

最短路徑-greedy.cpp

const INT mxn=1e5;
INT ans=0;
vector<PII> tre[mxn+1],bktre[mxn+1];//tre[起點][i]={終點,花費}
INT n,m;
INT lne[mxn+1];

/*main*/
int main(){
	if(!debug&&iofast){what_the_fuck;}
	srand(time(NULL));
	while(cin>>n>>m){
		for(INT i=0;i<=n;i++){
			tre[i].clear();
			bktre[i].clear();
		}
		for(INT i=0;i<=n;i++){
			lne[i]=1000000000;
		}
		ans=0;
		/*CIN*/
		for(INT i=0;i<m;i++){
			INT a,b,c;
			cin>>a>>b>>c;
			tre[a].push_back({b,c});
			bktre[b].push_back({a,c});
		}
		/*solve*/
		//出去
		priority_queue<PII,vector<PII>,greater<PII>>que;//目前路徑最小的會先被拉出來
		que.push({0,1});//{目前花費,位置}
		lne[1]=0;
		while(que.wassomething()){
			PII nw=que.top();
			que.pop();
			if(lne[nw.SEC]!=nw.FIR)continue;//如果紀錄的和現在的不一樣就跳出(根據bfs的特性，跑過的地方數值絕對比較小)
			ans+=lne[nw.SEC];
			for(PII i:tre[nw.SEC]){
				if(lne[i.FIR]>lne[nw.SEC]+i.SEC){//如果從這邊走過去會比原本的方案好，那就加進去
					lne[i.FIR]=lne[nw.SEC]+i.SEC;
					que.push({lne[i.FIR],i.FIR});
				}
			}
		}
		//回來
		for(INT i=0;i<=n;i++){
			lne[i]=1000000000;
		}
		lne[1]=0;
		que.push({0,1});
		while(que.wassomething()){
			PII nw=que.top();
			que.pop();
			if(lne[nw.SEC]!=nw.FIR)continue;
			ans+=lne[nw.SEC];
			for(PII i:bktre[nw.SEC]){
				if(lne[i.FIR]>lne[nw.SEC]+i.SEC){
					lne[i.FIR]=lne[nw.SEC]+i.SEC;
					que.push({lne[i.FIR],i.FIR});
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

最短路徑dfs.cpp

vector<PII> tre[27];
INT ans=0;
/*fn定義*/
INT dfs(INT p,INT g){
	ans=max(ans,g);
	for(auto i:(tre[p])){
		dfs(i.first,g+i.second);
	}
	return 0;
}
/*main*/
int main(){
	{/*IO加速*/
		cin.tie(0);
		cout.tie(0);
		ios::sync_with_stdio(false);
	}
	/*CIN*/
	char c;
	cin>>c;
	INT st=c-'A';
	INT n;
	cin>>n;
	for(INT i=0;i<n;i++){
		char a,b;
		INT g;
		cin>>a>>b>>g;
		INT ia=a-'A',ib=b-'A';
		tre[ia].push_back({ib,g});
	}
	/*solve*/
	dfs(st,0);
	cout<<ans<<"\n";
	return 0;
}

BIT.cpp

INT n;
vector<INT> vec;
vector<INT> BIT;

INT low_bit(INT x){
	return x&(-x);
}

INT getsum(INT x){//求1~x的值
	INT re=0;
	while(x>0){
		re+=BIT[x];
		x-=low_bit(x);
	}
	return re;
}

void update(INT x){//單點加1
	while(x<=n){
		BIT[x]+=1;
		x+=low_bit(x);
	}
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	INT t=read(int);
	while(t--){
		cin>>n;
		vec.clear();
		BIT.clear();
		vec.resize(n+1);
		BIT.resize(n+1);
		for(INT i=1;i<=n;i++){
			cin>>vec[i];
		}
		INT ans=0;
		for(INT i=n;i>=1;i--){
			ans+=getsum(vec[i]);
			update(vec[i]);
		}
		cout<<ans<<endl;

		DBG{
			cerr<<"DBG ";
			for(INT i=1;i<=n;i++){
				cerr<<BIT[i]<<" ";
			}
			cerr<<endl;
		}
	}
	return 0;
}

dsu.cpp

struct dsu{
	vector<INT> vec;//vec[i]紀錄i連到哪裡
	vector<set<INT>> se;//se[i]記錄所有連到i的點編號
	void init(INT n){//初始化
		se.clear();
		se.resize(n+1);
		vec.clear();
		vec.resize(n+1);
		for(INT i=0;i<=n;i++){
			vec[i]=i;
			se[i].clear();
		}
	}
	INT find(INT n){//查詢編號
		if(vec[n]==n){
			return n;
		}else{
			INT re=find(vec[n]);//找出最終老大
			se[vec[n]].erase(n);//將n連到re，所以要把vec[n]的被動連線解除掉
			vec[n]=re;//將n連到re
			se[re].insert(n);//re被n連
			return re;
		}
	}
	void merge(INT a,INT b){//合併兩者
		INT aboss=find(a);
		INT bboss=find(b);
		vec[aboss]=bboss;//將a樹連到b樹
		se[bboss].insert(aboss);//b樹被a連
	}
	void erase(INT n){//將n孤立
		vec[n]=n;//將自己連到自己
		INT othboss=*(se[n].begin());//其他的老大就用第一個連到n的人來當
		for(INT i:se[n]){
			vec[i]=othboss;
			se[othboss].insert(i);
		}
		se[n].clear();
	}
};

seg_tree.cpp

/*
[q]
[]
*/
//#ifndef eval
#include<bits/stdc++.h>
using namespace std;
#define INT long long int
#define endl "\n"
#define read(n) reader<n>()
#define DBG if(debug)
bool debug=0;
template<typename tpe>tpe reader(){
	tpe re;cin>>re;return re;
}

vector<INT> vec;
vector<INT> seg_tree;
INT n;
INT build(INT l,INT r,INT p=1){//將vec建成seg_tree
	if(l==r){
		seg_tree[p]=vec[l];
	}else{
		INT mnt=(l+r)/2;
		INT lp=build(l,mnt,p<<1);
		INT rp=build(mnt+1,r,p<<1|1);
		seg_tree[p]=lp+rp;
	}
	return seg_tree[p];
}

void call_build(INT n){
	build(0,n);
}

INT edit(INT e,INT v,INT l,INT r,INT p=1){//單點編輯
	if(l==r){
		if(l==e){
			vec[e]=v;
			seg_tree[p]=v;
		}
	}else{
		INT mnt=(l+r)/2;
		INT lp=edit(e,v,l,mnt,p<<1);
		INT rp=edit(e,v,mnt+1,r,p<<1|1);
		seg_tree[p]=lp+rp;
	}
	return seg_tree[p];
}

void call_edit(INT e,INT v,INT n){
	edit(e,v,0,n);
}

bool invs(INT la,INT ra,INT lb,INT rb){//檢測兩區間是否有重疊
	INT l=max(la,lb);
	INT r=min(ra,rb);
	return l<=r;
}

INT search(INT sl,INT sr,INT l,INT r,INT p=1){//求區間和
	if(sl<l)sl=l;
	if(r<sr)sr=r;
	if(sl==l && sr==r && l<=r){
		return seg_tree[p];
	}else{
		INT mnt=(l+r)/2;
		bool lbl=invs(l,mnt,sl,sr);
		bool rbl=invs(mnt+1,r,sl,sr);
		if(lbl && rbl){
			INT l=search(sl,sr,l,mnt,p<<1);
			INT r=search(sl,sr,mnt+1,r,p<<1|1);
			return l+r;
		}else if(lbl){
			INT l=search(sl,sr,l,mnt,p<<1);
			return l;
		}else if(rbl){
			INT r=search(sl,sr,mnt+1,r,p<<1|1);
			return r;
		}else{
			return 0;
		}
	}	
}

INT call_search(INT sl,INT sr,INT n){
	return search(sl,sr,0,n);
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	INT t=1;
	while(t--){
		n=read(INT);
		vec.resize(n);
		seg_tree.resize(n*4);
		for(INT i=0;i<n;i++){
		vec[i]=read(INT);	
		}
		n--;
		call_build(n);

		INT m=read(INT);
		while(m--){
			INT doid=read(INT);
			if(doid==1){
				INT e,v;
				cin>>e>>v;
				call_edit(e,v,n);
			}else{
				INT l,r;
				cin>>l>>r;
				cout<<call_search(l,r,n)<<endl;
			}
		}
	}
	return 0;
}
//#endif