以 P10304 为例，记录一下 MatrixGroup 的当前码风

· · 个人记录 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,del##i##verme=int(n);i<del##i##verme;++i)
#define rep1(i,n) for(int i=1,parano##i##a=int(n);i<=parano##i##a;++i)
#define per(i,n) for(int i=int(n)-1;i>=0;--i)
#define per1(i,n) for(int i=int(n);i>=1;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define y0 LingLuo
#define y1 VividCycle
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using namespace std;
const ll mod1=998244353;
const ll mod2=1000000007;
unsigned time_related_rand()
{
    return unsigned(std::chrono::steady_clock::now().time_since_epoch().count());
}
int n,m,q,u,v;
struct dsu{
    int p[100005];
    void init(int N)
    {
        rep1(i,N) p[i]=i;
    }
    int getp(int x)
    {
        return (p[x]==x)?x:(p[x]=getp(p[x]));
    }
    void merge(int x,int y)
    {
        p[getp(x)]=getp(y);
    }
};
struct fenwick{
    int s[100005];
    void add(int x,int val)
    {
        while(x<=n)
        {
            s[x]+=val;
            x+=x&-x;
        }
    }
    int query(int x)
    {
        int r=0;
        while(x)
        {
            r+=s[x];
            x&=x-1;
        }
        return r;
    }
};
dsu D;
fenwick tree;
vector<int> to[100005],tre[100005],fr[100005];int deg[100005];
int dep[100005],par[18][100005];
int c[100005];
int f[100005][18];
bool vis[100005];
int bg[100005],ed[100005],toki;
vector<pair<int,int> > query[100005];
queue<int> Q;
vector<int> id[100005];
int answer[100005];
void dfs(int ver)
{
    vis[ver]=true;bg[ver]=++toki;
    for(int x:to[ver])
    {
        ++deg[x];
        if(!vis[x])
        {
            dep[x]=dep[ver]+1;dfs(x);tre[ver].pb(x);par[0][x]=ver;
        }
        else
        {
            fr[x].pb(ver);
        }
    }
    ed[ver]=toki;
}
int value(int x,int y)
{
    int vv=0x3f3f3f3f;
    if(dep[x]>=dep[y])
    {
        int d=dep[x]-dep[y];
        rep(i,18) if((d>>i)&1) x=par[i][x];
    }
    else
    {
        int d=dep[y]-dep[x];
        rep(i,18) if((d>>i)&1) {vv=min(vv,f[y][i]);y=par[i][y];}
    }
    if(x==y) return min(vv,c[y]);
    per(i,18) if(par[i][x]!=par[i][y])
    {
        x=par[i][x];vv=min(vv,f[y][i]);y=par[i][y];
    }
    return min(vv,f[y][1]);
}
void link(int x,int y)
{
    int val=tree.query(ed[y])-tree.query(bg[y]-1);
    D.merge(y,x);
    tree.add(bg[x],val);
    if(D.getp(x)!=1)
    tree.add(bg[par[0][D.getp(x)]],-val);
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m>>q;
    rep1(i,m)
    {
        cin>>u>>v;to[u].pb(v);
    }
    rep1(i,n) sort(to[i].begin(),to[i].end());
    dfs(1);
    rep1(i,17)
    {
        rep1(j,n) par[i][j]=par[i-1][par[i-1][j]]; 
    }
    rep1(i,n) if(deg[i]==0) Q.push(i);
    rep(i,18) f[0][i]=0x3f3f3f3f;
    while(!Q.empty())
    {
        int x=Q.front();Q.pop();
        c[x]=dep[x];
        for(int y:fr[x])
        {
            c[x]=min(c[x],value(x,y));
        }
        for(int y:to[x])
        {
            if((--deg[y])==0) Q.push(y);
        }
        f[x][0]=c[x];
        rep1(i,17)
        {
            f[x][i]=min(f[x][i-1],f[par[i-1][x]][i-1]);
        }
        id[c[x]].pb(x);
    }
    rep1(i,q)
    {
        cin>>u>>v;query[dep[u]].pb(mp(v,i));
    }
    rep1(i,n) vis[i]=false;
    D.init(n);
    per(i,n)
    {
        for(pair<int,int> P:query[i])
        {
            answer[P.se]=tree.query(ed[P.fi])-tree.query(bg[P.fi]-1);
        }
        for(int ver:id[i])
        {
            tree.add(bg[ver],1);
            if(ver!=1) tree.add(bg[par[0][ver]],-1); 
            vis[ver]=true;
            for(int chd:tre[ver])
            {
                if(vis[chd]) link(ver,chd);
            }
            if(vis[par[0][ver]]) link(par[0][ver],ver);
        }
    }
    rep1(i,q) cout<<answer[i]<<'\n';
    return 0;
}
/* things to check
1.  int overflow or long long memory need
2.  recursion/array/binary search/dp/loop bounds
3.  precision
4.  special cases(n=1,bounds)
5.  delete debug statements
6.  initialize(especially multi-tests)
7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
8.  keep it simple and stupid
9.  do not delete, use // instead
10. operator priority
11. is there anything extra to output?
12. ...
*/

/* something to think about
1. greedy? dp? searching? dp with matrix/ segment tree? binary search?
2. If contains "not", why not ?????? or few affect?
*/

这里给出一点解释：