## 前言
之前的有在其他被廢所以現在我險一個新的，參考IO wiki
# 線段樹

//from:https://oi-wiki.org/ds/seg/
#include <bits/stdc++.h>
using namespace std;

template <typename T>
class SegTree{
  vector<T>tree,lazy;
  vector<T>*arr;
  int n,root,n4,end;

  void maintain(int cl,int cr,int p){
    int cm=cl+(cr-cl)/2;
    if (cl!=cr&&lazy[p]){
      lazy[p*2]+=lazy[p];
      lazy[p*2+1]+=lazy[p];
      tree[p*2]+=lazy[p]*(cm-cl+1);
      tree[p*2+1]+=lazy[p]*(cr-cm);
      lazy[p]=0;
    }
  }

  T range_sum(int l,int r,int cl,int cr,int p){//區間總和
    if(l<=cl&&cr<=r)return tree[p];
    int m=cl+(cr-cl)/2;
    T sum=0;
    maintain(cl,cr,p);
    if(l<=m)sum+=range_sum(l,r,cl,m,p*2);
    if(r>m)sum+=range_sum(l,r,m+1,cr,p*2+1);
    return sum;
  }

  void range_set(int l,int r,T val,int cl,int cr,int p){//區間加值
    if (l<=cl&&cr<=r){
      lazy[p]=val;
      tree[p]=(cr-cl+1)*val;
      return;
    }
    int m=cl+(cr-cl)/2;
    maintain(cl, cr, p);
    if(l<=m)range_set(l,r,val,cl,m,p*2);
    if(r> m)range_set(l,r,val,m+1,cr,p*2+1);
    tree[p]=tree[p*2]+tree[p*2+1];
  }

  void range_add(int l,int r,T val,int cl,int cr,int p) {//區間設值
    if(l<=cl&&cr<=r){
      lazy[p]+=val;
      tree[p]+=(cr-cl+1)*val;
      return;
    }
    int m=cl+(cr-cl)/2;
    maintain(cl,cr,p);
    if(l<=m)range_add(l,r,val,cl,m,p*2);
    if(r> m)range_add(l,r,val,m+1,cr,p*2+1);
    tree[p]=tree[p*2]+tree[p*2+1];
  }

  void build(int s, int t, int p) {//建樹
    if(s==t){
      tree[p]=(*arr)[s];
      return;
    }
    int m=s+(t-s)/2;
    build(s,m,p*2);
    build(m+1,t,p*2+1);
    tree[p]=tree[p*2]+tree[p*2+1];
  }

 public:
  explicit SegTree<T>(vector<T> v) {
    n=v.size();
    n4=n*4;
    tree=vector<T>(n4,0);
    lazy=vector<T>(n4,0);
    arr=&v;
    end=n-1;
    root=1;
    build(0,end,1);
    arr=nullptr;
  }
  void show(int p, int depth=0){
    if(p>n4||tree[p]==0)return;
    show(p*2,depth+1);
    for(int i=0;i<depth;i++)putchar('\t');
    printf("%d:%d\n", tree[p],lazy[p]);
    show(p*2+1,depth+1);
  }
  T range_sum(int l, int r) {return range_sum(l, r,0,end,root); }
  void range_add(int l, int r,int val){range_add(l,r,val,0,end,root);}
  void range_set(int l, int r,int val){range_set(l,r,val,0,end,root);}
};
int main(){
  int n,m,t,x,y,k;
  cin>>n>>m;
  vector<long long>a(n);
  for(auto&i:a)cin>>i;
  SegTree<long long>s(a);
  //s.show(1);//debuge用
  while(m--){
    cin>>t;
    if(t==1){//區間加值
      cin>>x>>y>>k;
      s.range_add(x-1,y-1,k);
    }
    else {//區間改值
      cin>>x>>y;
      cout<<s.range_sum(x-1,y-1)<<endl;
    }
  }
}

# 最短路

#include<bits/stdc++.h>
#define inf 0xfffff
using namespace std;
int main(){
  int t,n,r;cin>>t;
  while(t--){
    cin>>n>>r;
    int Map[n][r],ans[n][r],d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    bool vis[n][r]={};
    for(auto&i:Map)for(auto&j:i)cin>>j;
    for(auto&i:ans)for(auto&j:i)j=inf;ans[0][0]=Map[0][0];
    priority_queue<tuple<int,int,int>>pq;
    pq.push(make_tuple(-Map[0][0],0,0));
    //dijkstra
    while(pq.size()){
      int val=-get<0>(pq.top()),x=get<1>(pq.top()),y=get<2>(pq.top());
      pq.pop();
      vis[x][y]=1;
      for(int i=0;i<4;i++){
        int nx =x+d[i][0],ny=y+d[i][1];
        if(nx>=0&&nx<n&&ny>=0&&ny<r&&!vis[nx][ny]){
          int tmp=val+Map[nx][ny];
          if(ans[nx][ny]>tmp){
            ans[nx][ny]=tmp;
            pq.push(make_tuple(-tmp,nx,ny));
          }
        }
      }
    }
    cout<<ans[n-1][r-1]<<"\n";
   }   
}

# 併查集
最小生成樹演算法 中的 Kruskal 和 最近公共祖先 中的 Tarjan 演算法是基於併查集的演算法。

#include <bits/stdc++.h>

using namespace std;

struct dsu {
  vector<size_t>pa,size,sum;//unsigned int

  explicit dsu(size_t size_)
      :pa(size_*2),size(size_*2,1),sum(size_*2){
    //size 與 sum 的前半段其實沒有使用，只是為了讓下標計算更簡單
    iota(pa.begin(),pa.begin()+size_, size_);//生成連續數
    iota(pa.begin()+size_,pa.end(),size_);
    iota(sum.begin()+size_,sum.end(),0);
  }

  void unite(size_t x, size_t y){//合併
    x=find(x),y=find(y);
    if(x==y)return;
    if(size[x]<size[y])swap(x,y);
    pa[y]=x;
    size[x]+=size[y];
    sum[x]+=sum[y];
  }

  void move(size_t x,size_t y){
  //將x從他所在的群體當中移除並且加入y所在的群體
    auto fx=find(x),fy=find(y);
    if(fx==fy)return;
    pa[x]=fy;
    --size[fx],++size[fy];
    sum[fx]-=x,sum[fy]+=x;
  }

  size_t find(size_t x){return pa[x]==x?x:pa[x]=find(pa[x]); }
};

int main() {
  size_t n,m,op,x,y;
  while(cin>>n>>m){
    dsu dsu(n+1);//元素范围是1..n
    while(m--){
      cin>>op;
      switch(op){
        case 1:
          cin>>x>>y;
          dsu.unite(x,y);
          break;
        case 2:
          cin>>x>>y;
          dsu.move(x,y);
          break;
        case 3:
          cin>>x;
          x=dsu.find(x);
          cout<<dsu.size[x]<<' '<<dsu.sum[x]<<'\n';
          break;
        default:assert(false); 
      }
    }
  }
}
/*
5 4 1~5個數 4個指令
1 1 2 指令"1" 1 2 合併 
2 3 4 指令"2" 將3從他所在的群體當中移除並且加入4所在的群體
3 4   指令"3" 印出4所在的群體的size大小跟種數
*/

# 拓樸

#include"bits/stdc++.h"
using namespace std;
int main(){
  int m,p,a,b,temp;
  while(cin>>m>>p&&m+p){
    vector<int>id(m,0);//indegree
    vector<int>edge[m];
    while(p--){
      cin>>a>>b;
      edge[a-1].push_back(b-1);
      id[b-1]++;
    }
    queue<int>q;
    for(int i=0;i<m;i++)if(!id[i])q.push(i);
    bool flag=0;
    while(q.size()){
      if(flag++)cout<<' ';
      temp=q.front();
      q.pop();
      cout<<temp+1;
      for(auto&i:edge[temp]){
        id[i]--;
        if(!id[i])q.push(i);
      }
    }
    cout<<endl;
  }
}

## 字典樹

struct TrieNode {
    int nxt[26]; //遇到a~z時的節點編號(idx)
    int cnt; //以此結尾的字串個數
} node[1000005];
 
int idx = 2; //root = 1

void insert(string s){
  int cur = 1; //從root開始
  for(auto i:s) {
    if(node[cur].nxt[i-'a'] == 0){
      node[cur].nxt[i-'a']=idx;//開一個新的node
      cur = idx;
      idx++;
    }
    else {
      cur = node[cur].nxt[i-'a'];
    }
  }
  node[cur].cnt++;
}

int query(string s){
  int cur = 1;
  for(auto i:s) 
    if(node[cur].nxt[i-’a’] == 0)return 0;
    else cur = node[cur].nxt[i-’a’];
  return node[cur].cnt;
}

# LCS&LIS&LPS
## LCS 和 LIS 題目轉換
- LIS 轉成 LCS
1. A 為原序列，B=sort(A)
2. 對 A,B 做 LCS
- LCS 轉成 LIS
1. A,B 為原本的兩序列
2. 最 A 序列作編號轉換，將轉換規則套用在 B
3. 對 B 做 LIS
4. 重複的數字在編號轉換時後要變成不同的數字，越早出現的數字要越小
5. 如果有數字在 B 裡面而不在 A 裡面，直接忽略這個數字不做轉換即可

// 為了實作方便，從陣列的第1格開始存入序列。
int length[N1+1][N2+1];// DP表格

int LCS(){
  // 初始值：當s1或s2是空集合，則LCS是空集合。
  for (int i=0; i<=N1; i++) length[i][0] = 0;
  for (int j=0; j<=N2; j++) length[0][j] = 0;
  // 填表格：依照遞迴公式
  for (int i=1; i<=N1; i++)
  for (int j=1; j<=N2; j++)
    if (s1[i] == s2[j])
	  length[i][j] = length[i-1][j-1] + 1;
	else
	  length[i][j] = max(length[i-1][j],length[i][j-1]);
  return length[N1][N2];
}

//LIS長度(順序是錯的)運用dp+greedy+binary search
//https://www.youtube.com/watch?v=l2rCz7skAlk 講解
//O(nlogn)
#include"bits/stdc++.h"
using namespace std;
int LIS(auto&a){
  vector<int>dp;
  for(auto&i:a)
    if(dp.empty()||dp.back()<i)dp.push_back(i);
    else{auto it=lower_bound(dp.begin(),dp.end(),i);*it=i;}
  return dp.size();
}
int main(){
  int n;vector<int>a;
  while(cin>>n)a.push_back(n);
  cout<<LIS(a);
}

//LPS 最長回文子序列
//https://www.youtube.com/watch?v=g3R-pjUNa3k
#include"bits/stdc++.h"
using namespace std;
string LPS(string s){
  int n=s.size();
  auto getlen=[&](int l,int r){
    while(l>=0&&r<n&&s[l]==s[r]){
      r++;
      l--;
    }
    return r-l-1;
  };
  int len=0;
  int start=0;
  for(int i=0;i<n;i++){
    int temp=max(getlen(i,i),getlen(i,i+1));
    if(temp>len){
      len=temp;
      start=i-(len-1)/2;
    }
  }
  return s.substr(start,len);
}
int main(){
  string s;
  cin>>s;
  cout<<LPS(s);
}

# 擴增歐基里德

#include<iostream>
using namespace std;
int gcd(int a,int b,int&x,int&y){//g=ax+by
  if(b==0){
    x=1;y=0;return a;
  }
  int ox,oy;
  int g=gcd(b,a%b,ox,oy);
  x = oy;
  y = ox-a/b*oy; 

  return g;
}
int main(){
  int a,b;cin>>a;
  while(cin>>a>>b){
    int x,y,g=gcd(a,b,x,y);
    printf("%d %d %d\n",x,y,g);
  }
}

# 超大數相乘

import java.math.BigInteger;
import java.util.Scanner;
class Main{
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    while(sc.hasNext()){
      BigInteger n1=sc.nextBigInteger();
      BigInteger n2=sc.nextBigInteger();
      System.out.println(n1.multiply(n2));
    }
  }
};