USACO 22OPEN Platinum题解方法及代码分享

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
const int N = 3e5 + 5,M = 1e6 + 50;
struct DSU{
    vector <int> p,sz;
    void init(int n){
        p.resize(n);sz.assign(n,1);
        iota(p.begin(),p.end(),0);
    }
    int find(int x){return p[x] == x ? x : p[x] = find(p[x]);}
    void merge(int u,int v){
        u = find(u),v = find(v);
        if(u == v)return;
        if(sz[u] > sz[v])swap(u,v);
        p[u] = v,sz[v] += sz[u],sz[u] = 0;
    }
}d;
int n;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    vi a(n);for(auto &x : a)cin >> x;
    vector <vi> vec(M);
    rep(i,0,n-1)vec[a[i]].pb(i);
    vector <ll> cnt(M);
    vi R(n,-1),L(n+1,-1);
    auto getR = [&](int x){
        if(x == n)return n;
        return R[d.find(x)];
    };
    set <int> alive;
    ll ans = 0,now = 0;//the amount of values <= i
    d.init(n);
    rep(i,1,M-1){
        vector <int> dead,remove;
        for(int x : alive){
            int r = getR(x);
            int nxtR = max(r,r == n ? -1 : getR(r));
            if(nxtR == r)dead.pb(x);
            else{
                if(L[nxtR] != -1)dead.pb(x);
                else{
                    L[nxtR] = x;
                    remove.pb(nxtR);
                }
                now += 1ll * (nxtR - r) * d.sz[d.find(x)];
                R[d.find(x)] = nxtR;
            }
        }
        for(int x : dead){
            alive.erase(x);
            if(L[getR(x)] == -1)L[getR(x)] = x;
            else d.merge(L[getR(x)],x);
        }
        for(int x : remove)L[x] = -1;
        for(int x : vec[i]){
            ++now;
            R[x] = x + 1;
            alive.insert(x);
            if(L[x] != -1)alive.insert(L[x]);
            L[x] = -1;
        }
        cnt[i] = now;
    }
    per(i,M-1,0)cnt[i] -= cnt[i-1];
    rep(i,1,M-1)ans += cnt[i] * i;
    cout << ans << 'n';
    return 0;
}

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int n,m,q,fa[N],out[N];
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
set <int> G[N],R[N];
bool chk(int x,int y){
    x = find(x),y = find(y);
    if(!fa[x] || !fa[y])return 1;//dead end
    if(x == y)return 1;
    return 0;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    int u,v;
    rep(i,1,m){
        cin >> u >> v;
        out[u]++;
        R[v].insert(u);//reverse graph
        G[u].insert(v);
    }
    queue <int> Q;
    rep(i,1,n){
        fa[i] = i;
        if(sz(G[i]) <= 1)Q.push(i);
    }
    while(!Q.empty()){//topo
        int u = Q.front();
        Q.pop();
        int v = 0;
        for(int x : G[u])if(find(x) != 0){
            v = find(x);
            break;
        }
        if(v == 0){//dead end
            fa[u] = 0;
            for(int x : R[u]){
                --out[x];
                if(out[x] == 1)Q.push(x);
            }
        }else{
            //merge points of outdeg = 1
            if(u == v)continue;
            R[v].erase(u);
            if(sz(R[u]) > sz(R[v]))swap(R[u],R[v]);
            fa[u] = v;
            for(int x : R[u]){
                if(R[v].find(x) != R[v].end()){
                    --out[x];
                    if(out[x] == 1)Q.push(x); 
                }else R[v].insert(x);
            }
        }
        R[u].clear();
    }
    cin >> q;
    while(q--){
        cin >> u >> v;
        if(chk(u,v))putchar('B');
        else putchar('H');
    }
    return 0;
}

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
const int N = 3e5 + 5;
#define mid ((L + R) >> 1)
#define ls (p << 1)
#define rs (ls | 1)
struct SegTree{
    int mx[N << 2];
    void pushup(int p){mx[p] = max(mx[ls],mx[rs]);}
    void modify(int p,int L,int R,int x,int v){
        if(L == R){
            mx[p] = max(mx[p],v);
            return;
        }
        x <= mid ? modify(ls,L,mid,x,v) : modify(rs,mid + 1,R,x,v);
        pushup(p);
    }
    int Q(int p,int L,int R,int l,int r){
        if(r < L || R < l)return 0;
        if(l <= L && R <= r)return mx[p];
        return max(Q(ls,L,mid,l,r),Q(rs,mid + 1,R,l,r));
    }
}f,g;
int n,a[N];
string s;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    rep(i,1,n)cin >> a[i];
    cin >> s;
    rep(i,1,n){
        int U = f.Q(1,1,n,1,a[i]),D = g.Q(1,1,n,a[i],n);
        U++,D++;
        if(s[U - 1] == 'U')f.modify(1,1,n,a[i],U);
        else g.modify(1,1,n,a[i],U);
        if(s[D - 1] == 'U')f.modify(1,1,n,a[i],D);
        else g.modify(1,1,n,a[i],D);
    }
    int ans = max(f.Q(1,1,n,1,n),g.Q(1,1,n,1,n));
    cout << ans - 1 << 'n';
    return 0;
}