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

#include#definerep(i,a,b) for(int i=(a);i<=(b);++i)#defineper(i,a,b) for(int i=(a);i>=(b);--i)#definepii pair#definevi vector#definefi first#definese second#definepb push_back#defineALL(x) x.begin(),x.end()#definesz(x) int(x.size())#definell long longusingnamespacestd;constintN =3e5+5,M =1e6+50;structDSU{vector<int> p,sz;voidinit(intn){ p.resize(n);sz.assign(n,1); iota(p.begin(),p.end(),0); }intfind(intx){returnp[x] == x ? x : p[x] = find(p[x]);}voidmerge(intu,intv){ 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;intn;intmain(){cin.tie(0)->sync_with_stdio(0);cin>> n;via(n);for(auto&x : a)cin>> x;vector vec(M); rep(i,0,n-1)vec[a[i]].pb(i);vector cnt(M);viR(n,-1),L(n+1,-1);autogetR = [&](intx){if(x == n)returnn;returnR[d.find(x)]; };set<int> alive; ll ans =0,now =0;//the amount of values <= id.init(n); rep(i,1,M-1){vector<int> dead,remove;for(intx : alive){intr = getR(x);intnxtR = 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(intx : dead){ alive.erase(x);if(L[getR(x)] ==-1)L[getR(x)] = x;elsed.merge(L[getR(x)],x); }for(intx : remove)L[x] =-1;for(intx : 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';return0; }

#include#definerep(i,a,b) for(int i=(a);i<=(b);++i)#defineper(i,a,b) for(int i=(a);i>=(b);--i)#definepii pair#definevi vector#definefi first#definese second#definepb push_back#defineALL(x) x.begin(),x.end()#definesz(x) int(x.size())#definell long longusingnamespacestd;constintN =1e5+5;intn,m,q,fa[N],out[N];intfind(intx){returnfa[x] == x ? x : fa[x] = find(fa[x]);}set<int> G[N],R[N];boolchk(intx,inty){ x = find(x),y = find(y);if(!fa[x] || !fa[y])return1;//dead endif(x == y)return1;return0; }intmain(){cin.tie(0)->sync_with_stdio(0);cin>> n >> m;intu,v; rep(i,1,m){cin>> u >> v; out[u]++; R[v].insert(u);//reverse graphG[u].insert(v); }queue<int> Q; rep(i,1,n){ fa[i] = i;if(sz(G[i]) <=1)Q.push(i); }while(!Q.empty()){//topointu = Q.front(); Q.pop();intv =0;for(intx : G[u])if(find(x) !=0){ v = find(x);break; }if(v ==0){//dead endfa[u] =0;for(intx : R[u]){ --out[x];if(out[x] ==1)Q.push(x); } }else{//merge points of outdeg = 1if(u == v)continue; R[v].erase(u);if(sz(R[u]) > sz(R[v]))swap(R[u],R[v]); fa[u] = v;for(intx : R[u]){if(R[v].find(x) != R[v].end()){ --out[x];if(out[x] ==1)Q.push(x); }elseR[v].insert(x); } } R[u].clear(); }cin>> q;while(q--){cin>> u >> v;if(chk(u,v))putchar('B');elseputchar('H'); }return0; }

#include#definerep(i,a,b) for(int i=(a);i<=(b);++i)#defineper(i,a,b) for(int i=(a);i>=(b);--i)#definepii pair#definevi vector#definefi first#definese second#definepb push_back#definell long longusingnamespacestd;constintN =3e5+5;#definemid ((L + R) >> 1)#definels (p << 1)#definers (ls | 1)structSegTree{intmx[N <<2];voidpushup(intp){mx[p] = max(mx[ls],mx[rs]);}voidmodify(intp,intL,intR,intx,intv){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); }intQ(intp,intL,intR,intl,intr){if(r < L || R < l)return0;if(l <= L && R <= r)returnmx[p];returnmax(Q(ls,L,mid,l,r),Q(rs,mid +1,R,l,r)); } }f,g;intn,a[N];strings;intmain(){cin.tie(0)->sync_with_stdio(0);cin>> n; rep(i,1,n)cin>> a[i];cin>> s; rep(i,1,n){intU = 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);elseg.modify(1,1,n,a[i],U);if(s[D -1] =='U')f.modify(1,1,n,a[i],D);elseg.modify(1,1,n,a[i],D); }intans = max(f.Q(1,1,n,1,n),g.Q(1,1,n,1,n));cout<< ans -1<<'n';return0; }