NaiveMartin's Blog

namespace bit{
    const int N=500000;
    int n,a[N+10];
    void add(int x,int d){for(;x<=n;x+=x&-x)a[x]+=d;}
    int sum(int x){int r=0;for(;x;x-=x&-x)r+=a[x];return r;}
}

namespace gae{
    const int N=1600,M=1600;
    int n,m,p[M+10];
    bitset<M+10>a[N+10];
    void run(){
        for(int i=1;i<=n;++i){
            int j=1;for(;j<=m&&!a[i][j];++j);
            if(j<=m){
                p[j]=i;
                for(int k=1;k<=n;++k)if(k!=i&&a[k][j])
                    a[k]^=a[i];
            }
        }
    }
}

namespace sam{
    const int N=100000,L=26;
    int pr[N*2+10],ln[N*2+10],tr[N*2+10][L+10],nw;
    int make(){++nw;fill(tr[nw],tr[nw]+L,0);return nw;}
    void init(){nw=0;make();}
    int add(int c,int p){
        if(tr[p][c]){
            int q=tr[p][c];
            if(ln[q]==ln[p]+1)return q;
            else{
                int np=make();ln[np]=ln[p]+1;pr[np]=pr[q];
                copy(tr[q],tr[q]+L,tr[np]);pr[q]=np;
                for(;p&&tr[p][c]==q;p=pr[p])tr[p][c]=np;
                return np;
            }
        }else{
            int np=make();ln[np]=ln[p]+1;
            for(;p&&!tr[p][c];p=pr[p])tr[p][c]=np;
            if(!p)pr[np]=1;
            else{
                int q=tr[p][c];
                if(ln[q]==ln[p]+1)pr[np]=q;
                else{
                    int nq=make();ln[nq]=ln[p]+1;pr[nq]=pr[q];
                    copy(tr[q],tr[q]+L,tr[nq]);pr[q]=pr[np]=nq;
                    for(;p&&tr[p][c]==q;p=pr[p])tr[p][c]=nq;
                }
            }
            return np;
        }
    }
}

namespace tda{
    const int N=100000,L=17;
    vector<int>to[N+10],we[N+10];
    int up[N+10][L+10],dp[N+10];
    pair<int,int>mx[N+10][L+10];
    pair<int,int>merge(pair<int,int>x,pair<int,int>y){
        static int t[4];
        t[0]=x.first;t[1]=x.second;
        t[2]=y.first;t[3]=y.second;
        sort(t,t+4,greater<int>());
        unique(t,t+4);
        return make_pair(t[0],t[1]);
    }
    void add(int u,int v,int w){
        to[u].push_back(v);we[u].push_back(w);
        to[v].push_back(u);we[v].push_back(w);
    }
    void build(){
        static int vis[N+10];
        queue<int>qu;qu.push(1);vis[1]=1;
        while(!qu.empty()){
            int u=qu.front();qu.pop();
            for(int i=1;i<=L;++i){
                up[u][i]=up[up[u][i-1]][i-1];
                mx[u][i]=merge(mx[u][i-1],mx[up[u][i-1]][i-1]);
            }
            for(int i=0;i<to[u].size();++i){
                int v=to[u][i],w=we[u][i];
                if(!vis[v]){
                    vis[v]=1;up[v][0]=u;
                    mx[v][0]=make_pair(w,-(~0u>>1));
                    dp[v]=dp[u]+1;qu.push(v);
                }
            }
        }
    }
    pair<int,int>query(int u,int v){
        pair<int,int>ans(-(~0u>>1),-(~0u>>1)); 
        if(dp[u]<dp[v])swap(u,v);
        for(int i=0;i<=L;++i)
            if(((dp[u]-dp[v])>>i)&1){
                ans=merge(ans,mx[u][i]);
                u=up[u][i];
            }
        if(u==v)return ans;
        for(int i=L;i>=0;--i)
            if(up[u][i]!=up[v][i]){
                ans=merge(ans,mx[u][i]);
                ans=merge(ans,mx[v][i]);
                u=up[u][i];
                v=up[v][i];
            }
        ans=merge(ans,mx[u][0]);
        ans=merge(ans,mx[v][0]);
        return ans;
    }
}

namespace trp{
    struct node{
        node():s(1),w(rand()){ch[0]=ch[1]=0;}
        node*ch[2];
        int s,w;
    };
    void update(node*u){
        u->s=1;
        if(u->ch[0])u->s+=u->ch[0]->s;
        if(u->ch[1])u->s+=u->ch[1]->s;
    }
    void down(node*u){} 
    node*merge(node*u,node*v){
        if(!u)return v;
        if(!v)return u;
        if(u->w<v->w){
            down(u);
            u->ch[1]=merge(u->ch[1],v);
            update(u);
            return u;
        }else{
            down(v);
            v->ch[0]=merge(u,v->ch[0]);
            update(v);
            return v;
        }
    }
    pair<node*,node*>split(node*u,int k){
		if(!u)return make_pair((node*)0,(node*)0);
		down(u);
		int t=(u->ch[0]?u->ch[0]->s:0)+1;
		if(k<t){
            pair<node*,node*>r=split(u->ch[0],k);
			u->ch[0]=r.second;
			update(u);
			return make_pair(r.first,u);
		}else{
			pair<node*,node*>r=split(u->ch[1],k-t);
			u->ch[1]=r.first;
			update(u);
			return make_pair(u,r.second);
		}
	}
};

namespace ufs{
    const int N=1000;
    int n,pr[N+10];
    void build(){for(int i=1;i<=n;++i)pr[i]=i;}
    int find(int u){return u==pr[u]?u:pr[u]=find(pr[u]);}
    void link(int u,int v){pr[find(u)]=v;}
}

namespace kmp{
    const int AL=1000000,BL=1000000;
    char a[AL+10],b[BL+10];
    int pr[BL+10],al,bl;
    void build(){
        for(int i=2,j=0;i<=bl;++i){
            while(j>0&&b[j+1]!=b[i])j=pr[j];
            if(b[j+1]==b[i])++j;
            pr[i]=j;
        }
    }
    int run(){
        int r=0;
        for(int i=1,j=0;i<=al;++i){
            while(j>0&&a[i]!=b[j+1])j=pr[j];
            if(a[i]==b[j+1])++j;
            if(j==bl)++r,j=pr[j];
        }
        return r;
    }
}

namespace acm{
    const int L=2000,M=10;const char W='0';
    int ch[L+10][M+10],fa[L+10],tg[L+10],nw=1;
    void insert(char*s){
        int u=1;for(;*s;++s){
            if(!ch[u][*s-W])ch[u][*s-W]=++nw;
            u=ch[u][*s-W];
        }
        ++tg[u];
    }
    void build(){
        queue<int>qu;
        for(int i=0;i<M;++i)
            if(!ch[1][i])ch[1][i]=1;
            else fa[ch[1][i]]=1,qu.push(ch[1][i]);
        while(!qu.empty()){
            int u=qu.front();qu.pop();
            for(int i=0;i<M;++i)
                if(!ch[u][i])ch[u][i]=ch[fa[u]][i];
                else fa[ch[u][i]]=ch[fa[u]][i],qu.push(ch[u][i]);
        }
    }
}

namespace fft{
    typedef complex<double>cpx;
    double pi=acos(-1.0);cpx im(0,1);
    void run(cpx*a,int n,int s){
        for(int i=0;i<n;++i){
            int j=0;for(int k=0;(1<<k)<n;++k)j<<=1,j+=((i>>k)&1);
            if(i<j)swap(a[i],a[j]);
        }
        for(int i=1;(1<<i)<=n;++i){
            int m=(1<<i);cpx wm=exp(double(s)*im*2.0*pi/double(m));
            for(int j=0;j<n;j+=m){
                cpx w=1;
                for(int k=0;k<m/2;++k){
                    cpx u=a[j+k],v=w*a[j+k+m/2];
                    a[j+k]=u+v;a[j+k+m/2]=u-v;w*=wm;
                }
            }
        }
    }
}