# CSES-「Introductory Problems」解題紀錄
## Weird Algorithm
### 題序
>Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows:$$ 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$$
Your task is to simulate the execution of the algorithm for a given value of n.
<https://cses.fi/problemset/task/1068/>
### 考點
單純遞迴，記得開long long
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
ll n;
//functions
void f(ll n){
    cout<<n<<' ';
    if(n==1)return;
    if((n&1)==0){
        f(n/2);
    }else{
        f(3*n+1);
    }
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    f(n);
}

## Missing Number
### 題序
>You are given all numbers between 1,2...n except one. Your task is to find the missing number.
<https://cses.fi/problemset/task/1083/>
### 考點
無
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
ll n;
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    long long sum=n*(n+1)/2;
    n--;
    while(n--){
        int tmp;cin>>tmp;
        sum-=tmp;
    }
    cout<<sum;
}

## Repetitions
### 題序
>You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is to find the longest repetition in the sequence. This is a maximum-length substring containing only one type of character.
><https://cses.fi/problemset/task/1069/>
### 考點
無
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas

//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    string s;cin>>s;
    int mx=1,now=1;char x='p';
    for(char t:s){
        if(x!=t){
            now=1;
            x=t;
        }else{
            now+=1;
            mx=max(mx,now);
        }
    }
    cout<<mx;
}

## Increasing Array
### 題序
>You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.
On each move, you may increase the value of any element by one. What is the minimum number of moves required?
<https://cses.fi/problemset/task/1094/>
### 考點
無
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n;
int w[MAX]={0};
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    ll sum=0;
    for(int i=1;i<=n;i++){
        if(w[i]<w[i-1]){
            sum+=w[i-1]-w[i];
            w[i]=w[i-1];
        }
    }
    cout<<sum<<'\n';
}

## Bit Strings
### 題序
> Your task is to calculate the number of bit strings of length n.
For example, if n=3, the correct answer is 8, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.
<https://cses.fi/problemset/task/1617/>
### 考點
就是2的冪次，也不用快速冪，很水。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n;
ll s=1;
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    while(n--){
        s=s*2%1000000007;
    }
    cout<<s;
}

## Number Spiral
### 題序
>A number spiral is an infinite grid whose upper-left square has number 1. Here are the first five layers of the spiral:
Your task is to find out the number in row y and column x.
<https://cses.fi/problemset/task/1071/>
### 考點
數學，只要算好y,x的關係，就可以O(1)解。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int t;
ll y,x;
ll ans=0;
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    while(t--){
        cin>>y>>x;
        ans=0;
        if(y==x){
            ans=x*x-x+1;
        }else if(y>x){
            if((y&1)==0){
                ans=y*y-x+1;
            }else{
                ans=(y-1)*(y-1)+1+x-1;
            }
        }else{
            if((x&1)==1){
                ans=x*x-y+1;
            }else{
                ans=(x-1)*(x-1)+1+y-1;
            }
        }
        cout<<ans<<'\n';
    }
}

## Permutations
### 題序
>A permutation of integers 1,2,\ldots,n is called beautiful if there are no adjacent elements whose difference is 1.
Given n, construct a beautiful permutation if such a permutation exists.
<https://cses.fi/problemset/task/1070/>
### 考點
只需要特判n=2,3,4的情況，其他都先輸出奇數在輸出偶數就好。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n;
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    if(n==2||n==3)cout<<"NO SOLUTION";
    else if(n==4){
        cout<<"2 4 1 3";
    }
    else{
        for(int i=1;i<=n;i+=2){
            cout<<i<<' ';
        }
        for(int i=2;i<=n;i+=2){
            cout<<i<<' ';
        }
    }
}

## Palindrome Reorder
### 題序
>Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (i.e., it reads the same forwards and backwards).
><https://cses.fi/problemset/task/1755/>
### 考點
算有多少字元個數是奇數，超過一個就無解，如果有解就先輸出一半，在輸出奇數個的那項，最後在輸出一半。
### AC code

#include<iostream>
using namespace std;
int main(){
    string s;cin>>s;
    int cnt[26]={0};
    for(int i=0;i<s.size();i++){
        cnt[s[i]-'A']++;
    }
    int tet=0;
    int mid=0;
    for(int i=0;i<26;i++){
        if(cnt[i]&1){
            tet++;
            mid=i;
        }
    }
    if(tet>1){
        cout<<"NO SOLUTION\n";
        return 0;
    }else{
        for(int i=0;i<26;i++){
            if(i!=mid){
                for(int j=0;j<cnt[i]/2;j++)cout<<(char)('A'+i);
            }
        }
        for(int i=0;i<cnt[mid];i++)cout<<(char)('A'+mid);
        for(int i=25;i>=0;i--){
            if(i!=mid){
                for(int j=0;j<cnt[i]/2;j++)cout<<(char)('A'+i);
            }
        }
    }
}

# CSES-「Sorting ans Searching」解題紀錄
## Subarray Sums I
### 題序
>Given an array of n positive integers, your task is to count the number of subarrays having sum x.
<https://cses.fi/problemset/task/1660>
### 考點
這題如果枚舉所有子陣列複雜度到O(n^2)，要用到雙指針的技巧，設lb,rb，rb會一直往右直到sum>=x，接著lb會往右直到sum<=x，這樣最多只會跑O(n)的時間。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
//datas
int n,x;
ll w[MAX]={0};
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++)cin>>w[i];
    int lb=1,rb=1;
    ll sum=w[1];
    ll cnt=0;
    for(;lb<=n;lb++){
        while(sum<x){
            sum+=w[++rb];
        }
        if(sum==x)cnt++;
        sum-=w[lb];
    }
    cout<<cnt<<'\n';
}

## Nearest Smaller Values
### 題序
>Given an array of n integers, your task is to find for each array position the nearest position to its left having a smaller value.
<https://cses.fi/problemset/task/1645/>
### 考點
如果每個數字都往回跑找比他小的值複雜度O(n^2)，可以用stack存資料，遇到如果v.back()比他小就輸出它的idx，如果比他大就pop掉，因為之後的數字也不可能用到它了。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n;
int w[MAX]={0};
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    vector<pii>v;
    v.push_back({0,0});
    for(int i=1;i<=n;i++){
        while(v.back().first>=w[i]){
            v.pop_back();
        }
        cout<<v.back().second<<' ';
        v.push_back({w[i],i});
    }
}

## Distinct Numbers
### 題序
You are given a list of n integers, and your task is to calculate the number of distinct values in the list.
<https://cses.fi/problemset/task/1621/>
### 考點
排序後數有多少組前後數字不一樣
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n;
int arr[MAX]={0};
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>arr[i];
    sort(arr,arr+n+1);
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(arr[i]!=arr[i-1])cnt++;
    }
    cout<<cnt;
}

## Sum of Two Values
### 題序
>You are given an array of n integers, and your task is to find two values (at distinct positions) whose sum is x.
><https://cses.fi/problemset/task/1640/>
### 考點
用二分搜找有沒有剛好加起來等於x的東西
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n;
int x;
int a[MAX];
vector<pii>v;
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    cin>>x;
    for(int i=0;i<n;i++){
        cin>>a[i];
        v.push_back({a[i],i});
    }
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++){
        int b=x-a[i];
        int lb=0,rb=n;
        while(lb+1<rb){
            int m=(lb+rb)>>1;
            if(v[m].first>b){
                rb=m;
            }else{
                lb=m;
            }
        }
        if(v[lb].first==b){
            if(v[lb].second!=i){
                cout<<i+1<<' '<<v[lb].second+1;
                return 0;
            }
        }
    }
    cout<<"IMPOSSIBLE";
}

# CSES-「Advanced Technique」解題紀錄
## Meet in the Middle
### 題序
>You are given an array of n numbers. In how many ways can you choose a subset of the numbers with sum x?
<https://cses.fi/problemset/task/1628/>
### 考點
這題n最大到40，如果直接枚舉所有子集，複雜度O(2^n) 會TLE，要用到「折半枚舉」的技巧。分別枚舉L,R各一半的子集，複雜度O(2^(n/2))，排序兩個子集後，對於L的每個元素用二分搜找R有幾個元素與之相加會等於x，複雜度O(nlogn) 。總複雜度等於O(2^n/2)。
### 實作細節
#### 如何枚舉所有子集合？
可以用遞迴來跑，設定lb,rb的範圍，lb每遞迴一次+1,分散出有加arr[lb]與否兩種狀態，就能跑出所有可能的結果。

void fillL(int lb,int rb,long long sum){
    if(lb==rb){
        L.push_back(sum);
        return;
    }
    fillL(lb+1,rb,sum);
    fillL(lb+1,rb,sum+arr[lb]);
}

#### 如何求出R中有多少元素跟L[i]相加等於x
可以用內建的upper_bound,lowerbound相減就是數量，但要先判斷lower_bound==L[i]是否成立。

for(auto t:L){
        long long div=x-t;
        if(x-t<0)break;
        if(*lower_bound(R.begin(),R.end(),div)==div){
            ans+=upper_bound(R.begin(),R.end(),div)-lower_bound(R.begin(),R.end(),div);
        }
    }

### AC code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,x;
int arr[45];
vector<long long> L,R;
void fillL(int lb,int rb,long long sum){
    if(lb==rb){
        L.push_back(sum);
        return;
    }
    fillL(lb+1,rb,sum);
    fillL(lb+1,rb,sum+arr[lb]);
}
void fillR(int lb,int rb,long long sum){
    if(lb==rb){
        R.push_back(sum);
        return;
    }
    fillR(lb+1,rb,sum);
    fillR(lb+1,rb,sum+arr[lb]);
}
int main(){
    cin>>n>>x;
    for(int i=0;i<n;i++)cin>>arr[i];
    fillL(0,n/2,0);
    fillR(n/2,n,0);
    sort(L.begin(),L.end());
    sort(R.begin(),R.end());
    long long ans=0;
    for(auto t:L){
        long long div=x-t;
        if(x-t<0)break;
        if(*lower_bound(R.begin(),R.end(),div)==div){
            ans+=upper_bound(R.begin(),R.end(),div)-lower_bound(R.begin(),R.end(),div);
        }
    }
    cout<<ans;
}

## Hamming Distance
### 題序
>The Hamming distance between two strings a and b of equal length is the number of positions where the strings differ.
You are given n bit strings, each of length k and your task is to calculate the minimum Hamming distance between two strings.
<https://cses.fi/problemset/task/2136/>
### 考點
如果直接用字串一個一個比對，總複雜度會是O(kn^2) ，但是O(n^2)會壓不掉，只能用位元運算把O(k)降成O(1)。
### 實作細節
如何快速求hamming距離，上函式

int hamming(int a,int b){
    return __builtin_popcount(a^b);
}

### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#define MAX 200005
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n,k,arr[MAX]={0};
//functions
int hamming(int a,int b){
    return __builtin_popcount(a^b);
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        string tmp;cin>>tmp;
        int x=1;
        for(int j=0;j<tmp.size();j++){
            arr[i]+=x*(tmp[j]-'0');
            x*=2;
        }
    }
    int mn=INT_MAX;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            mn=min(mn,hamming(arr[i],arr[j]));
        }
    }
    cout<<mn;
}

## Beautiful Subgrids
### 題序
>You are given an n \times n grid whose each square is either black or white. A subgrid is called beautiful if its height and width is at least two and all of its corners are black. How many beautiful subgrids are there within the given grid?
<https://cses.fi/problemset/task/2137/>
### 考點
要把它當成很多條一維01陣列，用位元運算來解，兩條陣列之間同時有交集的數量可以推出有多少子矩陣。但這題最扯的地方是O(n^3/64)優化還是不行，要用到pragma指令來讓位元運算加速才會過，長知識了。
### 實作細節
__builtin_popcount只能用在unsigned int，如果要算long long 型態的東西要改成__builtin_popcountll，太細了。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define MAX 3005
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n;
ll grid[MAX][MAX]={0};
//functions
 
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        string tmp;cin>>tmp;
        for(int j=0;j<n;j++){
            grid[i][j/64]<<=1;
            grid[i][j/64]+=(tmp[j]-'0');
        }
    }
    ll sum=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            ll count=0;
            for(int k=0;k<=n/64;k++){
                //cout<<grid[i][k]<<' '<<grid[j][k]<<'\n';
                count+=__builtin_popcountll(grid[i][k]&grid[j][k]);
            }
            sum+=count*(count-1);
        }
    }
    cout<<(sum>>1)<<'\n';
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)cin>>grid[i];
    ll sum=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            sum+=f((grid[i]&grid[j]).count());
        }
    }
    cout<<(sum>>1);
}

# CSES-「Range Queries」解題紀錄
## Static Range Sum Queries
### 題序
>Given an array of n integers, your task is to process q queries of the form: what is the sum of values in range [a,b]?
<https://cses.fi/problemset/task/1646>
### 考點
單純考前綴和，沒什麼特別的
### AC code

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#define MAX 200005
#define F first
#define S second
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int main(){
        ios::sync_with_stdio(0);cin.tie(0);
        int n,times;cin>>n>>times;
        ll arr[MAX]={0},dp[MAX]={0};
        for(int i=1;i<=n;i++)cin>>arr[i];
        for(int i=1;i<=n;i++)dp[i]=dp[i-1]+arr[i];
        while(times--){
                int a,b;cin>>a>>b;
                cout<<dp[b]-dp[a-1]<<'\n';
        }
}

## Static Range Minimum Queries
### 題序
>Given an array of n integers, your task is to process q queries of the form: what is the minimum value in range [a,b]?
<https://cses.fi/problemset/task/1647/>
### 考點
因為n,q最大都有2*10^5 ，要用到sparse table技巧預處理，讓每次詢問的複雜度降到O(1)。
演算法的精華我們只需要算所有二的倍數的範圍的最小值，之後每一筆詢問都可以用兩個已知的答案來推，有夠神奇。
### 實作細節
#### 如何建[稀疏表](<https://hackmd.io/Sgwkv9VaSPew_Lj-008Xdw?both#%E7%A8%80%E7%96%8F%E8%A1%A8%E3%80%8CSparse-table%E3%80%8D>)
用迴圈來做會比較直覺

while(x<=n){
        int y=find_y(x);
        for(int i=1;i<=n-x+1;i++){
            if(x==1)spt[i][y]=arr[i];
            else{
                spt[i][y]=min(spt[i][y-1],spt[i+x/2][y-1]);
            }
        }
        x*=2;
    }

#### 開二維陣列存資料會爆儲存空間
仔細想想我們不需要用到那麼大的空間欸，只需要O(nlogn)就可以了，這樣就放得下了，實作上spt[i][j]中i代表起始點，j代表覆蓋了2^j的範圍。
#### 最接近的b-a的k怎麼找
用線性找的話會大幅增加複雜度，可以先預處理開vector存所有可能值，在用二分搜找，複雜度降很多。
### AC code

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<climits>
#include<map>
#define MAX 500005
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
//
int arr[MAX];
int spt[MAX][20];
vector<int>pw;
//map<int, map<int,int> >spt;
//
bool is_2pow(int x){
    while(x%2==0){
        x/=2;
    }
    if(x==1)return true;
    else return false;
}
int find_y(int x){
    int cnt=0;
    while(x%2==0){
        x/=2;
        cnt++;
    }
    return cnt;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    while(!is_2pow(n)){
        n+=1;
        arr[n]=INT_MAX;
    }
    int x=1;
    while(x<=n){
        int y=find_y(x);
        for(int i=1;i<=n-x+1;i++){
            if(x==1)spt[i][y]=arr[i];
            else{
                spt[i][y]=min(spt[i][y-1],spt[i+x/2][y-1]);
            }
        }
        x*=2;
    }
    int tmp=1;
    int times=20;
    while(times--){
        pw.push_back(tmp);
        tmp*=2;
    }
    while(q--){
        int a,b;cin>>a>>b;
        b++;
        int k=b-a;
        k=*prev(upper_bound(pw.begin(), pw.end(), k));
        int y=find_y(k);
        cout<<min(spt[a][y],spt[b-k][y])<<'\n';
    }
}

## Dynamic Range Sum Queries
### 題序
>Given an array of n integers, your task is to process q queries of the following types:
update the value at position k to u
what is the sum of values in range [a,b]?
<https://cses.fi/problemset/task/1648/>
### 考點
因為陣列的值會變化，所以普通的前綴和用不了。需要用到Binary Indexed Tree這個特殊的資料結構，他可以用O(logn)的複雜度修改單點的值，然後用O(logn)的時間算[1,n]的和。
想法是建一個tree[MAX]陣列，tree[i]是第i-p(i)+1項到第i項的和，p(i)是能夠整除i的最大power of two。建表的時間複雜度是O(nlogn)。
算[1,n]的和就可以用while迴圈，每次加上tree[i]的值，接著到i-p(i)項，也就是沒有被覆蓋到的地方，這樣跑完整個陣列只需要O(logn)的時間
修改第i項的值要修改有覆蓋到第i項的tree陣列，這個資料結構最神奇的地方就是i+=p(i)就能計算出下一個有覆蓋到的地方在哪裡。
:::info
是說這應該可以用數學來證明，但我不會...
:::
### 實作細節
#### 如何計算p(i)
能夠整除i的最大power of two等於i&-i，不知道為啥，好酷。
#### sum()函式

ll sum(int k) {
    ll s = 0;
    while (k >= 1){
        s += tree[k];
        k -= k&-k;
    }
    return s;
}

#### add()函式

void add(int k, ll x) {
    while (k <= n){
        tree[k] += x;
        k += k&-k;
    }
}

### AC code(1)BIT版本

#include<iostream>
#include<climits>
#include<algorithm>
#define MAX 200005
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
ll tree[MAX]={0};
int n,q;
ll arr[MAX];
//functions
ll sum(int k) {
    ll s = 0;
    while (k >= 1){
        s += tree[k];
        k -= k&-k;
    }
    return s;
}

void add(int k, ll x) {
    while (k <= n){
        tree[k] += x;
        k += k&-k;
    }
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>arr[i];
    for(int i=1;i<=n;i++){
        int p=i&-i;
        ll sum=0;
        for(int j=i-p+1;j<=i;j++){
            sum+=arr[j];
        }
        tree[i]=sum;
    }
    /*for(int i=1;i<=n;i++){
        cout<<tree[i]<<' ';
    }*/
    while(q--){
        int a,b,c;cin>>a>>b>>c;
        if(a==1){
            ll tmp=c-arr[b];
            arr[b]=c;
            add(b,tmp);
        }
        else{
            cout<<sum(c)-sum(b-1)<<'\n';
        }
    }
}

### 另解
可以用線段樹這個資料結構，就是一個二元樹，而且可以用[2n]長度的陣列表示，個人覺得比BIT還要直覺，適用範圍似乎也比較廣，實作也比較簡單。
### 實作難點
#### 如何建表
本來想說要不要把陣列長度補到power of two，但其實只要把陣列預設成0就不會有影響了，用遞迴很輕鬆就能完成。

void build(int node){
    if(n<=node)return;
    build(node*2);
    build(node*2+1);
    tree[node]=tree[node*2]+tree[node*2+1];
}

#### sum()怎麼寫
整個資料結構最精彩絕倫的就是他的算法，對左界來說，如果處在子樹的右邊，那就直接加上那一個節點的資料，然後-1，再/2，就會跑到右邊的父節點上，右界以此類推，當左界>右界代表已經算完區間的和，直接return 就好。

ll sum(int a,int b){
    ll s=0;
    a+=n-1;b+=n-1;
    while(a<=b){
        while(a%2==1)s+=tree[a++];
        while(b%2==0)s+=tree[b--];
        a/=2;b/=2;
    }
    return s;
}

#### add()函式怎麼寫
一直除二上去就能走過所有父節點。
### AC code(2)線段樹版本

#include<iostream>
#include<climits>
#include<algorithm>
#define MAX 400005
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n,q;
ll tree[MAX]={0};
//functions
void build(int node){
    if(n<=node)return;
    build(node*2);
    build(node*2+1);
    tree[node]=tree[node*2]+tree[node*2+1];
}
ll sum(int a,int b){
    ll s=0;
    a+=n-1;b+=n-1;
    while(a<=b){
        while(a%2==1)s+=tree[a++];
        while(b%2==0)s+=tree[b--];
        a/=2;b/=2;
    }
    return s;
}
void add(int k,int r){
    k+=n-1;
    tree[k]=r;
    for(k/=2;k>=1;k/=2){
        tree[k]=tree[k*2]+tree[k*2+1];
    }
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(int i=n;i<2*n;i++){
        cin>>tree[i];
    }
    build(1);
    /*for(int i=1;i<n+x;i++){
        cout<<tree[i]<<' ';
    }*/
    while(q--){
        int c,v,m;cin>>c>>v>>m;
        if(c==1){
            add(v,m);
        }else{
            cout<<sum(v,m)<<'\n';
        }
    }

## Dynamic Range Minimum Queries
### 題序
>Given an array of n integers, your task is to process q queries of the following types:
update the value at position k to u
what is the minimum value in range [a,b]?
<https://cses.fi/problemset/task/1649/>
### 考點
一樣是線段樹，跟上一題幾乎一模一樣，只是要改成紀錄最小值。廢話不多說直接上ac code
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#define MAX 400005
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n,q;
int tree[MAX];
//functions
void build(int node){
    if(n<=node)return;
    build(node*2);
    build(node*2+1);
    tree[node]=min(tree[node*2],tree[node*2+1]);
}
void update(int k,int u){
    k+=n-1;
    tree[k]=u;
    for(k/=2;k>=1;k/=2){
        tree[k]=min(tree[k*2],tree[k*2+1]);
    }
}
int mnm(int a,int b){
    a+=n-1;b+=n-1;
    int mn=INT_MAX;
    while(a<=b){
        while(a%2==1)mn=min(mn,tree[a++]);
        while(b%2==0)mn=min(mn,tree[b--]);
        a/=2;b/=2;
    }
    return mn;
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(int i=n;i<n*2;i++)cin>>tree[i];
    build(1);
    while(q--){
        int tmp;cin>>tmp;
        if(tmp==1){
            int k,u;cin>>k>>u;
            update(k,u);
        }else{
            int a,b;cin>>a>>b;
            cout<<mnm(a,b)<<'\n';
        }
    }
}

## Range Update Queries
### 題序
>Given an array of n integers, your task is to process q queries of the following types:
increase each value in range [a,b] by u
what is the value at position k?
<https://cses.fi/problemset/task/1651/>
### 考點
這題要一次增加某一段區間，然後問某一個位置的值是多少。如果慢慢加複雜度O(nq)會TLE，要用到前綴和的特殊用法，可以預處理陣列將tree[i]-=tree[i-1]，之後要問tree[i]就是從1加到i的和。如果要對[a,b]加x，就在tree[a]+=x，tree[b+1]-=x。有了這個觀念，就可以用線段樹來實作。
### 實作細節
如果b==n，就不用再tree[b+1]-=x了，不然會壞掉。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#define MAX 400005
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n,q;
ll tree[MAX]={0};
//functions
void build(int node){
    if(n<=node)return;
    build(node*2);
    build(node*2+1);
    tree[node]=tree[node*2]+tree[node*2+1];
}
ll sum(int a,int b){
    a+=n-1;b+=n-1;
    ll s=0;
    while(a<=b){
        while(a%2==1)s+=tree[a++];
        while(b%2==0)s+=tree[b--];
        a/=2;b/=2;
    }
    return s;
}
void add(int k,ll u){
    k+=n-1;
    tree[k]+=u;
    for(k/=2;k>=1;k/=2){
        tree[k]=tree[k*2]+tree[k*2+1];
    }
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(int i=n;i<n*2;i++)cin>>tree[i];
    for(int i=n*2-1;i>=n;i--)tree[i]-=tree[i-1];
    build(1);
    while(q--){
        int tmp;cin>>tmp;
        if(tmp==1){
            int a,b;cin>>a>>b;
            ll u;cin>>u;
            add(a,u);
            if(b!=n)add(b+1,-u);
        }else{
            int k;cin>>k;
            cout<<sum(1,k)<<'\n';
        }
    }
}

## Range Xor Queries
### 題序
>Given an array of n integers, your task is to process q queries of the form: what is the xor sum of values in range [a,b]?
><https://cses.fi/problemset/task/1650/>
### 考點
xor跟加法具有某種相似的性質，他們都可以用線段樹來寫，架構跟前幾題差不多。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 400005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n,q;
int a,b;
int tree[MAX];
//functions
void build(int node){
    if(n<=node)return;
    build(node*2);
    build(node*2+1);
    tree[node]=tree[node*2]^tree[node*2+1];
}
int sum(int a,int b){
    a+=n-1;b+=n-1;
    int s=0;
    while(a<=b){
        while((a&1)==1)s=s^tree[a++];
        while((b&1)==0)s=s^tree[b--];
        a/=2;b/=2;
    }
    return s;
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(int i=n;i<n*2;i++)cin>>tree[i];
    build(1);
    while(q--){
        cin>>a>>b;
        cout<<sum(a,b)<<'\n';
    }
}

# CSES-「Dynamic Programming」解題紀錄
## Elevator Rides
### 題序
>There are n people who want to get to the top of a building which has only one elevator. You know the weight of each person and the maximum allowed weight in the elevator. What is the minimum number of elevator rides?
<https://cses.fi/problemset/task/1653/>
### 考點
這題要用bit來表示有沒有上電梯的集合，可以說是bit和dp的融會貫通，定義pair<int,int>dp[1<<n]是有這些人上電梯的最佳方式，對於(1<<n)將每個1都挑出來看沒有他的最佳解＋他的w[i]會不會比較好，這樣的複雜度是O(kn2^k)。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#define MAX 2000005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
//datas
int n;
int x;
int w[MAX];
pair<int,int>dp[MAX];
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>x;
    for(int i=0;i<n;i++)cin>>w[i];
    dp[0]={1,0};
    for(int i=1;i<(1<<n);i++){
        dp[i]={n+i,0};
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                pair<int,int>option=dp[i^(1<<j)];
                if(option.second+w[j]<=x){
                    option.second+=w[j];
                }else{
                    option.first++;
                    option.second=w[j];
                }
                dp[i]=min(dp[i],option);
            }
        }
    }
    cout<<dp[(1<<n)-1].first;
}

## Edit Distance
### 題序
>The edit distance between two strings is the minimum number of operations required to transform one string into the other.
The allowed operations are:
Add one character to the string.
Remove one character from the string.
Replace one character in the string.
For example, the edit distance between LOVE and MOVIE is 2, because you can first replace L with M, and then add I.
Your task is to calculate the edit distance between two strings.
<https://cses.fi/problemset/task/1639/>
### 考點
定義dp[i][j]是將a的前i項和b的前j項所需的最少操作數，dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+x)，如果a[i]==b[j]的話x就是0，不然是1。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 5005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
string a,b;
int dp[MAX][MAX]={0};
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>a;
    cin>>b;
    for(int i=0;i<=a.size();i++){
        dp[i][0]=i;
    }
    for(int i=0;i<=b.size();i++){
        dp[0][i]=i;
    }
    for(int i=1;i<=a.size();i++){
        for(int j=1;j<=b.size();j++){
            int x=0;
            if(a[i-1]!=b[j-1])x++;
            dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+x);
        }
    }
    cout<<dp[a.size()][b.size()];
}

# CSES- 「Graph Algorithms」解題紀錄
## Counting Rooms
### 題序
>You are given a map of a building, and your task is to count the number of its rooms. The size of the map is n \times m squares, and each square is either floor or wall. You can walk left, right, up, and down through the floor squares.
><https://cses.fi/problemset/task/1192>
### 考點
用dfs看要跑幾次就解決了
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 1005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n,m;
char table[MAX][MAX];
bool nvisited[MAX][MAX]={0};
int cnt=0;
//functions
void dfs(int a,int b){
    nvisited[a][b]=false;
    int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
    for(int i=0;i<4;i++){
        if(nvisited[a+dir[i][0]][b+dir[i][1]]){
            dfs(a+dir[i][0],b+dir[i][1]);
        }
    }
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>table[i][j];
            if(table[i][j]=='.')nvisited[i][j]=true;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(nvisited[i][j]){
                dfs(i,j);
                cnt++;
            }
        }
    cout<<cnt;
}

## Labyrinth
### 題序
>You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.
><https://cses.fi/problemset/task/1193/>
### 考點
用BFS來掃這個迷宮，同時紀錄走的次數，比較麻煩的是要輸出走過的路竟，本來是用class 自定義一個string 的架構，每走一步在字串後面加一個字元附加上去，但這樣有一個測資會ＴＬＥ，其實可以再開一個二維陣列存你是怎麼到這個地方的，之後再一步一步倒退回去。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#define MAX 1005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
class spot{
public:
    int r,c,times;
};
//datas
int n,m;
char laby[MAX][MAX];
bool visited[MAX][MAX]={false};
char route[MAX][MAX];
//functions
bool inrange(int r,int c){
    return r>=1&&r<=n&&c>=1&&c<=m;
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    int ar,ac,br,bc;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>laby[i][j];
            if(laby[i][j]=='A'){
                ar=i;ac=j;
            }
            if(laby[i][j]=='B'){
                br=i;bc=j;
            }
            if(laby[i][j]=='#'){
                visited[i][j]=true;
            }
        }
    queue<spot>q;
    visited[ar][ac]=true;
    q.push({ar,ac,0});
    while(q.size()>0){
        spot t=q.front();q.pop();
        if(t.r==br&&t.c==bc){
            cout<<"YES\n";
            cout<<t.times<<'\n';
            char ans[2000005];
            int ir=t.r,ic=t.c;
            for(int i=t.times;i>0;i--){
                ans[i]=route[ir][ic];
                if(ans[i]=='U'){
                    ir++;
                }else if(ans[i]=='D'){
                    ir--;
                }else if(ans[i]=='L'){
                    ic++;
                }else{
                    ic--;
                }
            }
            for(int i=1;i<=t.times;i++)cout<<ans[i];
            return 0;
        }
        int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
        char rid[4]={'D','U','R','L'};
        for(int i=0;i<4;i++){
            if(inrange(t.r+dir[i][0],t.c+dir[i][1]))
            if(!visited[t.r+dir[i][0]][t.c+dir[i][1]]){
                visited[t.r+dir[i][0]][t.c+dir[i][1]]=true;
                route[t.r+dir[i][0]][t.c+dir[i][1]]=rid[i];
                q.push({t.r+dir[i][0],t.c+dir[i][1],t.times+1});
            }
        }
    }
    cout<<"NO\n";
}

## Building Roads
### 題序
>Byteland has n cities, and m roads between them. The goal is to construct new roads so that there is a route between any two cities.Your task is to find out the minimum number of roads required, and also determine which roads should be built.
><https://cses.fi/problemset/task/1666/>
### 考點
雖然放在圖論但是這題用併查集來寫超快，兩點中間有一條線視為一個整體，最後只要輸出有多少的分開的群體並隨機挑一個出來跟其他群體配對就好。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n,m;
int a,b;
int boss[MAX];
//functions
int find(int x){
    return boss[x]=(x==boss[x])?x:find(boss[x]);
}
void Union(int x,int y){
    x=find(x);
    y=find(y);
    boss[y]=x;
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<=n;i++)boss[i]=i;
    while(m--){
        cin>>a>>b;
        Union(a,b);
    }
    vector<int>v;
    bool visited[MAX]={false};
    for(int i=1;i<=n;i++){
        if(boss[i]==i)v.push_back(i);
    }
    cout<<v.size()-1<<'\n';
    bool p=false;
    int prv;
    for(auto t:v){
        if(!p){
            p=true;
            prv=t;
        }else{
            cout<<prv<<' '<<t<<'\n';
            prv=t;
        }
    }
}

## Message Route
### 題序
>Syrjälä's network has n computers and m connections. Your task is to find out if Uolevi can send a message to Maija, and if it is possible, what is the minimum number of computers on such a route.
><https://cses.fi/problemset/task/1667/>
### 考點
這題可以說是Labyrinth的簡化版，一樣用BFS掃出最近距離，開一個陣列紀錄我們是從哪一格過來的，要輸出的時候再倒退回去求路徑。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#define MAX 100005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n,m;
int a,b;
vector<int>adj[MAX];
bool visited[MAX]={false};
int route[MAX]={0};
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    while(m--){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    visited[1]=true;
    queue<pii>q;
    q.push({1,1});
    while(q.size()>0){
        pii t=q.front();q.pop();
        if(t.first==n){
            cout<<t.second<<'\n';
            int ans[MAX];
            int r=n;
            for(int i=t.second;i>0;i--){
                ans[i]=r;
                r=route[r];
            }
            for(int i=1;i<=t.second;i++){
                cout<<ans[i]<<' ';
            }
            return 0;
        }
        for(auto tmp:adj[t.first]){
            if(!visited[tmp]){
                visited[tmp]=true;
                route[tmp]=t.first;
                q.push({tmp,t.second+1});
            }
        }
    }
    cout<<"IMPOSSIBLE";
}

## Building Teams
### 題序
>There are n pupils in Uolevi's class, and m friendships between them. Your task is to divide the pupils into two teams in such a way that no two pupils in a team are friends. You can freely choose the sizes of the teams.
><https://cses.fi/problemset/task/1668/>
### 考點
要判斷是不是一張二分圖，只需要對每個點用dfs掃一次塗色即可
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 100005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n,m;
int a,b;
vector<int>adj[MAX];
int color[MAX]={0};
bool can=true;
//functions
void col(int source,int c){
    color[source]=c;
    for(int t:adj[source]){
        if(c==1){
            if(color[t]==0)col(t,2);
            if(color[t]==1){
                can=false;
            }
        }
        if(c==2){
            if(color[t]==0)col(t,1);
            if(color[t]==2){
                can=false;
            }
        }
    }
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    while(m--){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        if(color[i]==0){
            col(i,1);
        }
    }
    if(can){
        for(int i=1;i<=n;i++)cout<<color[i]<<' ';
    }else{
        cout<<"IMPOSSIBLE";
    }
}

## Round Trip
### 題序
>Byteland has n cities and m roads between them. Your task is to design a round trip that begins in a city, goes through two or more other cities, and finally returns to the starting city. Every intermediate city on the route has to be distinct.
<https://cses.fi/problemset/task/1669/>
### 考點
要隨機找到一個環並輸出他的路徑，想法很簡單只是實作蠻複雜的，要用dfs掃能走的路徑（除了不能走回頭路都走），如果碰到已經走過的點就代表找到環了，可以用back-tracking回去找路徑。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n,m;
int a,b;
vector<int>adj[MAX];
bool visited[MAX]={0};
int route[MAX];
bool hasprint=false;
//functions
void dfs(int source,int times){
    if(hasprint)return;
    if(visited[source]){
        int x=source;
        int ans[MAX];
        int i;
        for(i=times;i>0;i--){
            ans[i]=x;
            if(i<times&&ans[i]==source)break;
            x=route[x];
        }
        cout<<times-i+1<<'\n';
        for(;i<=times;i++)cout<<ans[i]<<' ';
        hasprint=true;
        return;
    }
    visited[source]=true;
    for(int t:adj[source]){
        if(t!=route[source]){
            route[t]=source;
            dfs(t,times+1);
        }
    }
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    while(m--){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=1;i<=n;i++)if(!visited[i])dfs(i,1);
    if(!hasprint)cout<<"IMPOSSIBLE";
}

## Monsters
### 題序
>You and some monsters are in a labyrinth. When taking a step to some direction in the labyrinth, each monster may simultaneously take one as well. Your goal is to reach one of the boundary squares without ever sharing a square with a monster.
Your task is to find out if your goal is possible, and if it is, print a path that you can follow. Your plan has to work in any situation; even if the monsters know your path beforehand.
<https://cses.fi/problemset/task/1194/>
### 考點
用ＢＦＳ同時跑A,M的路徑，並隨時更新laby[][]來控制A,M能不能往那個方向走，實作超級麻煩，最後還要backtracking。累。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#define MAX 1005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
class step{
public:
    int r,c,times;
    //char color;
};
//datas
int n,m;
char laby[MAX][MAX];
char route[MAX][MAX];
bool can=false;
//functions
bool inrange(int r,int c){
    return r>=1&&r<=n&&c>=1&&c<=m;
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    queue<step>q;
    queue<step>q2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>laby[i][j];
            if(laby[i][j]=='A'){
                q.push({i,j,0});
            }
            if(laby[i][j]=='M'){
                q2.push({i,j,0});
            }
        }
    while(q2.size()>0){
        q.push(q2.front());q2.pop();
    }
    while(q.size()>0){
        step t=q.front();q.pop();
        if(laby[t.r][t.c]=='A'&&(t.r==1||t.r==n||t.c==1||t.c==m)){
            cout<<"YES\n";
            cout<<t.times<<'\n';
            char ans[1000005];
            int sr=t.r,sc=t.c;
            for(int i=t.times;i>0;i--){
                ans[i]=route[sr][sc];
                if(ans[i]=='D'){
                    sr-=1;
                }
                if(ans[i]=='U'){
                    sr+=1;
                }
                if(ans[i]=='L'){
                    sc+=1;
                }
                if(ans[i]=='R'){
                    sc-=1;
                }
            }
            for(int i=1;i<=t.times;i++){
                cout<<ans[i];
            }
            can=true;
            break;
        }
        /*if(laby[t.r][t.c]=='A'){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    cout<<laby[i][j];
                }
                cout<<'\n';
            }
            cout<<'\n';
        }*/
        int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
        char cr[4]={'R','L','D','U'};
        for(int i=0;i<4;i++){
            int nr=t.r+dir[i][0];
            int nc=t.c+dir[i][1];
            if(inrange(nr,nc)){
                    if(laby[t.r][t.c]=='M'){
                        if(laby[nr][nc]=='A'||laby[nr][nc]=='.'){
                            q.push({nr,nc,t.times+1});
                            laby[nr][nc]='M';
                        }
                    }else if(laby[t.r][t.c]=='A'){
                        if(laby[nr][nc]=='.'){
                            q.push({nr,nc,t.times+1});
                            route[nr][nc]=cr[i];
                            laby[nr][nc]='A';
                        }
                    }
            }
        }
    }
    if(!can)cout<<"NO"<<'\n';
    /*for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<laby[i][j];
        }
        cout<<'\n';
    }*/
}

## Shortest Routes I
### 題序
>There are n cities and m flight connections between them. Your task is to determine the length of the shortest route from Syrjälä to every city.
><https://cses.fi/problemset/task/1671/>
### 考點
這題是dijkstra演算法的裸題，求單點元問題。實作上用priority_queue存到那邊的最小值。要注意的是這題是單向道路。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<long long,long long>pll;
typedef pair<int,int> pii;
//datas
int n,m;
int a,b,c;
vector<pll>adj[MAX];
ll dis[MAX]={0};
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    while(m--){
        cin>>a>>b>>c;
        adj[a].push_back({c,b});
    }
    for(int i=1;i<=n;i++)dis[i]=LLONG_MAX;
    priority_queue<pll,vector<pll>,greater<pll>>pq;
    pq.push({0,1});
    while(pq.size()>0){
        pll t=pq.top();pq.pop();
        if(dis[t.second]>t.first){
            dis[t.second]=t.first;
            for(auto tmp:adj[t.second]){
                if(dis[tmp.second]>dis[t.second]+tmp.first){
                    pq.push({dis[t.second]+tmp.first,tmp.second});
                }
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
}

## Shortest Route II
### 題序
>There are n cities and m roads between them. Your task is to process q queries where you have to determine the length of the shortest route between two given cities.
><https://cses.fi/problemset/task/1672/>
### 考點
全點對最短路徑的裸題，用到Floyd-Warshall演算法，主體其實很簡單，就是一個三層迴圈，但是k要在最外面，然後INF的值要特判出來。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 505
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n,m,q;
ll adm[MAX][MAX];
int a,b,c;
//functions

//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            adm[i][j]=LLONG_MAX;
        }
    }
    for(int i=1;i<=n;i++)adm[i][i]=0;
    while(m--){
        cin>>a>>b>>c;
        if(c<adm[a][b]){
            adm[a][b]=c;
            adm[b][a]=c;
        }
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(adm[i][k]!=LLONG_MAX&&adm[k][j]!=LLONG_MAX&&adm[i][k]+adm[k][j]<adm[i][j]){
                    adm[i][j]=adm[i][k]+adm[k][j];
                }
            }
        }
    }
    while(q--){
        cin>>a>>b;
        if(adm[a][b]==LLONG_MAX)cout<<"-1\n";
        else cout<<adm[a][b]<<'\n';
    }
}

# CSES-「Tree Algorithms」解題紀錄
## Subordinates
### 題序
>Given the structure of a company, your task is to calculate for each employee the number of their subordinates.
><https://cses.fi/problemset/task/1674/>
### 考點
以1為根，找每一個節點的子節點數量，用dfs 和dp的角度來做
### AC code

#include<cstdio>
#include<vector>
#define MAX 200005
using namespace std;
vector<int>adj[MAX];
int cnt[MAX]={0};
void dfs(int source,int prv){
    for(int t:adj[source])
        if(t!=prv){
            dfs(t,source);
            cnt[source]+=cnt[t]+1;
        }
}
int main(){
    int n;scanf("%d",&n);
    for(int i=2;i<=n;i++){
        int tmp;scanf("%d",&tmp);
        adj[tmp].push_back(i);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)printf("%d ",cnt[i]);
}

## Tree Diameter
### 題序
>You are given a tree consisting of n nodes.
The diameter of a tree is the maximum distance between two nodes. Your task is to determine the diameter of the tree.
<https://cses.fi/problemset/task/1131/>
### 考點
做兩次dfs找出最大值
### AC code

#include<cstdio>
#include<vector>
#define MAX 200005
using namespace std;
int n;
int a,b;
vector<int>adj[MAX];
int dis[MAX];
int mx,mxid;
void dfs(int source,int prv,int cnt){
    dis[source]=cnt;
    if(cnt>mx){
        mx=cnt;
        mxid=source;
    }
    for(int t:adj[source]){
        if(t!=prv){
            dfs(t,source,cnt+1);
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        scanf("%d %d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    mx=0;mxid=0;
    dfs(1,0,0);
    dfs(mxid,0,0);
    printf("%d",mx);
}

## Tree Disances I
### 題序
>You are given a tree consisting of n nodes.
Your task is to determine for each node the maximum distance to another node.
<https://cses.fi/problemset/task/1132/>
### 考點
這題在考求每一個節點到其他節點的最遠距離All longest paths，終於開始遇到難懂的演算法了（怎麼有點興奮！）。分兩次做dfs，第一次以1為根，求每一個節點的子節點能延伸最遠的前兩名，同時要紀錄第一名是要走哪一個子節點。第二次dfs有點dp的概念，對於第一名的子節點他的最大值是自己的first或是父節點的second，如果是後者那c[]就要紀錄成父節點，同時改變數值。注意第一次dfs是bottom up的，第二次是top down的。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n;
int a,b;
vector<int>adj[MAX];
int first[MAX]={0};
int second[MAX]{0};
int c[MAX]={0};
//functions
void dfs1(int source,int prv){
    for(int t:adj[source]){
        if(t!=prv){
            dfs1(t,source);
            if(first[t]+1>=first[source]){
                second[source]=first[source];
                first[source]=first[t]+1;
                c[source]=t;
            }else if(first[t]+1>second[source]){
                second[source]=first[t]+1;
            }
        }
    }
}
void dfs2(int source,int prv){
    for(int t:adj[source]){
        if(t!=prv){
            if(t==c[source]){
                if(first[t]<second[source]+1){
                    second[t]=first[t];
                    first[t]=second[source]+1;
                    c[t]=source;
                }else{
                    if(second[t]<second[source]+1){
                        second[t]=second[source]+1;
                    }
                }
            }else{
                second[t]=first[t];
                first[t]=first[source]+1;
                c[t]=source;
            }
            dfs2(t,source);
        }
    }
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++)cout<<first[i]<<' ';
}

## Tree Matching
### 題序
>You are given a tree consisting of n nodes.
A matching is a set of edges where each node is an endpoint of at most one edge. What is the maximum number of edges in a matching?
<https://cses.fi/problemset/task/1130/>
### 考點
這題要用dp的角度來看，定義dp[i][0]是i子樹y在i節點沒被用到的情況下的最大值，dp[i][1]是有用到的時候。對於dp[i][0]就是所有子節點dp[j][1]相加。dp[i][1]是考慮過選擇要連接每個子樹的最大值，要選的子樹dp[j][0]-dp[j][1]+1要最大，之後就能好好轉移了。然後抱怨一下，這題CPH講義沒寫，看APCSCamp的講義是寫錯的，查judge的詳解結果也是錯的？還得是自己想。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 500005
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n;
int a,b;
vector<int>adj[MAX];
int dp[MAX][2]={0};
//functions
void dfs(int source,int prv){
    for(int t:adj[source]){
        if(t!=prv)dfs(t,source);
    }
    int mx=-1,mxid=0;
    for(int t:adj[source]){
        if(t!=prv){
            dp[source][0]+=dp[t][1];
            if(dp[t][0]-dp[t][1]+1>mx){
                mx=dp[t][0]-dp[t][1]+1;
                mxid=t;
            }
        }
    }
    for(int t:adj[source]){
        if(t!=prv){
            if(t==mxid){
                dp[source][1]+=dp[t][0]+1;
            }else{
                dp[source][1]+=dp[t][1];
            }
        }
    }
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        adj[b].push_back(a);
        adj[a].push_back(b);
    }
    dfs(2,0);
    cout<<dp[2][1];
}

## Tree Distances II
### 題序
>You are given a tree consisting of n nodes.
Your task is to determine for each node the sum of the distances from the node to all other nodes.
><https://cses.fi/problemset/task/1133/>
### 考點
這題要用父節點的答案來O(1)推當前節點值，以1為根，先算leaf[]代表子樹的節點數，subans是用來算1的ans，之後的ans算法是父節點+n-2*leaf[i]，這個算法是我自己慧思出來的，好有成就感。
### AC code

#include<iostream>
#include<climits>
#include<algorithm>
#include<utility>
#include<vector>
#define MAX 200005
#define out cout<<"\n";
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//datas
int n;
int a,b;
vector<int>adj[MAX];
int leaf[MAX]={0};
ll subans[MAX]={0};
ll ans[MAX]={0};
//functions
void mkleaf(int source,int prv){
    if(adj[source].size()==0){
        leaf[source]=1;
        return;
    }
    for(int t:adj[source]){
        if(t!=prv){
            mkleaf(t,source);
            leaf[source]+=leaf[t];
        }
    }
    leaf[source]++;
}
void findsubans(int source,int prv){
    if(adj[source].size()==0){
        subans[source]=0;
        return;
    }
    for(int t:adj[source]){
        if(t!=prv){
            findsubans(t,source);
            subans[source]+=subans[t]+leaf[t];
        }
    }
}
void findans(int source,int prv){
    ans[source]=ans[prv]-leaf[source]*2+n;
    for(int t:adj[source]){
        if(t!=prv){
            findans(t,source);
        }
    }
}
//
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    mkleaf(1,0);
    findsubans(1,0);
    ans[0]=subans[1]+leaf[1];
    findans(1,0);
    //for(int i=1;i<=n;i++)cout<<leaf[i]<<' ';
    //out
    //for(int i=1;i<=n;i++)cout<<subans[i]<<' ';
    //out
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    //out
}