DSU#

#include<numeric>

struct DSU{
    vector<int>fa, sz;
    DSU(int n) : fa(n + 1),sz(n+1, 1){
        iota(fa.begin(), fa.end(), 0);
    }

    int find(int x){
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }

    bool same(int x,int y){
        return find(x) == find(y);
    }

    bool merge(int x,int y){
        x = find(x),y = find(y);
        if(x == y) return false;
        if(sz[x] <  sz[y]) swap(x, y);
        sz[x] += sz[y]; fa[y] = x;
        return true;
    }

    int size(int x){return sz[find(x)]; }
};

带权DSU#

• 强制在线

• 1 l r x 代表 $a_{l} - a_{r} = x$ ，若矛盾则忽略。

• 2 l r 代表回答 $a_{l} - a_{r}$ ,如果推不出则忽略。

  我们记向量 $vec_{x} = a_{x} - a_{f[ x ]}$

  当已知 $vec_{x} = a_{x} - a_{y}$ 和 $vec_{y} = a_{y} - a_{z}$ 时，

  我们求 x 到 z 的向量时，可以通过 $vec_{x} + vec_{y}$ 来计算

  递归压缩了父节点，得到已知信息 $vec_{par[x]}$ 为 $a_{par[x]} - a_{root}$

  那么节点 x 到 root 的关系就可以使用向量加法法则 $vec_{ x } + vec_{par[x]}$ 得到

  而合并的时候，只需要更新一组各自根节点root 的差值即可。

int find(int x){
    if(f[x] == x) return x; 
    int p = f[x]; 
    find(p);

    w[x] = w[x] + w[p];
    return f[x] = find(f[x]);
}

void solve(){
    int n,q;
    cin >> n >> q;

    for(int i = 1;i <= n;i ++){
        f[i] = i;
        w[i] = 0;
    }
    int t = 0;
    for(int i = 0;i < q;i ++){
        int ty, l, r;
        cin >> ty >> l >> r;
        l = (l + t) % n + 1;
        r = (r + t) % n + 1;
        if(ty == 2){
            if(find(l) != find(r)) continue;
            cout << w[l] - w[r] << endl;
            t = abs(w[l] - w[r]);
        }else if(ty == 1){
            int x;
            cin >> x;
            if(find(l) == find(r)) continue;
             w[f[l]] = x - w[l] + w[r];
             f[f[l]] = f[r];
        }
    }
}

树状数组#

template <typename T>
struct Fenwick {
    int n;
    vector<T> a;
     
    Fenwick(int n = 0) {
        init(n);
    }
     
    void init(int n) {
        this->n = n;
        a.assign(n, T());
    }
     
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
     
    T sum(int x) {
        auto ans = T();
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
     
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
     
    int kth(T k) {
        int x = 0;
        for (int i = 1 << __lg(n); i; i /= 2) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};
 
struct Info {
    int x = -1E9;
    Info &operator+=(Info b) & {
        x = std::max(x, b.x);
        return *this;
    }
};

树状数组区间加和#

const int N = 1e6 + 100;

template<class T>
struct BIT {
    T c[N];
    int size;
    void resize(int s) {
        size = s;
    }

    T query(int x) {
        assert(x <= size);
        T res = 0;

        for (; x; x -= x & -x) {
            res += c[x];
        }

        return res;
    }

    void modify(int x, T val) {
        assert(x != 0);

        for (; x <= size; x += x & -x)
            c[x] += val;
    }
};

BIT<int> c1, c2;

int n, q;

void add(int l, int r, int d) {
    c1.modify(l, d);
    c1.modify(r + 1, -d);
    c2.modify(l, l * d);
    c2.modify(r + 1, (r + 1) * (-d));
}

void solve() {
    cin >> n >> q;
    c1.resize(n);
    c2.resize(n);

    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        add(i, i, x);
    }

    for (int i = 0; i < q; i ++) {
        int ty;
        cin >> ty;

        if (ty == 1) {
            int l, r;
            int d;
            cin >> l >> r >> d;
            add(l, r, d);
        } else {
            int l, r;
            cin >> l >> r;
            //int res = (x + 1) * c1.query(x) - c2.query(x);
            //printf("%llu\n",res);
            int res = 0ll;
            res += (r + 1ll) * c1.query(r);
            res -= 1ll * l * c1.query(l - 1);
            res -= (c2.query(r) - c2.query(l - 1));
            cout << res << endl;
        }
    }

}

高维树状数组#

int n,m;


struct BIT{

int tree[N][N];

void init()
{
    for(int i = 0;i <= 2049;i ++)
        for(int j = 0;j <= 2049;j ++)
            tree[i][j] = 0;
}

int query(int x,int y){
    int res = 0;
    for(int p = x;p >= 1; p -= p & (-p))
        for(int q = y;q >= 1; q -= q & (-q))
            res += tree[p][q];
    return res;
}

void modify(int x,int y,int s){
    for(int p = x;p <= n;p += (p & -p))
        for(int q = y;q <= m; q += (q & -q))
            tree[p][q] += s;
}
};


char op[5];


BIT A,Ai,Aj,Aij;

void add(int x,int y,int val)
{
   A.modify(x,y,val);
   Ai.modify(x,y,val * x);
   Aj.modify(x,y,val * y);
   Aij.modify(x,y,val * x * y);
}

int cacl(int x,int y)
{
    int res = 0;
    res += A.query(x,y) * (x * y + x + y + 1);
    res -= Ai.query(x,y) * (y + 1);
    res -= Aj.query(x,y) * (x + 1);
    res += Aij.query(x,y);
    return res;
}

void solve()
{
  scanf("X %d %d",&n,&m);

  A.init(); Ai.init();
  Aj.init(); Aij.init();

  while(scanf("%s",&op) != EOF)
  {
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    if(op[0] == 'L')
    {
        int val;
        scanf("%d",&val);
        add(x1,y1 ,val);
        add(x1,y2 + 1,-val);
        add(x2+1,y1,-val);
        add(x2+1,y2+1,val);
    }
    else{
        int res = 0;
        res += cacl(x2,y2);
        res -= cacl(x1 - 1,y2);
        res -= cacl(x2,y1 - 1);
        res += cacl(x1 - 1,y1 - 1);
        printf("%d\n",res);

    }
  }
}

二维数点#

$n$ 个点 $(x_{i},y_{i})$。 回答 $q$ 个询问, 回答$[x_{i},y_{i}] \times [x_{j},y_{j}]$ 里面有几个点。

const int N = 2e5 + 100;

vector<int> vx;
vector<array<int, 4>> event;
int n,q;
int m;

int c[N];
int res[N];

int query(int x)
{
    int s = 0;

    for(; x; x -= x & (-x)){
        s += c[x];
    }

    return s;
}

void modify(int x,int s){
    for(; x <= m; x += x & (-x)){
        c[x] += s;
    }
}

void solve()
{
    cin >> n >> q;
    rep(i,1,n){
        int x,y; cin >> x >> y;
        vx.pb(x);
        event.pb({y, 0, x});
    }

    rep(i,1,q){
        int x1, x2, y1, y2;
        cin >> x1 >> x2 >> y1 >> y2;
        event.pb({y2, 2,x2, i});
        event.pb({y1 - 1, 2, x1 - 1, i});
        event.pb({y2, 1, x1 - 1, i});
        event.pb({y1 - 1, 1, x2, i});
    }

    sort(event.begin(), event.end());
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    
    m = vx.size();
    for(auto evt : event)
    {
        if(evt[1] == 0)
        {
            int y = lower_bound(vx.begin(), vx.end(), evt[2]) - vx.begin() + 1; // 0 base
            modify(y,1);
        }
        else{
            int y = upper_bound(vx.begin(), vx.end(), evt[2]) - vx.begin() + 1 - 1; // 0 base
            int tmp = query(y);
            if(evt[1] == 1) res[evt[3]] -= tmp;
            else res[evt[3]] += tmp;
        }
    }

    rep(i,1,q) cout << res[i] << endl;

}

cdq 二维偏序#

int cdq(int A[], int n)
{
    if(n == 1) return 0;

    int mid = n/2; int i = 0; int j = mid;

    int res = cdq(A,mid) + cdq(A + mid,n - mid);
    
    sort(A, A + mid, greater<int>());
    sort(A + mid, A + n, greater<int>());

    for(;j < n;j ++)
    {
        while(i < mid && A[i] > A[j])
            i ++;
        res += i;
    }
    return res;
}

cdq 三维偏序#

const int N = 1e5 + 100;

struct node{
    int x,y,z;
    int ans,w;
}a[N], b[N];

int n,m;
int idx;

int res[N];

bool operator != (node &a, node &b)
{
    return a.x != b.x | a.y != b.y | a.z != b.z;
}

bool cmpx(node &a, node &b)
{
    if(a.x != b.x) return a.x < b.x;
    if(a.y != b.y) return a.y < b.y;
    return a.z < b.z;
}


bool cmpy(node &a, node &b)
{
    if(a.y != b.y) return a.y < b.y;
    return a.z < b.z;
}

struct BIT{
    int c[N * 2];

    int query(int x){
        int res = 0;
        for(; x; x -= (x & -x))
            res += c[x];
        return res;
    }

    void add(int x,int v)
    {
        for(; x <= m; x += (x & -x))
            c[x] += v;
    }

}bit;

void cdq(int l,int r)
{
    if(l == r) return;
    int mid = (l + r) >> 1;

    cdq(l, mid); cdq(mid + 1, r);

    sort(a + l,a + mid + 1, cmpy);
    sort(a + mid + 1,a + r + 1, cmpy);

    int i = l; int j = mid + 1;

    for(;j <= r;j ++){
        while(a[i].y <= a[j].y && i <= mid)
        {
           bit.add(a[i].z, a[i].w);
           i ++;
        }
        a[j].ans += bit.query(a[j].z);
    }

    for(j = l;j < i;j ++) bit.add(a[j].z , -a[j].w);

    
}


void solve()
{
    cin >> n >> m;
    rep(i,1,n) cin >> b[i].x >> b[i].y >> b[i].z;
    sort(b + 1,b + 1 + n,cmpx);
    idx = 0; int cnt = 0;
    for(int i = 1;i <= n;i ++){
        cnt ++;
        if(b[i] != b[i + 1]){
            a[ ++idx ] = b[i];
            a[ idx ].w = cnt;
            cnt = 0; 
        }
    }

    cdq(1, idx);

    rep(i,1,idx) res[a[i].ans + a[i].w - 1] += a[i].w;

    rep(i,0,n - 1) cout << res[i] << endl;
}

线段树 单点修改 区间查询#

单点修改，区间查询。维护区间最小值和最小值个数。

const int N = 2e5 + 100;

int n,q;

int a[N];

struct info {
    int minv, mincnt;
};

info operator + (const info &l, const info &r){
    info a;
    a.minv = min(l.minv, r.minv);
    if(l.minv == r.minv)
    {
        a.mincnt = l.mincnt + r.mincnt;
        return a;
    }

    a.mincnt = (l.minv < r.minv ? l.mincnt : r.mincnt);
    return a;
}

struct node{
    info val;
}seg[N * 4];


// son -> fa
void update(int u){
    seg[u].val = seg[u << 1].val + seg[u << 1 | 1].val;
}

void build(int u,int l,int r)
{
    if(l == r) seg[u].val = {a[l], 1};
    else{
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1,mid + 1, r);
        update(u);
        // 自下而上建树
    }
}


//  [u , l, r]
//  当前查询的区间编号为 u 他的管辖的位置参数为 l <= i <= r  
//  需要修改的位置编号为 pos 改为 val 单点修改
//  a[pos] -> v
//  自上而下搜索 pos 位置 自下而上 更新信息
void change(int u, int l, int r, int pos, int v)
{
    if(l == r) seg[u].val = (info){v,1};
    else{
        int mid = (l + r)>>1;
        if(pos <= mid) change(u << 1, l, mid, pos, v);
        else change(u << 1 | 1, mid + 1, r, pos, v);

        update(u);
    }
}

// [u ,l ,r] 
// [ql ,qr]  quite 参数 目标参数
// 核心 u ql qr
info query(int u,int l,int r,int ql,int qr)
{
    if(l == ql && r == qr) return seg[u].val;

    int mid = (l + r) >> 1;

    // [l , mid]  [mid + 1, r]

    if(qr <= mid) return query(u << 1, l, mid, ql, qr);
    else if(ql >= mid + 1) return query(u << 1 | 1,mid + 1, r, ql, qr);
    else{
        // target  [ql, mid] [mid + 1, qr]

        return query(u << 1, l, mid, ql, mid)
         + query(u << 1 | 1, mid + 1, r, mid + 1, qr);
    }
}

线段树 求最大连续子段和#

const int N = 2e5 + 100;

int n,q;

int a[N];

struct info {
    int mss, mpre, msuf, s;
    info () {}
    info(int a) : mss(a), mpre(a), msuf(a), s(a) {}
};

info operator + (const info &l, const info &r){
    info a;
    a.mss = max({l.mss, r.mss, l.msuf + r.mpre});
    a.mpre = max(l.mpre, l.s + r.mpre);
    a.msuf = max(r.msuf, r.s + l.msuf);
    a.s = l.s + r.s;
    return a;
}

struct node{
    info val;
}seg[N * 4];

void build(int u,int l,int r)
{
    if(l == r) seg[u].val = info(a[l]);
    else{
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1,mid + 1, r);
        update(u);
        // 自下而上建树
    }
}

线段树 区间修改 区间查询#

const int N = 2e5 + 100;

int n,q;

int a[N];

struct info {
    int maxv;
};

struct tag {
    int add;
};

info operator + (const info &l, const info &r){
    info a;
    a.maxv = max(l.maxv, r.maxv);
    return a;
}

info operator + (const info &v, const tag &t)
{
    info a;
    a.maxv = v.maxv + t.add;
    return a;
}

tag operator + (const tag &t1, const tag &t2)
{
    tag a;
    a.add = t1.add + t2.add;
    return a;
}

struct node{
    tag t;
    info val;
}seg[N * 4];


// son -> fa
void update(int u){
    seg[u].val = seg[u << 1].val + seg[u << 1 | 1].val;
}

void settag(int u,tag t)
{
    seg[u].val = seg[u].val + t;
    seg[u].t = seg[u].t + t;
}

void pushdown(int u)
{
    if(seg[u].t.add != 0){
        settag(u << 1,seg[u].t);
        settag(u << 1 | 1,seg[u].t);
        seg[u].t.add = 0;
    }
}

void build(int u,int l,int r)
{
    if(l == r) seg[u].val = {a[l]};
    else{
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1,mid + 1, r);
        update(u);
        // 自下而上建树
    }
}

void modify(int u,int l,int r,int ql,int qr, tag t)
{
    if(l == ql && r == qr)
    {
        settag(u, t);
        return;
    }

    int mid = (l + r) >> 1;

    pushdown(u);

    // [l , mid]  [mid + 1, r]

    if(qr <= mid) modify(u << 1, l, mid, ql, qr, t);
    else if(ql >= mid + 1) modify(u << 1 | 1,mid + 1, r, ql, qr, t);
    else{
        // target  [ql, mid] [mid + 1, qr]

        modify(u << 1, l, mid, ql, mid, t);
        modify(u << 1 | 1, mid + 1, r, mid + 1, qr, t);
    }

    update(u);
}


// [u ,l ,r] 
// [ql ,qr]  quite 参数 目标参数
// 核心 u ql qr
info query(int u,int l,int r,int ql,int qr)
{
    if(l == ql && r == qr) return seg[u].val;

    int mid = (l + r) >> 1;

    // [l , mid]  [mid + 1, r]
    
    pushdown(u);
    if(qr <= mid) return query(u << 1, l, mid, ql, qr);
    else if(ql >= mid + 1) return query(u << 1 | 1,mid + 1, r, ql, qr);
    else{
        // target  [ql, mid] [mid + 1, qr]

        return query(u << 1, l, mid, ql, mid)
         + query(u << 1 | 1, mid + 1, r, mid + 1, qr);
    }
}

void solve()
{
    cin >> n >> q;
    for(int i = 1;i <= n;i ++) cin >> a[i];

    build(1, 1, n);
    
    for(int i = 0;i < q;i ++){
        int op;
        cin >> op;

        if(op == 1){
            int l, r, d;
            cin >> l >> r >> d;
            modify(1, 1, n, l, r, (tag){d});
        }
        else{
            int l, r;
            cin >> l >> r;
            auto ans = query(1, 1, n, l, r);
            cout << ans.maxv << endl;
        }
    }

}

基础 01trie 模版#

01Trie 是解决区间连续异或和和最大异或和的有利工具。

HDU 4825

给一个数集集合，给 $M$ 个询问。 每个询问 $ask_{i}$，给出集合中与他异或值最大的数。

const int N = 1e5 + 100;
const int Bit = 32;

int n,m;

struct Trie
{
    int id; int root;
    int tr[N * 32][2];
    long long val[N * 32];

    void init(){
        id = 1;
        root = 0;
        memset(tr[0], 0,sizeof(tr));
    }

    void insert(long long x){
    
    int go = root;
    for(int i = Bit;i >= 0;i --){
        int u = (x >> i) & 1;
        if(tr[go][u] == 0){
            memset(tr[id], 0, sizeof(tr[id]));
            tr[go][u] = id;
            val[id ++] = 0;
        }
        go = tr[go][u];
    }
    val[go] = x;

   }

   long long query(long long x){
        int go = root;
        for(int i = Bit;i >= 0;i --){
            int u = (x >> i) & 1;
            if(tr[go][u ^ 1]) go = tr[go][u ^ 1];
            else go = tr[go][u];
        }
        return val[go];
   }

}f;



void solve()
{
    f.init();
    cin >> n >> m;
    for(int i = 0;i < n;i ++)
    {
        long long x; cin >> x;
        f.insert(x);
    }

    while(m --)
    {
        long long v; cin >> v;
        cout << f.query(v) << endl;
    }

}

权值线段树#

给定数集 ${a_{n}}$ 和 $m$ 个询问。 每次询问两个数 $x_{i}$ $k_{i}$。 问 ${a_{n}}$ 中 $a_{j} \xor x_{i}$中排序第 $k_{i}$ 小的元素。

const int N = 2e5 + 100;
const int Bit = 32;

int n,m;

int x,k;

struct Trie
{
    int id; int root;
    int tr[N * 32][2];
    //long long val[N * 32];
    int sz[N * 32];

    void init(){
        id = 1;
        root = 1;
        memset(tr[0], 0,sizeof(tr));
        memset(sz, 0,sizeof sz);
    }

    int getid()
    {
        id ++;
        return id;
    }

    void insert(long long x){
    
    int go = root;
    for(int i = Bit;i >= 0;i --){
        
        sz[go] ++;
        int u = (x >> i) & 1;
        if(tr[go][u] == 0){
            memset(tr[id], 0, sizeof(tr[id]));
            tr[go][u] = getid();  
        }
        go = tr[go][u];
    }
        sz[go] ++;

   }

   long long query(long long x){
       int go = root;
       int ans = 0;
       for(int i = Bit;i >= 0;i --){
        int u = (x >> i) & 1;
        if(sz[tr[go][u]] >= k){
            go = tr[go][u];
        }
        else{
            k -= sz[tr[go][u]];
            ans ^= 1ll << i;
            go = tr[go][u ^ 1];
        }

       }

       return ans;
   }

}f;

void solve()
{
    cin >> n >> m;
    f.init();

    for(int i = 0;i < n;i ++)
    {
        cin >> x; f.insert(x);
    }

    for(int i = 0;i < m;i ++)
    {
        cin >> x >> k;
        cout << f.query(x) << endl;
    }
}

基础莫队#

给一个长度为 n 的序列。q 个询问。 问区间 (l,r) 中选两个数，选到相同数字的概率是多少。 n,q范围到 5e4。

const int N = 5e4 + 100;
int c[N];
int n,q;
int ans[N];
int ans2[N];
int cnt[N];
int tmp;
array<int,3> que[N];

void solve()
{
   cin >> n >> q;
   for(int i = 1;i <= n;i ++) cin >> c[i];
   for(int i = 0;i < q; i ++){
    int l,r; cin >> l >> r;
    que[i] = {l,r,i};
    ans2[i] = (r - l) * (r - l + 1) / 2;
   }

   int B = 500;
   sort(que, que + q, [&](array<int,3> a, array<int,3> b){
    if(a[0]/B != b[0]/B ) return a[0]/B < b[0]/B;
    return a[1]< b[1];
   }  );

   int l = 1; int r = 0;

   auto add = [&](int x){
    tmp += cnt[c[x]];
    cnt[c[x]] ++;
   };

   auto del = [&](int x){
    cnt[c[x]] --;
    tmp -= cnt[c[x]];
   };

   for(int i = 0;i < q;i ++){
    while(r < que[i][1]) r ++, add(r);
    while(l > que[i][0]) l --, add(l);
    while(r > que[i][1]) del(r), r --;
    while(l < que[i][0]) del(l), l ++;
    ans[que[i][2]] = tmp;
   }

   for(int i = 0;i < q;i ++)
   {
     int d = gcd(ans[i],ans2[i]);
     
     cout << ans[i]/d << '/' << ans2[i]/d << endl;
   }
}

回滚莫队#

给定一个长度为𝑛的序列，离线询问𝑚个问题 每次回答区间内元素val * cnt[val]的最大值。 n m 范围都到 1E5

const int N = 1e5 + 100;
int n,m;
int len;
int w[N],cnt[N];
int ans[N];

struct Query
{
    int id, l, r;
} q[N];

vector<int> nums;

int get(int x)
{
    return x/len;
}

bool cmp(const Query& a,const Query& b)
{
    if(get(a.l) == get(b.l)) return a.r < b.r;

    return get(a.l) < get(b.l);
}

void add(int x,int& res)
{
    cnt[x] ++;
    res = max(res,cnt[x] * nums[x]);
}

void solve()
{
    cin >> n >> m;
    len = sqrt(n);
    rep(i,1,n) cin >> w[i],nums.pb(w[i]);
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    rep(i,1,n) 
    w[i] = lower_bound(nums.begin(),nums.end(),w[i]) - nums.begin();

    for(int i = 0;i < m;i ++){
        int l,r; cin >> l >> r;
        q[i] = {i, l, r};
    }

    sort(q,q + m,cmp);

    for(int x = 0;x < m; )
    {
        int y = x;
        while(y < m && get(q[y].l) == get(q[x].l)) y++;   // 确定左边界在同一块的询问
        
        int right = get(q[x].l) * len + len - 1;          // 确定左边界块的右端点

        while(x < y && q[x].r <= right)                   // 暴力处理同一块的询问
        {
            int res = 0;
            rep(k,q[x].l,q[x].r) add(w[k],res);
            ans[q[x].id] = res;
            rep(k,q[x].l,q[x].r) cnt[w[k]] --;
            x ++;
        }

        int res = 0;
        int i = right; int j = right + 1;                 // 处理左右端点不在同一块的询问
        while(x < y)
        {
            while(i < q[x].r) add(w[++ i], res);          // 处理右端点所在部分
            int backup = res;                             // 备份只有右端点部分答案
            while(j > q[x].l) add(w[-- j],res);           // 处理左半部分
            ans[q[x].id] = res;                           // 记录答案
            while(j < right + 1) cnt[w[j ++]] --;         // 回溯数量
            res = backup;                                 // 回溯右端点答案
            x ++;
        }                                                 // 相当于每次只记录右端点的影响
        memset(cnt, 0,sizeof cnt);                        // 涉及左端点时重算

    }

    for(int i = 0;i < m;i ++) cout << ans[i] << endl;
}

学习参考:大佬的资料

点分治#

const int N = 1e5 + 100;

int n, sz[N], maxs[N], L;
vector<PII> e[N];
bool del[N];
int ans;

void solves(int u, int s) {
	int ms = s + 1, root = -1;
	function<void(int, int)> dfs1 = [&](int u, int par) {
		sz[u] = 1;
		maxs[u] = 0;
		for (auto [v, w]: e[u]) {
			if (del[v] || v == par) continue;
			dfs1(v, u);
			sz[u] += sz[v];
			maxs[u] = max(maxs[u], sz[v]);
		}
		maxs[u] = max(maxs[u], s - sz[u]);
		if (maxs[u] < ms) ms = maxs[u], root = u;
	};
	dfs1(u, -1);
	vector<int> d1, d2;
	d1.push_back(0);
	auto calc = [&](vector<int> &d) {
		sort(d.begin(), d.end());
		int m = d.size();
		int r = m - 1;
		int ans = 0;
		for (int i = 0; i < m; i++) {
			while (r >= 0 && d[i] + d[r] > L) --r;
			if (i < r) ans += r - i;
		}
		return ans;
	};
	for (auto [v, w] : e[root]) {
		if (del[v]) continue;
		d2.clear();
		function<void(int, int, int)> dfs2 = [&](int u, int par, int dep) {
			sz[u] = 1;
            d1.push_back(dep);
			d2.push_back(dep);
			for (auto [v, w] : e[u]) {
				if (del[v] || v == par) continue;
                dfs2(v, u, dep + w);
                sz[u] += sz[v];
			}
		};
		dfs2(v, root, w);
		ans -= calc(d2);
	}
	ans += calc(d1);
	del[root] = true;
	for (auto [v, w] : e[root]) {
		if (!del[v]) solves(v, sz[v]);
	}
}

void solve()
{
    cin >> n;
    for(int i = 1;i < n;i ++){
        int u,v,w;
        cin >> u >> v >> w;
        e[u].pb(make_pair(v,w));
        e[v].pb(make_pair(u,w));
    }
    cin >> L;
    solves(1, n);
    cout << ans << endl;
}

ST表#

#include <bits/stdc++.h>
using namespace std;
const int logn = 21;
const int maxn = 2000001;
int f[maxn][logn + 1], Logn[maxn + 1];

int read() {  // 快读
  char c = getchar();
  int x = 0, f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}

void pre() {  // 准备工作，初始化
  Logn[1] = 0;
  Logn[2] = 1;
  for (int i = 3; i < maxn; i++) {
    Logn[i] = Logn[i / 2] + 1;
  }
}

int main() {
  int n = read(), m = read();
  for (int i = 1; i <= n; i++) f[i][0] = read();
  pre();
  for (int j = 1; j <= logn; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);  // ST表具体实现
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read();
    int s = Logn[y - x + 1];
    printf("%d\n", max(f[x][s], f[y - (1 << s) + 1][s]));
  }
  return 0;
}

Tarjan#

给一个 n 个点 m 条边的图，输出所有的强连通分量。

#define pb push_back

int n,m;
const int N = 1e5 + 100;
vector<int> e[N];

int dfn[N],low[N],ins[N],bel[N];
int idx,cnt;

stack<int> stk;
vector<vector<int>> scc;

void dfs(int u)
{
    dfn[u] = low[u] = ++idx;
    ins[u] = true; stk.push(u);

    for(auto v : e[u])
    {
        if(!dfn[v]) dfs(v);
        if(ins[v]) low[u] = min(low[u],low[v]);
    }
    if(dfn[u] == low[u])
    {
        vector<int> c; ++ cnt;
        while(true){
            int v = stk.top();
            c.pb(v);ins[v] = false;
            bel[v] = cnt;
            stk.pop();
            if(u == v) break;
        }
        sort(c.begin(),c.end());
        scc.pb(c);
    }
}

void solve()
{ 
   cin >> n >> m;
   for(int i = 0;i < m;i ++){
    int u,v; cin >> u >> v;
    e[u].pb(v);
   }
   for(int i = 1;i <= n;i ++) if(!dfn[i]) dfs(i);
   sort(scc.begin(),scc.end());
   for(auto c : scc){
    for(auto u : c) cout << u << ' ';
    cout << endl;
   }
}

匈牙利算法#

#define pb push_back
#define rep(i, x, y) for(int i=x;i<=y;i++)

int n,m,k;
vector<int> g[N];

map<int,int> mp;

bool st[N];  // vailable of second set

bool find(int x)
{
    for(int y : g[x])
    {
        if(st[y] ^ 1)
        {
            st[y] = true;
            if(mp[y] == 0 || find(mp[y])) 
            { 
                mp[y] = x;
                return true;
            }
        }
    }

    return false;
}

void solve()
{
    cin >> n >> m >> k;
    for(int i = 0;i < k;i ++){
        int u,v; cin >> u >> v;
        g[u].pb(v);
    }
    int res = 0;
    rep(i,1,n)
    { 
        memset(st,false,sizeof st);
        if(find(i)) res ++;
    }
    cout << res << endl;
}