OI模板汇总

上一版的算法名称不能识别到目录，不好找，于是有了这一版本

数学算法

求解GCD

int gcd(int x,int y) {
    return y?gcd(y,x%y):x;
}

快速幂

int qpow(int a,int b,int mod) {
    int tmp=a,ans=1;
    while(b){
        if(b&1){
            ans=ans*tmp%mod;
        }
        b>>=1;
        tmp=tmp*tmp%mod;
    }
    return ans;
}

逆元（质数）数组初始化

void init(){
    fac[0]=1;
    for(int i=1;i<=100000;i++) {
        fac[i]=fac[i-1]*i%mod;
    }
    inv[100000]=qpow(fac[100000],mod-2,mod);
    for (int i=100000-1;i>=0;i--) {
        inv[i]=inv[i+1]*(i+1)%mod; 
    }
}

组合数（C）

int C(int n,int m){
    if(n<m){
        return 0;
    }
    else{
        return fac[n]*inv[m]%mod*inv[n-m]%mod;
    }
}

矩阵类（附带快速幂）

class Matrix {
        int dat[101][101];
        int size;
    public:
        Matrix(int size_=0) {
            memset(dat,0,sizeof(dat));
            size=size_;
        }
        void set_init(){
            for(int i=1;i<=size;i++)
                dat[i][i]=1;
        }
        void set(int x,int y,int v) {
            dat[x][y]=v;
        }
        int get(int x,int y) {
            return dat[x][y]%MOD;
        }
        friend Matrix operator * (Matrix &a_,Matrix &b_){
            Matrix ans_(a_.size);
            for(int i=1; i<=a_.size; i++) {
                for(int j=1; j<=a_.size; j++) {
                    for(int k=1; k<=a_.size; k++) {
                        ans_.dat[i][j]+=a_.dat[i][k]*b_.dat[k][j]%MOD;
                        ans_.dat[i][j]%=MOD;
                    }
                }
            }
            return ans_;
        }
        friend Matrix operator ^ (Matrix n_,int k_){
            if(k_==1)return n_;
            Matrix ans_(n_.size);
            ans_.set_init();
            while(k_) {
                if(k_&1)
                    ans_=ans_*n_;
                n_=n_*n_;
                k_>>=1;
            }
            return ans_;
        }
};

线性筛求素数

int prime[20000001],cnt;
void init(int n){
    for(int i=2;i<=n;i++){
        if(lst[i]==false)
            prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
            lst[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        } 
    }
}

ExGCD

void exgcd(int a,int b,int&x,int&y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int z=x;
    x=y;
    y=z-y*(a/b);
}

中国剩余定理（CRT）

void exgcd(int a,int b,int&x,int&y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int z=x;
    x=y;
    y=z-y*(a/b);
}
int CRT(int n,vector<int>M,vector<int>a,int mul){
    int ans=0;
    vector<int>Mi(n+10);
    for(int i=1;i<=n;i++){
        Mi[i]=mul/M[i];
        int x=0,y=0;
        exgcd(Mi[i],M[i],x,y);
        ans+=a[i]*Mi[i]*(x<0?x+M[i]:x);
    }
    return ans%mul;
}

扩展中国剩余定理（ExCRT）

int exgcd(int a,int b,int&x,int&y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int g=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return g;
}
int exCRT(int n,vector<int>M,vector<int>a){
    int m=M[1],ans=a[1],x=0,y=0;
    for(int i=2;i<=n;i++){
        int c=((a[i]-ans)%M[i]+M[i])%M[i];
        int g=exgcd(m,M[i],x,y);
        int p=M[i]/g;
        x=__int128(x)*__int128(c/g)%p;
        ans+=x*m;
        m*=p;
        ans=(ans%m+m)%m;
    }
    return ans;
}

自适应辛普森法

double f(double x){
    //自定义函数
}
double simpson(double l,double r){
    return (r-l)*(f(l)+f(r)+4*f((l+r)/2))/6;
}
double asr(double l,double r,double ans,double eps){
    double mid=(l+r)/2;
    double ll=simpson(l,mid),rr=simpson(mid,r);
    if(fabs(ll+rr-ans)/15<=eps)return ll+rr+(ll+rr-ans)/15;
    return asr(l,mid,ll,eps/2)+asr(mid,r,rr,eps/2);
}

Nim博弈

直接判断异或和是否等于0即可

图论算法

LCA（ST）

struct LCA{
    int n,s;
    vector<int>G[1000100];
    int st[600100][40];
    const int st_max=30;
    int dep[600100];
    int fa[600100];
    int vis[600100];
    void dfs(int now,int d){
        vis[now]=1;
        dep[now]=d;
        for(auto i:G[now]){
            if(vis[i]){
                continue;
            }
            fa[i]=now;
            dfs(i,d+1);
        }
    }
    void make_st(){
        for(int i=1;i<=n;i++){
            st[i][0]=fa[i];
        }
        for(int j=1;j<=st_max;j++){
            for(int i=1;i<=n;i++){
                st[i][j]=st[st[i][j-1]][j-1];
            }
        }
    }
    void init(){
        fa[s]=s;
        dfs(s,1);
        make_st();
    }
    int lca(int a,int b){
        if(dep[a]>dep[b]){
            swap(a,b);
        }
        for(int i=st_max;i>=0;i--){
            if(dep[b]>(1<<i)&&dep[st[b][i]]>=dep[a]){
                b=st[b][i];
            }
        }
        if(a==b){
            return a;
        }
        for(int i=st_max;i>=0;i--){
            if(dep[a]>(1<<i)&&dep[b]>(1<<i)&&st[a][i]!=st[b][i]){
                a=st[a][i];
                b=st[b][i];
            }
        }
        return st[b][0];
    }
}Graph;

LCA（Tarjan）

int n,m,s,fa[500005];
vector<int>G[500005];
vector<int>ask[500005];
int ans[500005],vis[500005];
int asku[500005];
int askv[500005];
int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]);
    }
    return fa[x];
}
void addask(int i,int u,int v){
    asku[i]=u,askv[i]=v;
    ask[u].push_back(i);
    ask[v].push_back(i);
}
void tarjan(int ffa,int u){
    vis[u]=1;
    for(auto v:G[u]){
        if(v==ffa)continue;
        tarjan(u,v);
        fa[v]=u;
    }
    for(auto i:ask[u]){
        if(asku[i]==u){
            if(vis[askv[i]]){
                ans[i]=find(askv[i]);
            }
        }
        else if(askv[i]==u){
            if(vis[asku[i]]){
                ans[i]=find(asku[i]);
            }
        }
    }
}

最小生成树

//不要忘记并查集初始化!!!
#define int long long
int n,m;
struct edge{
    int u,v,w;
}G[1000001];
int fa[1000001];
int find(int x){
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}
bool cmp(edge _1,edge _2){
    return _1.w<_2.w;
}
int Kruskal(){
    int ans=0,tot=0;
    for(int i=1;i<=m;i++){
        int fx=find(G[i].u);
        int fy=find(G[i].v);
        if(fx!=fy){
            fa[fx]=fy;
            ans+=G[i].w;
            tot++;
            if(tot==n-1){
                return ans;
            }
        }
    }
    return -1;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>G[i].u>>G[i].v>>G[i].w;
    }
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    sort(G+1,G+m+1,cmp);
    int tmp=Kruskal();
    if(tmp==-1)cout<<"orz"<<endl;
    else cout<<tmp<<endl;
    return 0;
}

Dijkstra

struct edge{
    int v,w;
}; 
struct node{
    int x,d;
    friend bool operator < (node tmp_x,node tmp_y){
        return tmp_x.d>tmp_y.d;
    }
};
vector<edge>e[100001];
int dis[100001],vis[100001];
priority_queue<node>q;
void dijkstra(int n,int s){
    memset(dis,0x3f,sizeof(dis));
    while(!q.empty())q.pop();
    q.push({s,0});
    dis[s]=0;
    while(!q.empty()){
        int now=q.top().x;
        q.pop();
        if(!vis[now]){
            vis[now]=1;
            for(auto ed:e[now]){
                int v=ed.v;
                int w=ed.w;
                if(dis[v]>dis[now]+w){
                    dis[v]=dis[now]+w;
                    q.push({v,dis[v]});
                }
            }
        }
    }
}

SPFA（判负环）

struct edge{
    int v,w;
};
struct node{
    int x,d;
};
vector<edge>G[200005];
queue<int>q;
int dis[200005];
int vis[200005];
int tot[200005];
bool spfa(){
    memset(dis,0x3f,sizeof(dis));
    memset(tot,0,sizeof(tot));
    while(!q.empty())q.pop();
    q.push(1);
    dis[1]=0;
    vis[1]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto i:G[u]){
            if(dis[i.v]>dis[u]+i.w){
                dis[i.v]=dis[u]+i.w;
                tot[i.v]=tot[u]+1;
                if(tot[i.v]>=n){
                    return true;
                }
                q.push(i.v);
                vis[i.v]=1;
            }
        }
    }
    return false;
}

拓扑排序

#include<bits/stdc++.h>
using namespace std;
int n;
int deg[1001];
//deg[] : 入度
vector<int>G[1001];
queue<int>q;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        while(cin>>x&&x){
            G[i].push_back(x);
            deg[x]++;
        }
    }
    for(int i=1;i<=n;i++){
        if(deg[i]==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front();
        cout<<u<<" ";
        q.pop();
        for(auto v:G[u]){
            deg[v]--;
            if(deg[v]==0){
                q.push(v);
            }
        }
    }
    return 0;
}

强连通分量

vector<int>G[50001];
int n,m,tot,at;
bool vis[50001],V[50001];
int dfn[50001];
int low[50001];
vector<int>ans[50001];
stack<int>s;
void tarjan(int u){
    s.push(u);
    V[u]=true;
    vis[u]=true;
    dfn[u]=++tot;
    low[u]=dfn[u];
    for(auto v:G[u]){
        if(!V[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        at++;
        int tmp;
        do{
            tmp=s.top();
            ans[at].push_back(tmp);
            vis[tmp]=false;
            s.pop();
        }while(!s.empty()&&tmp!=u);
    }
}

点双连通分量

const int N=500005;
int n,m,idx;
vector<int>G[N];
int dfn[N],low[N];
stack<int>s;
int ansCnt;
vector<int>ans[N];
void tarjan(int fa,int u){
    s.push(u);
    dfn[u]=low[u]=++idx;
    for(auto v:G[u]){
        if(v==fa)continue;
        if(!dfn[v]){
            tarjan(u,v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                ansCnt++;
                // while(s.top()!=u){
                //   ans[ansCnt].push_back(s.top());
                //   s.pop();
                // }
                int tmp;
                do{
                    tmp=s.top();
                    ans[ansCnt].push_back(tmp);
                    s.pop();
                }while(tmp!=v);
                ans[ansCnt].push_back(u);
            }
        }
        else{
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(fa==-1&&G[u].size()==0){
        ansCnt++;
        ans[ansCnt].push_back(u);
    }
}

边双连通分量

const int N=500005;
int n,m,idx;
vector<int>G[N];
int dfn[N],low[N];
stack<int>s;
int ansCnt;
vector<int>ans[N];
unordered_map<int,int>bridge;
unordered_map<int,int>edge;
unordered_map<int,int>ok;
void tarjan(int fa,int u){
    s.push(u);
    dfn[u]=low[u]=++idx;
    for(auto v:G[u]){
        if(v==fa)continue;
        if(!dfn[v]){
            tarjan(u,v);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
                bridge[u*N+v]=!ok[u*N+v];
                bridge[v*N+u]=!ok[u*N+v];
            }
        }
        else{
            low[u]=min(low[u],dfn[v]);
        }
    }
}
bool vis[N];
void dfs(int u){
    vis[u]=1;
    ans[ansCnt].push_back(u);
    for(auto v:G[u]){
        if(!vis[v]&&(!bridge[u*N+v])){
            dfs(v);
        }
    }
}

割点

const int maxn=20000;
vector<int>G[maxn+100];
int dfn[maxn+100],low[maxn+100],tot;
int n,m;
vector<int>cut;
void Tarjan(int u,int root){
    low[u]=dfn[u]=++tot;
    int cnt=0;
    for(auto v:G[u]){
        if(!dfn[v]){
            Tarjan(v,root);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])cnt++;
        }
        else{
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(u==root){
        if(cnt>1)cut.push_back(u);
    }
    else 
        if(cnt>0)cut.push_back(u);
}

网络流加边

void add(int u,int v,int w){
    int ru=G[v].size();
    int rv=G[u].size();
    G[u].push_back({v,w,ru});
    G[v].push_back({u,0,rv});
}

EK网络流

int n,m,s,t;
struct edge{
    int v,w,r;
};
vector<edge>G[10001];
bool vis[10001];
int mn,pre[10001],lst[10001];
int bfs(){
    memset(vis,0,sizeof(vis));
    vis[s]=true;
    queue<int>q;
    q.push(s);
    mn=0x3f3f3f3f;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].v,w=G[u][i].w,r=G[u][i].r;
            if(!vis[v]&&w>0){
                mn=min(mn,w);
                vis[v]=true;
                lst[v]=u;
                pre[v]=i;
                q.push(v);
                if(v==t){
                    return mn;
                }
            }
        }
    }
    return 0;
}
int EK(){
    int ans=0;
    while(true){
        int now=bfs();
        if(!now)break;
        ans+=now;
        for(int i=t;i!=s;i=lst[i]){
            G[lst[i]][pre[i]].w-=now;
            G[i][G[lst[i]][pre[i]].r].w+=now;
        }
    }
    return ans;
}

Dinic网络流

int n,m,s,t;
struct edge{
    int v,w,r;
};
vector<edge>G[10001];
bool vis[10001];
int d[10001],p[10001];
bool bfs(){
    memset(d,-1,sizeof(d));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s);
    vis[s]=true;
    d[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto i:G[u]){
            int v=i.v,w=i.w;
            if(!vis[v]&&w&&d[v]==-1){
                d[v]=d[u]+1;
                vis[v]=true;
                q.push(v);
            }
        }
    }
    if(d[t]==-1)return false;
    else return true;
}
int dfs(int u,int lim){
    if(u==t)return lim;
    for(int i=p[u];i<G[u].size();i++){
        p[u]=i;
        int v=G[u][i].v,w=G[u][i].w,r=G[u][i].r;
        if(d[v]==d[u]+1&&w){
            int tmp=dfs(v,min(lim,w));
            if(tmp){
                G[u][i].w-=tmp;
                G[v][G[u][i].r].w+=tmp;
                return tmp;
            }
            else{
                d[v]=-1;
            }
        }
    }
    return 0;
}
int dinic(){
    int ans=0;
    while(bfs()){
        memset(p,0,sizeof(p));
        while(true){
            int now=dfs(s,0x3f3f3f3f);
            if(now==0)break;
            ans+=now;
        }
    }
    return ans;
}

差分约束

struct SDC{
    struct g_node{
        int v,w;
    };
    vector<g_node>G[maxn+100];
    struct node{
        int u,v,w;
        //a-b<=w
    };
    int dis[maxn+10],vis[maxn+100],cnt[maxn+100];
    queue<int>q;
    bool SPFA(int s,int n){
        memset(dis,0x3f,sizeof(dis));
        dis[s]=0;
        vis[s]=1;
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
//          cout<<"u="<<u<<endl;
            for(auto tmp:G[u]){
                int v=tmp.v;
                int w=tmp.w;
//              cout<<u<<"->"<<v<<"("<<w<<")"<<endl;
                if(dis[v]>dis[u]+w){
                    dis[v]=dis[u]+w;
                    cnt[v]=cnt[u]+1;
                    if(cnt[v]>n)
                        return false;
                    if(!vis[v]){
                        q.push(v);
                        vis[v]=1;
                    }
                }
            }
        }
        return true;
    }
    node dat[maxn+100];
    int n,m;
    void build(int _n,int _m){
        n=_n;
        m=_m;
        for(int i=1;i<=m;i++){
            G[dat[i].u].push_back({dat[i].v,dat[i].w});
        }
        for(int i=1;i<=n;i++){
            G[0].push_back({i,0});
        }
    }
    void solve(){
        if(SPFA(0,n))
            for(int i=1;i<=n;i++){
                cout<<dis[i]<<" ";
            }
        else
            cout<<"NO";
        cout<<endl;
    }
};

字符串算法

KMP

int kmp[MAXN];
int la,lb,j;
char a[MAXN],b[MAXN];
int main() {
    cin>>a+1;
    cin>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for (int i=2; i<=lb; i++) {
        while(j&&b[i]!=b[j+1])
            j=kmp[j];
        if(b[j+1]==b[i])j++;
        kmp[i]=j;
    }
    j=0;
    for(int i=1; i<=la; i++) {
        while(j>0&&b[j+1]!=a[i])
            j=kmp[j];
        if (b[j+1]==a[i])
            j++;
        if (j==lb) {
            cout<<i-lb+1<<endl;
            j=kmp[j];
        }
    }
    for (int i=1; i<=lb; i++)
        cout<<kmp[i]<<" ";
    return 0;
}

字典树

class Trie{
    int cnt;
    int nxt[maxn][75];
    int flag[maxn];
public:
    void init(){
        for(int i=0;i<=cnt;i++){
            flag[i]=0;
            for(int j=0;j<=74;j++)
                nxt[i][j]=0;
        }
        cnt=0;
    }
    void insert(char* s){
        int n=strlen(s);
        int p=0;
        flag[p]++;
        for(int i=0;i<n;i++){
            if(!nxt[p][s[i]-'0']){
                nxt[p][s[i]-'0']=(++cnt);
            }
            p=nxt[p][s[i]-'0'];
            flag[p]++;
        }
    }
    int find(char* s){
        int n=strlen(s);
        int p=0;
        for(int i=0;i<n;i++){
            if(!nxt[p][s[i]-'0']){
                return 0;
            }
            p=nxt[p][s[i]-'0'];
        }
        return flag[p];
    }
};

字符串哈希

#define ull unsigned long long
#define base 500
ull hush(string s){
    ull ans=0;
    for(int i=0;i<s.size();i++){
        ans=ans*base+s[i];
    }
    return ans;
}

Manacher

s[0]='|'
len=strlen(ch);
tot=0;
for (int i=0; i<len; i++)
    s[++tot]='|',s[++tot]=ch[i];
s[++tot]='|';
s[++tot]=21;
mr=pos=ml=0;
for (int i=1; i<tot; i++) {
   if (i<mr) p[i]=min(p[pos*2-i],mr-i);
   else p[i]=1;
    while (s[i+p[i]]==s[i-p[i]]) p[i]++;
    if (i+p[i]>mr)  mr=i+p[i],pos=i;
    ml=max(ml,p[i]-1);
}
printf("%d\n",ml);

动态规划

最长公共子序列

int n,len;
int a[100001];
int b[100001];
int id[100001];
int dp[100001];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        id[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        b[i]=id[b[i]];
    }
    for(int i=1;i<=n;i++)
        if(b[i]>dp[len])
            dp[++len]=b[i];
        else
            *lower_bound(dp+1,dp+len+1,b[i])=b[i];
    cout<<len<<endl;
    return 0;
}

数据结构

并查集

void init(){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}
int find(int x){
    if(fa[x]!=x)
        fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int x,int y){
    int fx=find(x);
    int fy=find(y);
    fa[fx]=fy;
}

线段树

struct Segmenttree{
    struct node{
        int v,l,r,tag;
    };
    node t[4*100001];
    int dat[4*100001];
    void build(int x,int l,int r){
        t[x].l=l;
        t[x].r=r;
        if(l==r){
            t[x].v=dat[l];
            return;
        }
        int mid=(l+r)/2;
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
        t[x].v=t[x*2].v+t[x*2+1].v;
    }
    void apply(int x,int v){
        t[x].v+=v*(t[x].r-t[x].l+1);
        t[x].tag+=v;
    }
    void pushdown(int x){
        if(t[x].tag&&t[x].r-t[x].l){
            apply(x*2,t[x].tag);
            apply(x*2+1,t[x].tag);
            t[x].tag=0;
        }
    }
    void update(int x,int L,int R,int v){
        int l=t[x].l;
        int r=t[x].r;
        if(L<=l&&r<=R){
            apply(x,v);
            return;
        }
        pushdown(x);
        int mid=(l+r)/2;
        if(L<=mid){
            update(x*2,L,R,v);
        }
        if(mid<R){
            update(x*2+1,L,R,v);
        }
        t[x].v=t[x*2].v+t[x*2+1].v;
    }
    int query(int x,int L,int R){
        int l=t[x].l;
        int r=t[x].r;
        if(L<=l&&r<=R){
            return t[x].v;
        }
        pushdown(x);
        int mid=(l+r)/2;
        int tot=0;
        if(L<=mid){
            tot+=query(x*2,L,R);
        }
        if(mid<R){
            tot+=query(x*2+1,L,R);
        }
        return tot;
    }
    void update(int x,int X,int v){
        update(x,X,X,v);
    }
    int query(int x,int X){
        return query(x,X,X);
    }
}SegTree;

可持久化线段树（单点）

template <typename T> struct PSegmentTree{
    struct node{
        int l,r,ls,rs;
        T v;
    }t[1000006*24];
    T dat[1000006];
    int root[10000006],tot;
    int _build(int l,int r){
        int x=tot++;
        t[x].l=l,t[x].r=r;
        if(l==r){
            t[x].v=dat[l];
            return x;
        }
        int mid=(l+r)/2;
        t[x].ls=_build(l,mid);
        t[x].rs=_build(mid+1,r);
        return x;
    }
    int _update(int x,int X,T v){
        int nx=tot++;
        t[nx]=t[x];
        int l=t[x].l,r=t[x].r;
        if(l==r){
            t[nx].v=v;
            return nx;
        }
        int mid=(l+r)/2;
        if(X<=mid)t[nx].ls=_update(t[nx].ls,X,v);
        else t[nx].rs=_update(t[nx].rs,X,v);
        return nx;
    }
    T _query(int x,int X){
        int l=t[x].l,r=t[x].r;
        if(l==r){
            return t[x].v;
        }
        int mid=(l+r)/2;
        if(X<=mid)return _query(t[x].ls,X);
        else return _query(t[x].rs,X);
    }
    void build(int n){
        root[0]=_build(1,n);
    }
    void update(int now,int var,int x,int v){
        root[now]=_update(root[var],x,v);
    }
    T query(int now,int var,int x){
        root[now]=root[var];
        return _query(root[var],x);
    }
};
PSegmentTree<int>pst;

树状数组

struct BIT{
    int a[600001];
    int max_size;
    int lowbit(int x){
        return x&-x;
    }
    void update(int x,int v){
        for(int i=x;i<=max_size;i+=lowbit(i)){
            a[i]+=v;
        }
    }
    int query(int r){
        int tot=0;
        for(int i=r;i>=1;i-=lowbit(i)){
            tot+=a[i];
        }
        return tot;
    }
    int query(int l,int r){
        return query(r)-query(l-1);
    }
}T;

扫描线

int n,m;
struct nn{
    int x,yy1,yy2,f;
}Q[20500000];
int st[20500000];
bool cmp1(nn a,nn b){
    return a.x<b.x;
}
struct node{
    int l,r;
    int m,ans;
}e[80500000];
void Build(int l,int r,int idd){
    e[idd].l=l;
    e[idd].r=r;
    if(l==r) return;
    int m=(l+r)/2;
    Build(l,m,idd*2);
    Build(m+1,r,idd*2+1);
}
void Up(int idd){
    if(e[idd].m>0){
        e[idd].ans=st[e[idd].r+1]-st[e[idd].l];
    }
    else{
        e[idd].ans=e[idd*2].ans+e[idd*2+1].ans;
    }
}
void Update(int l,int r,int idd,int f){
    if(l<=e[idd].l && e[idd].r<=r){
        e[idd].m+=f;
        Up(idd);
        return ;
    }
    int m=(e[idd].l + e[idd].r)/2;
    if(l<=m)
        Update(l,r,idd*2,f);
    if(r>m)
        Update(l,r,idd*2+1,f);
    Up(idd);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        Q[i]={a,b,d,1};
        Q[i+n]={c,b,d,-1};
        st[i]=b;st[i+n]=d;
    }
    sort(st+1,st+1+2*n);
    int c=2;
    for(int i=2;i<=2*n;i++){
        if(st[i-1]!=st[i]){
            st[c]=st[i];
            c++;
        }
    }
    for(int i=1;i<=2*n;i++){
        Q[i].yy1=lower_bound(st+1,st+c,Q[i].yy1)-st;
        Q[i].yy2=lower_bound(st+1,st+c,Q[i].yy2)-st;
    }
    sort(Q+1,Q+1+2*n,cmp1);
    Build(1,c-1,1);
    long long ans=0;
    for(int i=1;i<2*n;i++){
        Update(Q[i].yy1,Q[i].yy2-1,1,Q[i].f);
        ans+=1LL*(Q[i+1].x-Q[i].x)*e[1].ans;
    }
    printf("%lld\n",ans);
} 

计算几何

二维凸包

struct Point{
    double x,y;
};
typedef Point Vector;
bool cmp(Point _1,Point _2){
    if(_1.x!=_2.x)
        return _1.x<_2.x;
    return _1.y<_2.y;
}
Vector operator - (Point _1,Point _2){
    return {_1.x-_2.x,_1.y-_2.y};
}
double operator * (Vector _1,Vector _2){
    return _1.x*_2.y-_1.y*_2.x;
}
double operator + (Point _1,Point _2){
    return sqrt((_1.x-_2.x)*(_1.x-_2.x)+(_1.y-_2.y)*(_1.y-_2.y));
}
int n;
Point a[100001];
struct Stack{
    Point s[100001];
    int tot;
    void push(Point x){s[++tot]=x;}
    Point top(){return s[tot];}
    void pop(){tot--;}
    bool empty(){return tot==0;}
};
Stack s;
bool ok(int i){
    Vector v1=s.s[s.tot-1]-s.s[s.tot];
    Vector v2=s.s[s.tot-1]-a[i];
    return v1*v2>0;
}
double ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        while(s.tot>1&&!ok(i))
            s.pop();
        s.push(a[i]);
    }
    int tmp=s.tot;
    //cout<<tmp<<endl;
    for(int i=n-1;i>=1;i--){
        while(s.tot>tmp&&!ok(i))
            s.pop();
        s.push(a[i]);
    }
    //cout<<s.tot<<endl;
    Point lst=s.top();
    //cout<<lst.x<<","<<lst.y<<endl;
    s.pop();
    while(!s.empty()){
        Point now=s.top();
        //cout<<now.x<<","<<now.y<<endl;
        s.pop();
        ans+=now+lst;
        lst=now;
    }
    printf("%.2lf\n",ans);
    return 0;
}