各种模板

zhou888
关注文章
TinyMind专栏频道

各种模板

lct

#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
    int x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c<'0' || c>'9'));
    if(c=='-') c=getchar(),f=-1;
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
    return x*f;
}
inline ll readll(){
    ll x;
    char c;
    ll f=1;
    while((c=getchar())!='-' && (c<'0' || c>'9'));
    if(c=='-') c=getchar(),f=-1;
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
    return x*f;
}
const int maxn=3e5+10;
#define ls(x) (ch[x][0])
#define rs(x) (ch[x][1])
#define isr(x) (rs(fa[x])==x)
int stk[maxn],Top;
struct Link_cut_tree{
    int sum[maxn],ch[maxn][2],fa[maxn],rev[maxn],val[maxn];
    inline bool isroot(int x){
        return rs(fa[x])!=x && ls(fa[x])!=x;
    }
    inline void push_up(int x){
        sum[x]=sum[ls(x)]^sum[rs(x)]^val[x];
    }
    inline void push_down(int x){
        if(rev[x]){
            int l=ls(x),r=rs(x);
            if(l) swap(ch[l][0],ch[l][1]),rev[l]^=1;
            if(r) swap(ch[r][0],ch[r][1]),rev[r]^=1;
            rev[x]=0;
        }
    }
    inline void rotate(int x){
        int f=fa[x],ff=fa[f],u=isr(x);
        ch[fa[ch[x][u^1]]=f][u]=ch[x][u^1];
        fa[x]=ff;if(!isroot(f)) ch[ff][isr(f)]=x;
        ch[fa[f]=x][u^1]=f;
        push_up(f);
    }
    inline void splay(int x){
        stk[Top=1]=x;
        for(int i=x;!isroot(i);i=fa[i]) stk[++Top]=fa[i];
        DREP(i,Top,1) push_down(stk[i]);
        for(;!isroot(x);rotate(x))
            if(!isroot(fa[x])) rotate((isr(fa[x])^isr(x))?x:fa[x]);
        push_up(x);
    }
    inline void access(int x){
        for(int i=0;x;x=fa[i=x]) splay(x),ch[x][1]=i,push_up(x);
    }
    inline void makeroot(int x){
        access(x),splay(x),rev[x]^=1,swap(ch[x][0],ch[x][1]);
    }
    inline int findroot(int x){
        access(x),splay(x);
        while(ch[x][0]) push_down(x),x=ch[x][0];
        splay(x);return x;
    }
    inline void split(int x,int y){
        makeroot(x),access(y),splay(y);
    }
    inline bool link(int x,int y){
        makeroot(x);
        if(findroot(y)==x) return 0;
        fa[x]=y;return 1;
    }
    inline void cut(int x,int y){
        split(x,y);
        if(ch[y][0]==x)  fa[x]=ch[y][0]=0;
        push_up(y);
    }
}lct;
int main(){
#ifndef ONLINE_JUDGE
    freopen("lct.in","r",stdin);
    freopen("lct.out","w",stdout);
#endif
    int n=read(),q=read();
    REP(i,1,n) lct.val[i]=lct.sum[i]=read();
    while(q--){
        int ty=read(),x=read(),y=read();
        if(ty==0) lct.split(x,y),printf("%d\n",lct.sum[y]);
        else if(ty==1) lct.link(x,y);
        else if(ty==2) lct.cut(x,y);
        else lct.access(x),lct.splay(x),lct.val[x]=y,lct.push_up(x);
    }
    return 0;
}

替罪羊

#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
    int x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
    return x*f;
}
inline ll readll(){
    ll x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
    return x*f;
}
#define ls(x) (ch[x][0])
#define rs(x) (ch[x][1])
#define isr(x) (x==rs(fa[x]))
const int maxn=1e5+10,inf=0x3f3f3f3f;
const double alpha=0.75;
inline bool chkmax(int &x,int y){return (y>x)?(x=y,1):0;}
inline bool chkmin(int &x,int y){return (y<x)?(x=y,1):0;}
struct TZY{
    int rt,cnt,tmp,num[maxn],sz[maxn],w[maxn],fa[maxn],ch[maxn][2];
    inline void push_up(int x){
        sz[x]=sz[ls(x)]+sz[rs(x)]+1;
    }
    inline bool check(int x){
        return alpha*sz[x]>=sz[ls(x)] && alpha*sz[x]>=sz[rs(x)];
    }
    void find_son(int x){
        if(!x) return;
        find_son(ls(x)),num[++tmp]=x,find_son(rs(x));
    }
    int build_tree(int L,int R){
        if(L>R) return 0;
        int Mid=(L+R)>>1,x;
        ch[num[Mid]][0]=ch[num[Mid]][1]=fa[num[Mid]]=0;
        if(x=build_tree(L,Mid-1)) fa[num[x]]=num[Mid],ch[num[Mid]][0]=num[x];
        if(x=build_tree(Mid+1,R)) fa[num[x]]=num[Mid],ch[num[Mid]][1]=num[x];
        push_up(num[Mid]);
//      cerr<<"UPDATE::"<<sz[num[Mid]]<<' '<<sz[ls(num[Mid])]<<' '<<sz[rs(num[Mid])]<<endl;
        return Mid;
    }
    void rebuild(int x){
        int f=fa[x],S=isr(x);
        tmp=0,find_son(x);
        int u=build_tree(1,tmp);
        u=num[u];
        if(rt==x) rt=u;
        else ch[fa[u]=f][S]=u;
    }
    void update(int x){
        int u=0;
        for(int i=x;i;i=fa[i]){
//          cout<<i<<endl;
            if(!check(i)) u=i;
        }
        if(u) rebuild(u);
    }
    void insert(int x){
        w[++cnt]=x,sz[cnt]=1;
        if(!rt) rt=cnt;
        else{
            int u=rt,lst;
            while(u){
                lst=u;sz[u]++;
                if(x>=w[u]) u=rs(u);
                else u=ls(u);
            }
//      cerr<<"INSERT::"<<sz[rt]<<' '<<sz[ls(rt)]<<' '<<sz[rs(rt)]<<endl;
            ch[lst][x>=w[lst]]=cnt,fa[cnt]=lst,update(cnt);
        }
//      cerr<<"INSERT!::"<<sz[rt]<<' '<<sz[ls(rt)]<<' '<<sz[rs(rt)]<<endl;
    }
    int find_id(int x){
        int u=rt;
        while(u){
            if(x==w[u]) return u;
            u=ch[u][x>w[u]];
        }
    }
    int find_rank(int x){
        int u=rt,sum=1;
        while(u){
            if(w[u]<x) sum+=sz[ls(u)]+1,u=rs(u);
            else u=ls(u);
        }
        return sum;
    }
    int find_kth(int x){
//      cerr<<"@#%##"<<endl;
        int u=rt;
        while(u){
//          cerr<<sz[u]<<' '<<sz[ls(u)]<<' '<<sz[rs(u)]<<endl;
            if(sz[ls(u)]+1==x) return w[u];
            if(sz[ls(u)]<x) x-=sz[ls(u)]+1,u=rs(u);
            else u=ls(u);
        }
    }
    int find_pre(int x){
        int u=rt,ans=-inf;
        while(u){
            if(w[u]<x) chkmax(ans,w[u]),u=rs(u);
            else u=ls(u);
        }
        return ans;
    }
    int find_next(int x){
        int u=rt,ans=inf;
//      cerr<<"!!!!"<<x<<endl;
        while(u){
//          cerr<<u<<' '<<w[u]<<endl;
            if(w[u]>x) chkmin(ans,w[u]),u=ls(u);
            else u=rs(u);
        }
        return ans;
    }
    int find_n(int x){
        x=rs(x);while(ls(x)) x=ls(x);
        return x;
    }
    void del(int x){
        x=find_id(x);
        int u;
        if(ls(x) && rs(x)){
            u=find_n(x);
            w[x]=w[u];x=u;
        }
        int S=ls(x)?ls(x):rs(x);
        ch[fa[S]=fa[x]][isr(x)]=S;
        for(int i=x;i;i=fa[i]) --sz[i];
        if(x==rt) rt=S;
    }
}T;
int main(){
#ifndef ONLINE_JUDGE
    freopen("tzy.in","r",stdin);
    freopen("tzy.out","w",stdout);
#endif
    int n=read();
    while(n--){
        int ty=read(),x=read();
        if(ty==1) T.insert(x);
        else if(ty==2) T.del(x);
        else if(ty==3) printf("%d\n",T.find_rank(x));
        else if(ty==4) printf("%d\n",T.find_kth(x));
        else if(ty==5) printf("%d\n",T.find_pre(x));
        else printf("%d\n",T.find_next(x));
    }
    return 0;
}

割顶和桥

#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
    int x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c<'0' || c>'9'));
    if(c=='-') c=getchar(),f=-1;
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
    return x*f;
}
inline ll readll(){
    ll x;
    char c;
    ll f=1;
    while((c=getchar())!='-' && (c<'0' || c>'9'));
    if(c=='-') c=getchar(),f=-1;
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
    return x*f;
}
const int maxn=1e5+10;
inline bool chkmin(int &x,int y){return (y<x)?(x=y,1):0;}
int Begin[maxn],Next[maxn<<1],to[maxn<<1],e;
int low[maxn],pre[maxn],dfs_clock;
int iscut[maxn];
vector<pair<int,int> > ve;
void add_edge(int x,int y){
    to[++e]=y;
    Next[e]=Begin[x];
    Begin[x]=e;
}
void tarjan(int x,int ff){
    int ch=0;
    pre[x]=low[x]=++dfs_clock;
    for(int i=Begin[x];i;i=Next[i]){
        if(to[i]==ff) continue;
        if(!pre[to[i]]){
            ++ch;
            tarjan(to[i],x);
            chkmin(low[x],low[to[i]]);
            if(low[to[i]]>=pre[x]) iscut[x]=1;
            if(low[to[i]]>pre[x]) ve.push_back(make_pair(x,to[i]));
        }
        else chkmin(low[x],pre[to[i]]);
    }
    if(!ff && ch==1) iscut[x]=0;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("tarjan.in","r",stdin);
    freopen("tarjan.out","w",stdout);
#endif
    int n=read(),m=read();
    REP(i,1,m){
        int x=read(),y=read();
        add_edge(x,y),add_edge(y,x);
    }
    REP(i,1,n) if(!pre[i]) tarjan(i,0);
    int ans=0;
    REP(i,1,n) if(iscut[i]) ++ans;
    printf("%d\n",ans);
    REP(i,1,n) if(iscut[i]) --ans,printf("%d%c",i,ans?' ':'\n');
    return 0;
}

bcc_点双

#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
    int x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c<'0' || c>'9'));
    if(c=='-') c=getchar(),f=-1;
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
    return x*f;
}
inline ll readll(){
    ll x;
    char c;
    ll f=1;
    while((c=getchar())!='-' && (c<'0' || c>'9'));
    if(c=='-') c=getchar(),f=-1;
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
    return x*f;
}
const int maxn=2e5+10;
inline bool chkmin(int &x,int y){return (y<x)?(x=y,1):0;}
int Begin[maxn],Next[maxn<<1],to[maxn<<1],e;
int pre[maxn],low[maxn],bccno[maxn],bcc_cnt;
int dfs_clock;
struct point{
    int x,y;
};
stack<point> S;
void add_edge(int x,int y){
    to[++e]=y;
    Next[e]=Begin[x];
    Begin[x]=e;
}
void tarjan(int x,int ff){
    pre[x]=low[x]=++dfs_clock;
    for(int i=Begin[x];i;i=Next[i]){
        if(to[i]==ff) continue;
        if(!pre[to[i]]){
            S.push((point){x,to[i]});
            tarjan(to[i],x);
            chkmin(low[x],low[to[i]]);
            if(low[to[i]]>=pre[x]){
                ++bcc_cnt;
                while(!S.empty()){
                    point u=S.top();S.pop();
                    bccno[u.x]=bccno[u.y]=bcc_cnt;
                    if(u.x==x && u.y==to[i]) break;
                }
            }
        }
        else if(pre[to[i]]<pre[x]){
            S.push((point){x,to[i]});
            chkmin(low[x],pre[to[i]]);
        }
    }
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("bcc.in","r",stdin);
    freopen("bcc.out","w",stdout);
#endif
    int n=read(),m=read();
    REP(i,1,m){
        int x=read(),y=read();
        add_edge(x,y),add_edge(y,x);
    }
    REP(i,1,n) if(!pre[i]) tarjan(i,0);
    printf("%d\n",bcc_cnt);
    REP(i,1,n) printf("%d\n",bccno[i]);
    return 0;
}

ecc_边双

#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
    int x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c<'0' || c>'9'));
    if(c=='-') c=getchar(),f=-1;
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
    return x*f;
}
inline ll readll(){
    ll x;
    char c;
    ll f=1;
    while((c=getchar())!='-' && (c<'0' || c>'9'));
    if(c=='-') c=getchar(),f=-1;
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
    return x*f;
}
const int maxn=2e5+10;
inline bool chkmin(int &x,int y){return (y<x)?(x=y,1):0;}
int Begin[maxn],Next[maxn<<1],to[maxn<<1],e;
int eccno[maxn],ecc_cnt,pre[maxn],low[maxn],dfs_clock;
bool bri[maxn<<1],p[maxn];
void add_edge(int x,int y){
    to[++e]=y;
    Next[e]=Begin[x];
    Begin[x]=e;
}
void tarjan(int x,int ff){
    pre[x]=low[x]=++dfs_clock;
    for(int i=Begin[x];i;i=Next[i]){
        if(to[i]==ff) continue;
        if(!pre[to[i]]){
            tarjan(to[i],x);
            chkmin(low[x],low[to[i]]);
            if(low[to[i]]>pre[x]) bri[i]=bri[i^1]=1;
        }
        else chkmin(low[x],pre[to[i]]);
    }
}
void findecc(int x){
    eccno[x]=ecc_cnt;p[x]=1;
    for(int i=Begin[x];i;i=Next[i]){
        if(p[to[i]] || bri[i]) continue;
        findecc(to[i]);
    }
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("ecc.in","r",stdin);
    freopen("ecc.out","w",stdout);
#endif
    int n=read(),m=read();
    e=1;
    REP(i,1,m){
        int x=read(),y=read();
        add_edge(x,y),add_edge(y,x);
    }
    REP(i,1,n) if(!pre[i]) tarjan(i,0);
    REP(i,1,n) if(!p[i]) ++ecc_cnt,findecc(i);
    printf("%d\n",ecc_cnt);
//  cerr<<1<<' '<<eccno[1]<<endl;
    REP(i,1,n) printf("%d%c",eccno[i],'\n');
    return 0;
}

支配树

#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
    int x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
    return x*f;
}
inline ll readll(){
    ll x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
    return x*f;
}
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
const int maxn=50000+10,maxm=1e5+10;
int Begin[maxn],Next[maxm],to[maxm],e;
int n,m,f[maxn],pre[maxn],sdom[maxn],idom[maxn];
int dfs_clock,p[maxn],ans[maxn];
vector<int> G[maxn],ve[maxn];
struct bcj{
    int fa[maxn],Max[maxn];
    void clear(){
        REP(i,1,n) fa[i]=Max[i]=i;
    }
    int find(int x){
        if(fa[x]==x) return x;
        int ff=find(fa[x]);
        if(sdom[Max[fa[x]]]<sdom[Max[x]]) Max[x]=Max[fa[x]];
        return fa[x]=ff;
    }
    int find_Max(int x){
        find(x);return Max[x];
    }
}T;
void add_edge(int x,int y){
    to[++e]=y;
    Next[e]=Begin[x];
    Begin[x]=e;
    G[y].push_back(x);
}
void dfs_init(int x){
    p[pre[x]=++dfs_clock]=x,sdom[x]=dfs_clock;
    for(int i=Begin[x];i;i=Next[i]) if(!pre[to[i]]) f[to[i]]=x,dfs_init(to[i]);
}
int solve(int x){
    if(ans[x]) return ans[x];
    return ans[x]=x+solve(idom[x]);
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
#endif
    while(scanf("%d%d",&n,&m)!=EOF){
        e=dfs_clock=0;T.clear();
        REP(i,1,n) G[i].clear(),Begin[i]=ans[i]=pre[i]=sdom[i]=idom[i]=f[i]=p[i]=0;
        REP(i,1,m){
            int x=read(),y=read();
            add_edge(x,y);
        }
        dfs_init(n);
        DREP(i,dfs_clock,2){
            int u=p[i];
            REP(j,0,G[u].size()-1) if(pre[G[u][j]]) chkmin(sdom[u],sdom[T.find_Max(G[u][j])]);
            ve[p[sdom[u]]].push_back(u);T.fa[u]=f[u];
            REP(j,0,ve[f[u]].size()-1){
                int x=T.find_Max(ve[f[u]][j]);
                if(sdom[x]==sdom[ve[f[u]][j]]) idom[ve[f[u]][j]]=f[u];
                else idom[ve[f[u]][j]]=x;
            }
            ve[f[u]].clear();
        }
        REP(i,2,dfs_clock) if(idom[p[i]]!=p[sdom[p[i]]]) idom[p[i]]=idom[idom[p[i]]];
        ans[n]=n;assert(p[1]==n);
        REP(i,1,n) printf("%d%c",pre[i]?solve(i):0,i==iend?'\n':' ');
    }
    return 0;
}
优质内容筛选与推荐>>
1、oracle提高查询效率的解析
2、轮播图片, 不用滚动视图, 也不用时间计时器
3、谋哥：玩App怎么赚钱（三）
4、Linux C 非阻塞Socket
5、entity framework 数据库库映射简单配置步骤


长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消，“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字，当前共字 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字，当前共字

    发送中

    网络异常，请稍后重试

    微信扫一扫
    关注该公众号

    0 │ 收藏 │ 举报