板子哲学康复练习

#include<bits;/stdc++.h>
#define rg register int
#define il inline
il int Min(int x,int y){ return x<y?x:y; }
il int Max(int x,int y){ return x<y?y:x; }
il int Abs(int x,int y){ return x<0?-x:x; }
il int read(){
    char c=getchar();int f=1,x=0;
    while(c<48){ if(c=='-')f=-1;c=getchar(); }
    while(c>47){ x=(x<<3)+(x<<1)+(c^48);c=getchar(); }
    return x*f;
}

int n,m,a[maxn];
int dfn[maxn],
int head[maxn<<1],t;
struct Edge{ int v,w;int next; };Edge e[maxn<<1];
il void add_edge(int u,int v,int w){ e[++t].v=v;e[t].w=w;e[t].next=head[u];head[u]=t; }

void tarjan(int now){
    dfn[now]=low[now]=++cnt;
    for(rg i=head[now];i;i=e[i].next){
        int to=e[i].v;
        if(!dfn[to]){
            tarjan(to);
            low[now]=Min(low[now],low[to]);
        }
        else if(vis[to])    low[now]=Min(low[now],dfn[to]);
    }
    if(dfn[now]==low[now]){
        int cur;++id;
        do{
            cur=stk[top--];vis[cur]=false;
            scc[cur]=id;++siz[id];
        }while(cur!=now);
    }
}

il void input(){
    n=read(),m=read();int u,v,w;
    for(rg i=1;i<=n;++i)    a[i]=read();
    for(rg i=1;i<=m;++i)    u=read(),v=read(),w=read(),add_edge(u,v,w);
}

int main(){
    input();
    for(rg i=1;i<=n;++i)    if(!dfn[i]) tarjan(i);
    return 0;
}

#include<bits/stdc++.h>
#define rg register int
#define il inline
#define cerr std::cerr
#define endl '\n'
il int Max(int x,int y){ return x<y?y:x; }
il int Min(int x,int y){ return x<y?x:y; }
il int Abs(int x){ return x<0?-x:x; }
il int read(){
    char c=getchar();int x=0,f=1;
    while(c<48){ if(c=='-')f=-1;c=getchar(); }
    while(c>47){ x=(x<<3)+(x<<1)+(c^48);c=getchar(); }
    return x*f;
}const int maxn=2e5+5,inf=0x3f3f3f3f;

int n,m,minn,id,a[maxn],dfn[maxn],low[maxn],tot,stk[maxn],top;
bool invis[maxn];
int head[maxn<<1],t;
struct Edge{ int v;int next; };Edge e[maxn<<1];
il void add_edge(int u,int v){ e[++t].v=v;e[t].next=head[u];head[u]=t; }

void tarjan(int now){
    dfn[now]=low[now]=++tot;
    stk[++top]=now;invis[now]=true;
    for(rg i=head[now];i;i=e[i].next){
        int to=e[i].v;
        if(!dfn[to]){
            tarjan(to);
            low[now]=Min(low[now],low[to]);
        }
        else if(invis[to]) low[now]=Min(low[now],dfn[to]);
    }
    if(dfn[now]==low[now]){
        int cur=stk[top],count_=0;
        while(cur!=now){
            ++count_;invis[cur]=false;
            --top;cur=stk[top];
        }
        ++count_;
        invis[cur]=false;--top;
        if(count_>1)    minn=Min(minn,count_);
    }
}

il void input(){
    n=read();int v;
    for(rg i=1;i<=n;++i)    v=read(),add_edge(i,v);
}

int main(){
// freopen("tarjan.in","r",stdin);
    input();minn=inf;
    for(rg i=1;i<=n;++i)    if(!dfn[i]) tarjan(i);
    printf("%d\n",minn);
    return 0;
}

#include<bits/stdc++.h>
#define il inline
#define rg register int
#define cerr std::cerr
#define endl '\n'
il int Max(int x,int y){ return x<y?y:x; }
il int Min(int x,int y){ return x<y?x:y; }
il int Abs(int x){ return x<0?-x:x; }
il int read(){
    char c=getchar();int x=0,f=1;
    while(c<48){ if(c=='-')f=-1;c=getchar(); }
    while(c>47){ x=(x<<3)+(x<<1)+(c^48);c=getchar(); }
    return x*f;
}const int maxn=5e5+5;

int n,q,max[maxn][20],min[maxn][20];

int query_max(int l,int r){
    int k=log2(r-l+1);
    return Max(max[l][k],max[r-(1<<k)+1][k]);
}

int query_min(int l,int r){
    int k=log2(r-l+1);
    return Min(min[l][k],min[r-(1<<k)+1][k]);
}

il void input(){
    n=read(),q=read();
    for(rg i=1;i<=n;++i)    max[i][0]=min[i][0]=read();
    for(rg j=1;j<19;++j)
        for(rg i=1;i+(1<<j)-1<=n;++i){
            max[i][j]=Max(max[i][j-1],max[i+(1<<(j-1))][j-1]);
            min[i][j]=Min(min[i][j-1],min[i+(1<<(j-1))][j-1]);
        }
}

int main(){
    input();
    return 0;
}