# 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`
> > ```c++=
> > /*
> > [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`
> > ```c++=
> > /*
> > [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`
> > > ```c++=
> > > /*
> > > [擴展歐幾里得]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`
> > > ```c++=
> > > /*
> > > [求反模逆元 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`
> > ```c++=
> > /*
> > [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`
> > ```c++=
> > /*
> > 字串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`
> > ```c++=
> > 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`
> > ```c++=
> >
> > 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`
> > ```c++=
> > /*
> > [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`
> > ```c++=
> > //區間最大值
> > 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`
> > ```c++=
> > /*
> > [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`
> > ```c++=
> > 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`
> > ```c++=
> > 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`
> > ```c++=
> > 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`
> > ```c++=
> > 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`
> > ```c++=
> > /*
> > [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
> > ```