T1 星际联邦
菠萝算法。不过简化版。考虑从后往前遍历，如果当前的电 的联通块大小为 \(1\) 的话，就把他和前缀最大值或者是前缀最小值连边。如果大于 \(1\)，那就将联通块里的最小权点和前缀最大值连边即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 3e5 + 5;
int n, a[N], f[N], mn[N], Mx[N], Mn[N], siz[N];
inline int find(int k){ return f[k] ? f[k] = find(f[k]) : k; }
inline void merge(int a, int b){
a = find(a), b = find(b); f[b] = a;
mn[a] = min(mn[a], mn[b]);
siz[a] += siz[b];
}
signed main(){
freopen("star.in", "r", stdin); freopen("star.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n; for(int i=1; i<=n; ++i) cin>>a[i];
Mx[1] = 1; Mn[n] = n;
for(int i=2; i<=n; ++i){
Mx[i] = Mx[i-1];
if(a[Mx[i]] < a[i]) Mx[i] = i;
}
for(int i=n-1; i>=1; --i){
Mn[i] = Mn[i+1];
if(a[i] < a[Mn[i]]) Mn[i] = i;
}
for(int i=1; i<=n; ++i) mn[i] = a[i], siz[i] = 1;
int ans = 0;
for(int i=n; i>=2; --i){
if(siz[find(i)] == 1 && i != n){
if(a[i] - a[Mx[i-1]] < a[Mn[i+1]] - a[i]){
ans += a[i] - a[Mx[i-1]];
merge(i, Mx[i-1]);
} else {
ans += a[Mn[i+1]] - a[i];
merge(i, Mn[i+1]);
}
} else {
ans += mn[find(i)] - a[Mx[i-1]];
merge(i, Mx[i-1]);
}
} return cout<<ans, 0;
}
T2 和平精英
有一个显然的性质就是，把一堆数与起来，大小是不升的，把一堆数或起来，大小是不降的。那么假定一个值 \(val\) 显然要把所有小于 \(val\) 的值或起来，把所有大于 \(val\) 的值与起来，等于 \(val\) 的值随便放。
考虑如何优化，继续发掘性质，把一堆数与起来，数中 \(1\) 的数量不升，把一堆数或起来，\(1\) 的数量不降。那么假定一个 \(1\) 的数量 \(p\)，显然要把所有 \(1\) 的数量小于 \(p\) 的值或起来，把所有 \(1\) 的数量大于 \(p\) 的值与起来。等于 \(p\) 的数一定相等，若不相等 \(p\) 无效。单次查询复杂度为 \(\mathcal{O}(n\log n)\)。使用线段树维护复杂度为 \(\mathcal{O}((n+q)\log n)\)。
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
int n, a[N], q;
namespace ST{
#define ls (id << 1)
#define rs (id << 1 | 1)
struct node{
int l, r, _or[31], _and[31], val[31], num[31];
bitset<31> orvis, andvis;
node(){
memset(_or, 0, sizeof(_or));
memset(val, 0, sizeof(val));
memset(num, 0, sizeof(num));
orvis.reset(), andvis.reset();
for(int i=0; i<=30; ++i) _and[i] = (1 << 30) - 1;
}
}t[N<<2];
inline void pushup(node &id, node _ls, node _rs){
for(int i=0; i<=30; ++i){
id._or[i] = _ls._or[i] | _rs._or[i];
id.val[i] = _ls.val[i] | _rs.val[i];
id._and[i] = _ls._and[i] & _rs._and[i];
id.andvis[i] = _ls.andvis[i] | _rs.andvis[i];
id.orvis[i] = _ls.orvis[i] | _rs.orvis[i];
id.num[i] = _ls.num[i] + _rs.num[i];
}
}
inline void build(int id, int l, int r){
t[id].l = l, t[id].r = r;
if(l == r){
for(int i=0; i<=30; ++i) t[id]._and[i] = (1 << 30) - 1;
int cnt = __builtin_popcount(a[l]);
t[id].val[cnt] = a[l]; t[id].num[cnt] = 1;
for(int i=0; i<cnt; ++i) t[id]._and[i] = a[l], t[id].andvis[i] = 1;
for(int i=cnt+1; i<=30; ++i) t[id]._or[i] = a[l], t[id].orvis[i] = 1;
return;
} int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid+1, r);
pushup(t[id], t[ls], t[rs]);
}
inline node query(int id, int l, int r){
if(l <= t[id].l && t[id].r <= r) return t[id];
int mid = (t[id].l + t[id].r) >> 1; node res; bool ok = 0;
if(l <= mid) res = query(ls, l, r), ok = 1;
if(r > mid){
if(!ok) res = query(rs, l, r);
else pushup(res, res, query(rs, l, r));
} return res;
}
}
int main(){
freopen("peace.in", "r", stdin); freopen("peace.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>q; for(int i=1; i<=n; ++i) cin>>a[i];
ST::build(1, 1, n);
auto check = [](int _and, int _or, int val, int num, bool vand, bool vor){
if(!num) return (_and == _or) && vand && vor;
if(num == 1) return ((_or | val) == _and && vand) || ((val & _and) == _or && vor);
return (_or | val) == (val & _and);
};
while(q--){
int l, r; cin>>l>>r;
ST::node res = ST::query(1, l, r);
bool ok = 0;
for(int i=0; i<=30; ++i) if((res.num[i] && __builtin_popcount(res.val[i]) == i) && check(res._and[i], res._or[i], res.val[i], res.num[i], res.andvis[i], res.orvis[i]))
{ ok = 1; break; }
cout<<(ok ? "YES" : "NO")<<'\n';
} return 0;
}
T3 摆烂合唱
给我一天也想不到，这东西可以建树求解。树的叶子节点为 \(0/1\)，其他的为运算符。所以整个表达式的值就是根节点的值。令 \(g_u\) 表示当前节点的值为 \(1\) 的概率，根据与、或和异或的定义，有：
\[g_u=\left\{\begin{matrix} or & 1-(1-g_{ls})(1-g_{rs})\\ and & g_{ls}\times g_{rs}\\ xor & g_{ls}(1-g_{rs})+g_{rs}(1-g_{ls}) \end{matrix}\right. \]特殊地，叶子节点的 \(g\) 为 \(\frac{1}{2}\)。令 \(f_{u,0/1}\) 表示当左儿子或者右儿子取 \(0,1\) 的时候表达式值变化的概率，那么有：
\[f_{u,0}=\left\{\begin{matrix} or & 1-g_{rs}\\ and & g_{rs}\\ xor & 1 \end{matrix}\right. \ \ f_{u,1}=\left\{\begin{matrix} or & 1-g_{ls}\\ and & g_{ls}\\ xor & 1 \end{matrix}\right. \]做两次 dfs 即可求出。复杂度 \(\mathcal{O}(n)\)。注意特判 \(n=1\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N = 2e5 + 5, M = 998244353;
int n, cnt, opt[N], rt, st[N], tl, g[N], ls[N], rs[N], f[N][2], ans[N];
string str;
inline int add(initializer_list<int> Add){
int res = 0;
for(int v : Add) res = res + v >= M ? res + v - M : res + v;
return res;
}
inline int mul(initializer_list<int> Mul){
int res = 1;
for(int v : Mul) res = (ll)res * v % M;
return res;
}
inline int mod(int x){ return (x + M) % M; }
inline int calc(int x){ return add({1, mod(-x)}); }
inline void dfs1(int u){
if(!ls[u]) return;
int l = ls[u], r = rs[u];
dfs1(l), dfs1(r);
if(opt[u] == 1){
g[u] = calc(mul({calc(g[l]), calc(g[r])}));
f[u][0] = calc(g[l]), f[u][1] = calc(g[r]);
} else if(opt[u] == 2){
g[u] = mul({g[l], g[r]});
f[u][0] = g[l], f[u][1] = g[r];
} else {
g[u] = add({mul({g[l], calc(g[r])}), mul({g[r], calc(g[l])})});
f[u][0] = f[u][1] = 1;
}
}
inline void dfs2(int u, int val){
if(!ls[u]) return ans[u] = val, void();
dfs2(ls[u], mul({val, f[u][1]}));
dfs2(rs[u], mul({val, f[u][0]}));
}
int main(){
freopen("binary.in", "r", stdin); freopen("binary.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>str; int len = str.size();
if(n == 1) return cout<<'1', 0;
for(int i=0; i<len; ++i){
if(str[i] == '|' || str[i] == '^' || str[i] == '&'){
opt[++cnt] = str[i] == '|' ? 1 : str[i] == '&' ? 2 : 3;
ls[cnt] = st[tl]; st[tl] = cnt;
} else if(str[i] == 'x'){
if(st[tl] == -1) st[++tl] = ++cnt, g[cnt] = 499122177;
else st[++tl] = ++cnt, g[cnt] = 499122177;
} else if(str[i] == ')'){
int x = st[tl--];
rs[rt = st[tl]] = x;
st[--tl] = rt;
} else st[++tl] = -1;
} dfs1(rt); dfs2(rt, 1);
for(int i=1; i<=cnt; ++i) if(!ls[i]) cout<<ans[i]<<'\n';
return 0;
}
T4 对称旅行者
看样子是个没见过的 trick。如果说求所有情况的值的和，那么可以考虑转成期望来计算。令 \(f_i\) 表示旅行者 \(i\) 的期望位置，那么有：\(f_i=\frac{1}{2}(2f_{i-1}-f_i+2f_{i+1}-f_i)=f_{i-1}+f_{i+1}-f_i\)，也就是把 \(f_i\) 关于 \(f_{i-1}\) 和 \(f_{i+1}\) 的中点对称。令 \(g_i=f_{i+1}-f_i\)，那么条第 \(i\) 枚棋子相当于交换 \(g_{i-1}\) 和 \(g_i\)。然后求置换即可。
#include<bits/stdc++.h>
using namespace std;
#define ll __int128
#define int long long
constexpr int N = 1e5 + 5, M = 1e9 + 7;
int m, n, to[N]; int k, g[N], f[N];
struct node{ int to[N]; } bg, ans;
inline int qpow(int a, int k){
int res = 1; while(k){
if(k & 1) res = (ll)res * a % M;
a = (ll)a * a % M; k >>= 1;
} return res;
}
inline int mul(int a, int b){ return ((ll)a * b % M + M) % M; }
signed main(){
freopen("travel.in", "r", stdin); freopen("travel.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n; for(int i=1; i<=n; ++i) cin>>f[i];
for(int i=1; i<n; ++i) g[i] = f[i+1] - f[i], to[i] = i;
cin>>m>>k; for(int i=1, a; i<=m; ++i) cin>>a, swap(to[a], to[a-1]);
for(int i=1; i<n; ++i) bg.to[to[i]] = i;
int p = qpow(qpow(2, k), m); --k;
auto merge = [](node a, node b){
node c;
for(int i=1; i<n; ++i) c.to[i] = b.to[a.to[i]];
return c;
}; ans = bg;
while(k){
if(k & 1) ans = merge(ans, bg);
bg = merge(bg, bg), k >>= 1;
}
for(int i=1; i<n; ++i) to[ans.to[i]] = i;
for(int i=2; i<=n; ++i) f[i] = f[i-1] + g[to[i-1]];
for(int i=1; i<=n; ++i) cout<<mul(f[i], p)<<' ';
return 0;
}