快排

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N];
void q_sort(int q[],int l,int r){
    if(l>=r)return;
    int i = l-1,j = r+1,x = q[(l+r)/2];
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)swap(q[i],q[j]);
    }
    q_sort(q,l,j),q_sort(q,j+1,r);
}
int n;
int main(){
    cin>>n;
    for(int i = 0;i<n;++i)cin>>q[i];
    q_sort(q,0,n-1);
    for(int i = 0;i<n;++i)cout<<q[i]<<" ";
    return 0;
}

快选

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N];
int quick_sort(int q[],int l,int r,int k){
    if(l>=r)return q[l];
    int i = l-1,j = r+1,x = q[(l+r)/2];
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)swap(q[i],q[j]);
    }
    int sl = j-l+1;
    if(sl>=k)return quick_sort(q,l,j,k);
    else return quick_sort(q,j+1,r,k-sl);
}
int k,n;
int main(){
    cin>>n>>k;
    for(int i = 0;i<n;i++)cin>>q[i];
    cout<<quick_sort(q,0,n-1,k);
    return 0;
}

归排

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N],tmp[N];
void m_sort(int q[],int l,int r){
    if(l>=r)return;
    int mid = l+r>>1;
    m_sort(q,l,mid),m_sort(q,mid+1,r);
    int k = 0,i = l,j = mid+1;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j])tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    while(i<=mid)tmp[k++] = q[i++];
    while(j<=r)tmp[k++] = q[j++];
    for(int i = l,j = 0;i<=r;i++,j++)q[i] = tmp[j];
}
int n;
int main(){
    cin>>n;
    for(int i = 0;i<n;i++)cin>>q[i];
    m_sort(q,0,n-1);
    for(int i = 0;i<n;i++)cout<<q[i]<<" ";
    return 0;
}

分治 逆序对

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
int q[N],tmp[N];
ll m_sort(int q[],int l,int r){
    if(l>=r)return 0;
    int mid = l+r>>1;
    ll res = m_sort(q,l,mid)+m_sort(q,mid+1,r);
    int i = l,j = mid+1,k=0;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j])tmp[k++] = q[i++];
        else{
            res+=mid-i+1;
            tmp[k++] = q[j++];
        }
    }
    while(i<=mid)tmp[k++] = q[i++];
    while(j<=r)tmp[k++] = q[j++];
    for(int i = l,j = 0;i<=r;i++,j++)q[i] = tmp[j];
    return res;
}
int main(){
    int n;cin>>n;
    for(int i = 0;i<n;i++)cin>>q[i];
    cout<<m_sort(q,0,n-1);
    return 0;
}

整数二分

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n,q;
int main(){
    cin>>n>>q;
    for(int i = 0;i<n;i++)cin>>a[i];
    while(q--){
        int x;cin>>x;
        int l = 0,r = n-1;
        while(l<r){
            int mid = l+r>>1;
            if(a[mid]>=x)r = mid;
            else l = mid+1;
        }
        if(a[l] != x)puts("-1 -1");
        else{
            cout<<l<<" ";
            l = 0,r = n-1;
            while(l<r){
                int mid  = l+r+1>>1;
                if(a[mid]<=x)l = mid;
                else r = mid-1;
            }
            cout<<r<<endl;
        }
    }
}

浮点二分

#include<bits/stdc++.h>
using namespace std;
int main(){
    double x;int f;
    cin>>x;
    if(x<0)f=1,x = -x;
    double l = 0,r = 10000000,mid;
    while(l<r){
        mid = (l+r)/2;
        if(abs(mid*mid*mid-x)<0.0000000001)break;
        if(mid*mid*mid<x)l = mid;
        else r = mid;
    }
    printf("%.6lf",!f?mid:-mid);
}

高精度加法（不压位）

#include<bits/stdc++.h>
using namespace std;
vector<int> add(vector<int> &A,vector<int> &B){
    if(A.size()<B.size())return add(B,A);
    int t = 0;
    vector<int> C;
    for(int i = 0;i<A.size();i++){
        t += A[i];
        if(i<B.size())t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t)C.push_back(t);
    return C;
}
int main(){
    string a,b;cin>>a>>b;
    vector<int> A,B;
    for(int i = a.size()-1;i>=0;--i)A.push_back(a[i]-'0');
    for(int i = b.size()-1;i>=0;--i)B.push_back(b[i]-'0');
    auto C = add(A,B);
    for(int i = C.size()-1;~i;--i)cout<<C[i];
    return 0;
}

高精度减法

#include<bits/stdc++.h>
using namespace std;
bool cmp(string a,string b){
    if(a.size()!=b.size())return a.size()>b.size();
    for(int i = 0;i<a.size();i++)
        if(a[i]!=b[i])return a[i]>b[i];
    return true;
}
string sub(string a,string b){
    if(!cmp(a,b))return "-" + sub(b,a);
    vector<int> A,B;
    for(int i = a.size()-1;~i;--i)A.push_back(a[i]-'0');
    for(int i = b.size()-1;~i;--i)B.push_back(b[i]-'0');
    vector<int> C;
    for(int i = 0,t = 0;i<A.size();i++){
        t = A[i] - t;
        if(i<B.size())t -= B[i];
        C.push_back((t+10)%10);
        t<0?(t=1):(t=0);
    }
    while(C.size()>1&&C.back()==0)C.pop_back();
    string c;
    for(int i = C.size()-1;~i;--i)c+=to_string(C[i]);
    return c;
}
int main(){
    string a,b;cin>>a>>b;
    cout<<sub(a,b)<<endl;
    return 0;
}

高进度乘法

#include<bits/stdc++.h>
using namespace std;
vector<int> mul(vector<int> A,int b){
    vector<int> C;
    int t = 0;
    for(int i = 0;i<A.size()||t;i++){
        if(i<A.size())t += A[i] * b;
        C.push_back(t%10);
        t/=10;
    }
    while(C.size()>1&&C.back()==0)C.pop_back();
    return C;
}
int main(){
    string a;int b;
    cin>>a>>b;
    vector<int> A;
    for(int i = a.size()-1;~i;--i)A.push_back(a[i]-'0');
    auto C = mul(A,b);
    for(int i = C.size()-1;~i;--i)cout<<C[i];
    return 0;
}

高精度除法

#include<bits/stdc++.h>
using namespace std;
vector<int> div(vector<int> A,int b,int &r){
    vector<int> C;
    r = 0;
    for(int i = A.size()-1;~i;--i){
        r = r*10+A[i];
        C.push_back(r/b);
        r%=b;
    }
    reverse(C.begin(),C.end());
    while(C.back()==0&&C.size()>1)C.pop_back();
    return C;
}
int main(){
    string a;int b,r;
    cin>>a>>b>>r;
    vector<int> A;
    for(int i = a.size()-1;~i;--i)A.push_back(a[i]-'0');
    auto C = div(A,b,r);
    for(int i = C.size()-1;~i;--i)cout<<C[i];
    cout<<endl<<r<<endl;
    return 0;
}

前缀和

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
    int n,m;cin>>n>>m;for(int i = 1;i<=n;i++){cin>>a[i];a[i]+=a[i-1];}
    while(m--){
        int l,r;cin>>l>>r;cout<<a[r]-a[l-1]<<endl;
    }
    return 0;
}

2d前缀和

#include<bits/stdc++.h>
using namespace std;
int s[1010][1010];
int n,m,q;
int main(){
    cin>>n>>m>>q;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++){cin>>s[i][j];s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];}
    while(q--){
        int a,b,c,d;cin>>a>>b>>c>>d;
        cout<<s[c][d]-s[c][b-1]-s[a-1][d]+s[a-1][b-1]<<endl;
    }    
    return 0;
}

1d差分

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int d[N];
int main(){
    int n,m;cin>>n>>m;
    for(int i = 1;i<=n;i++){
        int x;cin>>x;d[i]+=x;d[i+1]-=x;
    }
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        d[a]+=c,d[b+1]-=c;
    }
    for(int i = 1;i<=n;i++){d[i] += d[i-1];cout<<d[i]<<" ";}
    return 0;
}

2d差分

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int d[N][N];
int n,m,q;
void insert(int h,int i,int j,int k,int c){
    d[h][i]+=c,d[h][k+1]-=c,d[j+1][i]-=c,d[j+1][k+1]+=c;
}
int main(){
    cin>>n>>m>>q;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++){
            int x;cin>>x;insert(i,j,i,j,x);
        }
    while(q--){
        int h,i,j,k,c;
        cin>>h>>i>>j>>k>>c;
        insert(h,i,j,k,c);
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            d[i][j] += d[i-1][j] + d[i][j-1] -d[i-1][j-1];cout<<d[i][j]<<" ";}
        puts("");
    }    
    return 0;
}

双指针最长不重复子序列

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main(){
    int n,res = 0;cin>>n;
    for(int i = 0;i<n;i++)cin>>a[i];
    map<int,int> s;
    for(int i = 0,j=0;i<n;i++){
        s[a[i]]++;
        while(s[a[i]]>1)s[a[j++]]--;
        res = max(res,i-j+1);
    }
    cout<<res;
    return 0;
}

双指针

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],b[N];
int main(){
    int n,m,x;
    cin>>n>>m>>x;
    for(int i = 0;i<n;i++)cin>>a[i];
    for(int j = 0;j<m;j++)cin>>b[j];
    for(int i = 0,j=m-1;i<n;i++){
        while(~j&&b[j]+a[i]>x)j--;
        if(b[j]+a[i]==x){
            cout<<i<<" "<<j<<endl;
            break;
        }
    }
    return 0;
}

双指针 判断子序列

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 100010;
int a[N],b[N];
int main(){
    cin>>n>>m;
    for(int i = 0;i<n;i++)cin>>a[i];
    for(int j = 0;j<m;j++)cin>>b[j];
    int i = 0,j = 0;
    while(i<n&&j<m){
        if(a[i]==b[j])i++;
        j++;
    }
    if(i==n)puts("Yes");
    else puts("No");
    return 0;
}

二进制

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    while(n--){
        int res = 0;
        int x;cin>>x;
        while(x)x-=x&(~x+1),res++;
        printf("%d ",res);
    }
}

区间合并

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
void merge(vector<pii> &segs){
    sort(segs.begin(),segs.end());
    vector<pii> res;
    int st = -2e9,ed = -2e9;
    for(auto seg:segs){
        if(ed<seg.first){
            if(st!=-2e9)res.push_back({st,ed});
            st = seg.first,ed = seg.second;
        }
        else ed = max(ed,seg.second);
    }
    if(st!=-2e9)res.push_back({st,ed});
    segs = res;
}
int main(){
    int n;
    vector<pii> segs;
    cin>>n;
    for(int i = 0;i<n;i++){
        int l,r;cin>>l>>r;
        segs.push_back({l,r});
    }
    merge(segs);
    cout<<segs.size()<<endl;
    return 0;
}