省选模拟之辞旧迎新1
A. 神必的集合
不太理解
code
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cassert>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 405;
const int mod = 998244353;
void add(int &x, int y){x += y; if(x >= mod)x -= mod;}
int n, m, rk[maxn], a[maxn], f[65], dp[65][65], p2[65];
void ins(int x){
for(int i = n - 1; i >= 0; --i)if((x >> i) & 1){
if(!f[i])f[i] = x, i = 0;
else x ^= f[i];
}
}
int solve(){
for(int i = 0; i <= n; ++i)p2[i] = (1ll << n) - 1;
for(int i = 1; i <= m; ++i)ins(a[i]);
int mx = 0;
for(int j = 1; j <= m; ++j){
int nowa = a[j], d = rk[j];
for(int i = 0; i < n; ++i){
if((d >> i) & 1)p2[i + 1] &= nowa, mx = max(mx, i + 1);
else p2[i + 1] &= (p2[0] ^ nowa);
}
}
if(!f[0])dp[0][0] = 1; if(p2[1] & 1)dp[0][1] = 1;
for(int i = 1; i < n; ++i){
if(f[i]){
for(int j = 1; j <= i + 1; ++j)if((p2[j] >> i) & 1)
add(dp[i][j], dp[i - 1][j - 1]);
}else{
for(int j = 1; j <= i + 1; ++j)if((p2[j] >> i) & 1)
add(dp[i][j], (1ll << (i + 1 - j)) % mod * dp[i - 1][j - 1] % mod);
for(int j = 0; j <= i; j++)add(dp[i][j], dp[i - 1][j]);
}
}
int ans = 0;
for(int i = mx; i <= n; ++i)
add(ans, dp[n - 1][i]);
return ans;
}
signed main(){
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
n = read(), m = read();
for(int i = 1; i <= m; ++i)rk[i] = read() - 1, a[i] = read();
printf("%d\n", solve());
return 0;
}
B. 法阵
原题见
https://www.cnblogs.com/Chencgy/p/16760114.html
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){
int x = 0; char c = getchar();
while(c < '0' || c > '9')c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');
return x;
}
const int maxn = 500005;
int a[maxn], n;
struct query{
int l, r, id;
friend bool operator < (const query &x, const query &y){
return x.l > y.l;
}
}q[maxn];
struct seg{
struct node{
ll tag, val, mx;
}t[maxn << 2 | 1];
void push_up(int x){
t[x].mx = max(t[x << 1].mx, t[x << 1 | 1].mx);
t[x].val = max(t[x << 1].val , t[x << 1 | 1].val);
}
void built(int x, int l, int r){
if(l == r){
t[x].mx = a[l];
return;
}
int mid = (l + r) >> 1;
built(x << 1, l, mid);
built(x << 1 | 1, mid + 1, r);
push_up(x);
}
void upd(int x, ll val){
t[x].tag = max(t[x].tag, val);
t[x].val = max(t[x].val, t[x].mx + val);
}
void push_down(int x){
upd(x << 1, t[x].tag);
upd(x << 1 | 1, t[x].tag);
t[x].tag = 0;
}
void modify(int x, int l, int r, int L, int R, ll val){
if(L > R)return;
if(L <= l && r <= R){
upd(x, val);
return;
}
if(t[x].tag)push_down(x);
int mid = (l + r) >> 1;
if(L <= mid)modify(x << 1, l, mid, L, R, val);
if(R > mid)modify(x << 1 | 1, mid + 1, r, L ,R, val);
push_up(x);
}
ll query(int x, int l, int r, int L, int R){
if(L <= l && r <= R)return t[x].val;
if(t[x].tag)push_down(x);
int mid = (l + r) >> 1;
ll ans = 0;
if(L <= mid)ans = max(ans, query(x << 1, l, mid, L, R));
if(R > mid)ans = max(ans, query(x << 1 | 1, mid + 1, r, L, R));
return ans;
}
}t;
int sta[maxn], top;
ll ans[maxn];
void pop(int x){
t.modify(1, 1, n, sta[top] + sta[top] - x, n, a[sta[top]] + a[x]);
--top;
}
void push(int x){
if(top)t.modify(1, 1, n, sta[top] + sta[top] - x, n, a[sta[top]] + a[x]);
sta[++top] = x;
}
int main(){
freopen("fz.in","r",stdin);
freopen("fz.out","w",stdout);
n = read();
for(int i = 1; i <= n; ++i)a[i] = read();
t.built(1, 1, n);
int Q = read();
for(int i = 1; i <= Q; ++i){
q[i].l = read(); q[i].r = read(); q[i].id = i;
}
sort(q + 1, q + Q + 1);
int pq = 1;
for(int i = n; i >= 1; --i){
while(top && a[sta[top]] <= a[i])pop(i);
push(i);
while(pq <= Q && q[pq].l >= i){
ans[q[pq].id] = t.query(1, 1, n, q[pq].l, q[pq].r);
++pq;
}
}
for(int i = 1; i <= Q; ++i)printf("%lld\n",ans[i]);
return 0;
}
C. 旅行
暴力连边优化，在点分治时候连边，对每个深度开一个虚点
详细看学长的博客吧
https://www.cnblogs.com/MaxQAQ/p/16010035.html
题解做法是建立点分树，不过跟这个本质类似
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, int> pli;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 2e5 + 55;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, cnt, rem[maxn];
struct DSU{
int f[maxn];
void init(){for(int i = 1; i <= n; ++i)f[i] = i;}
int fa(int x){return f[x] == x ? x : f[x] = fa(f[x]);}
bool merge(int x, int y){x = fa(x); y = fa(y); if(x == y)return false; f[y] = x; return true;}
}s;
int d[maxn], c[maxn];
struct EDGE{int x, y;}E[maxn];
vector<int>g[maxn];
bool del[maxn], vis[maxn * 150], in[maxn];
int dis[maxn * 150];
ll ans[maxn * 150];
priority_queue<pli, vector<pli>, greater<pli>>q;
struct edge{int to, net, val;}e[maxn * 150];
int head[maxn * 40], tot;
void add(int u, int v, int w){
e[++tot].net = head[u];
head[u] = tot;
e[tot].to = v;
e[tot].val = w;
}
int S, mx[maxn], si[maxn], root, mxd, dep[maxn];
void getroot(int x, int fa){
si[x] = 1; mx[x] = 0;
for(int v : g[x])if(!del[v] && v != fa){
getroot(v, x);
si[x] += si[v];
mx[x] = max(mx[x], si[v]);
}
mx[x] = max(mx[x], S - si[x]);
if(mx[x] < mx[root])root = x;
}
void dfs1(int x, int fa){
mxd = max(mxd, dep[x]);
for(int v : g[x])if(!del[v] && v != fa){
dep[v] = dep[x] + 1;
dfs1(v, x);
}
}
void dfs2(int x, int fa){
add(rem[dep[x]], x, 0);
if(d[x] >= dep[x])add(x, rem[min(mxd, d[x] - dep[x])], c[x]);
for(auto v : g[x])if(!del[v] && v != fa)dfs2(v, x);
}
void calc(int x){
mxd = 0;
dep[x] = 0; dfs1(x, 0);
for(int i = 0; i <= mxd; ++i)rem[i] = ++cnt;
for(int i = 1; i <= mxd; ++i)add(rem[i], rem[i - 1], 0);
dfs2(x, 0);
}
void solve(int x){
del[x] = 1; calc(x);
for(int v : g[x])if(!del[v]){
S = si[v]; root = 0;
getroot(v, x); solve(root);
}
}
void bfs(int S){
queue<int>q;
for(int i = 1; i <= n; ++i)dis[i] = 0x3f3f3f3f; dis[S] = 0; q.push(S);
while(!q.empty()){
int x = q.front(); q.pop();
for(int v : g[x])if(dis[v] > dis[x] + 1){
dis[v] = dis[x] + 1;
q.push(v);
}
}
}
int main(){
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
n = read(), m = read(); s.init();
for(int i = 1; i <= m; ++i)E[i].x = read(), E[i].y = read();
for(int i = 1; i <= n; ++i)d[i] = read(), c[i] = read();
for(int i = 1; i <= m; ++i)if(s.merge(E[i].x, E[i].y)){
in[i] = true; g[E[i].x].push_back(E[i].y); g[E[i].y].push_back(E[i].x);
}
cnt = S = n; mx[0] = n + n; getroot(1, 0); solve(root);
for(int i = 1; i <= m; ++i)if(!in[i]){
g[E[i].x].push_back(E[i].y);
g[E[i].y].push_back(E[i].x);
}
for(int i = 1; i <= m; ++i)if(!in[i]){
bfs(E[i].x); int mxd = 0;
for(int j = 1; j <= n; ++j)mxd = max(mxd, dis[j]);
for(int j = 0; j <= mxd; ++j)rem[j] = ++cnt;
for(int j = 1; j <= n; ++j)add(rem[dis[j]], j, 0);
for(int j = 1; j <= mxd; ++j)add(rem[j], rem[j - 1], 0);
for(int j = 1; j <= n; ++j)if(d[j] >= dis[j])add(j, rem[min(d[j] - dis[j], mxd)], c[j]);
}
for(int i = 1; i <= cnt; ++i)ans[i] = inf; q.push(pli(0, 1)); ans[1] = 0;
while(!q.empty()){
int x = q.top().second; q.pop();
if(vis[x])continue;
vis[x] = true;
for(int i = head[x]; i; i = e[i].net){
int v = e[i].to;
if(ans[v] > ans[x] + e[i].val){
ans[v] = ans[x] + e[i].val;
q.push(pli{ans[v], v});
}
}
}
for(int i = 2; i <= n; ++i)printf("%lld\n",ans[i]);
return 0;
}
省选模拟之辞旧迎新2
A. 小 F 与游戏
阿巴阿巴
code
#include<bits/stdc++.h>
using namespace std;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 1e6 + 55, mx = 1e6;
int n, k, mod, fac[maxn], ifac[maxn];
int qpow(int x, int y){
int ans = 1;
for(; y; y >>= 1, x = 1ll * x * x % mod)if(y & 1)ans = 1ll * ans * x % mod;
return ans;
}
inline int c(int n,int m){return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;}
signed main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
n = read(); k = read(); mod = read();
fac[0] = ifac[0] = 1; for(int i = 1; i <= mx; ++i)fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[mx] = qpow(fac[mx], mod - 2);
for(int i = mx - 1; i >= 1; --i)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
if(k == 1){
printf("%d\n", qpow(2,n - 2));
return 0;
}
if(n==k){
printf("%d\n",(c(n + n - 2, n - 1) - c(n + n - 2, n - 2) + mod) % mod);
return 0;
}
printf("%d\n",1ll * qpow(2, n - k - 1) * ( c(n + k - 2, k - 1) - c(n + k - 2, k - 2) + mod) % mod);
return 0;
}
B. 小 Z 与函数
不考虑 \(vs\)， 剩下的就是顺序对
现在考虑如何得到 \(vs\)
考虑执行完 \(i - 1\) 轮之后
第 \(i\) 个位置上是 \([1, i]\) 的最小值，而此次循环首次产生贡献的位置是后面第一个比最小值大的数
把贡献放到那个位置即可
但是可能会有重复选择同一个位置的情况，那么记录对于每个最小值上次选择的位置在哪里，作为查询的左界即可
code
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cassert>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 600005;
int n, b[maxn];
struct BIT{
int t[maxn];
int lowbit(int x){return x & -x;}
void add(int x){
while(x <= n){
++t[x];
x += lowbit(x);
}
}
int query(int x){
int ans = 0;
while(x){
ans += t[x];
x -= lowbit(x);
}
return ans;
}
void clear(){
for(int i = 1; i <= n; ++i)t[i] = 0;
}
}t;
struct seg{
int t[maxn << 2 | 1];
void build(int x, int l, int r){
if(l == r){
t[x] = b[l];
return;
}
int mid = (l + r) >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
t[x] = max(t[x << 1], t[x << 1 | 1]);
}
int query(int x, int l, int r, int L, int R, int val){
if(t[x] <= val)return n + 1;
if(l == r)return l;
int mid = (l + r) >> 1;
if(L <= l && r <= R){
if(t[x << 1] > val)return query(x << 1, l, mid, L, R, val);
return query(x << 1 | 1, mid + 1, r, L, R, val);
}
int res = n + 1;
if(L <= mid && t[x << 1] > val)res = query(x << 1, l, mid, L, R, val);
if(res == n + 1 && R > mid && t[x << 1 | 1] > val)res = query(x << 1 | 1, mid + 1, r, L, R, val);
return res;
}
}T;
int las[maxn], cnt[maxn];
void solve(){
n = read();
for(int i = 1; i <= n; ++i)b[i] = read();
ll ans = 0; int mi = 0x3f3f3f3f;
T.build(1, 1, n);
for(int i = 1; i <= n; ++i){
ans += t.query(b[i] - 1);
ans += cnt[i];
mi = min(mi, b[i]);
int pos = max(i, las[mi]) + 1;
if(pos <= n){pos = T.query(1, 1, n, pos, n, mi); ++cnt[pos];}
las[mi] = pos;
if(t.query(b[i]) == t.query(b[i] - 1))t.add(b[i]);
printf("%lld ",ans);
}
printf("\n");
for(int i = 1; i <= n + 5; ++i)las[i] = cnt[i] = 0;
t.clear();
}
signed main(){
freopen("function.in","r",stdin);
freopen("function.out","w",stdout);
int t = read();
for(int i = 1; i <= t; ++i)solve();
return 0;
}
C. 小 W 与骑士
如果平行，坐标压成一维搞
不平行，根据平面向量基本定理得到唯一解
然后用组合数算方案数，对障碍点进行容斥，减去其他障碍点到自己的方案
https://www.cnblogs.com/MaxQAQ/p/16051258.html
code
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cassert>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read(){
int x = 0;bool f = 0; char c = getchar();
while(!isdigit(c)){f = c == '-'; c = getchar();}
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return f ? -x : x;
}
const int mx = 1e6, mod = 1e9 + 7, maxn = 1e6 + 55;
int qpow(int x, int y){
int ans = 1;
for(; y; y >>= 1, x = 1ll * x * x % mod)if(y & 1)ans = 1ll * ans * x % mod;
return ans;
}
int fac[maxn], ifac[maxn];
int c(int n, int m){return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;}
int f[2005], f1[2005];
bool vis[2005], flag[2005];
int x, y, k, ax, ay, bx, by;
struct node{int x, y;}d[maxn];
int calc(int x, int y){
int p, q;
q = (1ll * ax * y - 1ll * ay * x) / (1ll * ax * by - 1ll * bx * ay);
if(1ll * q * (1ll * ax * by - 1ll * bx * ay) != (1ll * ax * y - 1ll * ay * x))return 0;
p = (x - q * bx) / ax;
if(p * ax != x - q * bx || p < 0 || q < 0) return 0;
return c(p + q, p);
}
int dfs(int x){
if(vis[x])return f[x];
vis[x] = 1;
int res = calc(d[x].x, d[x].y);
if(res == 0)return f[x] = 0;
for(int i = 1; i <= k; ++i)if(i != x){
int nx = d[x].x - d[i].x;
int ny = d[x].y - d[i].y;
int v = calc(nx, ny);
if(v == 0)continue;
res = (res - 1ll * v * dfs(i) % mod + mod) % mod;
}
return f[x] = res;
}
void px(){
memset(flag,0,sizeof(flag));memset(f1,0,sizeof(f1));
if(ax * bx < 0){
printf("-1\n");
return;
}
if(ax < 0){
x = -x, y = -y, ax = -ax,ay = -ay, bx = -bx, by = -by;
for(int i = 1; i <= k; ++i)
d[i].x = -d[i].x, d[i].y = -d[i].y;
}
for(int i = 1; i < k; ++i)if(d[i].x > 0){
if(1ll * ay * d[i].x == 1ll * d[i].y * ax)flag[d[i].x] = 1;
}
f1[0] = 1;
for(int i = 0; i <= x; ++i)if(!flag[i]){
f1[i + ax] = (f1[i + ax] + f1[i]) % mod;
if(ax != bx)f1[i + bx] = (f1[i + bx] + f1[i]) % mod;
}
printf("%d\n",f1[x]);
}
void solve(){
x = read(), y = read(), k = read();
ax = read(); ay = read(); bx = read(); by = read();
for(int i = 1; i <= k; ++i)d[i].x = read(), d[i].y = read();
d[++k] = {x, y};
if(ax == 0 && ay){
swap(ax, ay); swap(bx, by); swap(x, y);
for(int i = 1; i <= k; ++i)swap(d[i].x, d[i].y);
}
if(1ll * ay * bx == 1ll * by * ax){
if(1ll * y * ax == 1ll * ay * x)px();
else printf("0\n");
return;
}
memset(f,0,sizeof(f));
memset(vis,0,sizeof(vis));
printf("%d\n",dfs(k));
}
int main(){
freopen("knight.in","r",stdin);
freopen("knight.out","w",stdout);
fac[0] = ifac[0] = 1; for(int i = 1; i <=mx; ++i)fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[mx] = qpow(fac[mx], mod - 2); for(int i = mx - 1; i > 0; --i)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
int t = read(); for(int i = 1; i <= t; ++i)solve();
return 0;
}
省选模拟之辞旧迎新3
A. 异或矩阵
通过观察性质发现某一位的值是他向上 \(2^x\) 行开始的 \(2^x\) 项的异或
那么得到那一行，前缀异或可以快速得到当前行
发现这个过程可以递归，次数类似快速幂
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
uint read(){
uint x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 3e6 + 5;
uint n, k, a[maxn], tmp[maxn], ans;
void sol(int k){
if(k == 1)return;
int h = 1; while(h + h <= k)h += h;
int l = k - h + 1; sol(l);
for(int i = 1; i <= n - l + 1; ++i)a[i] ^= a[i - 1];
for(int i = 1; i <= n - k + 1; ++i)tmp[i] = a[i - 1] ^ a[i + h - 1];
for(int i = 1; i <= n - k + 1; ++i)a[i] = tmp[i];
}
int main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
n = read(), k = read(); a[1] = read();
for(int i = 2; i <= n; ++i)a[i] = (1145141 * a[i - 1] + 1919 * i + 810);
sol(k);
uint ans = 0;
for(int i = 1; i <= n - k + 1; ++i){
ans = (ans + i * (i ^ a[i]));
}
printf("%u\n",ans);
return 0;
}
B. 树
简单容斥题，考场傻逼了，写的相对复杂一些
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 3e5 + 55, mod = 998244353;
int n, si[maxn], p2[maxn], ans[maxn];
vector<int>g[maxn];
void add(int &x, int y){x += y; if(x >= mod)x -= mod;}
void dfs(int x, int fa){
si[x] = 1;
for(int v : g[x])if(v != fa){
dfs(v, x); si[x] += si[v];
}
int sum = si[x];
for(int v : g[x])if(v != fa){
sum -= si[v];
add(ans[x], 1ll * (p2[si[v]] - 1) * (p2[sum] - 1) % mod);
}
add(ans[x], 1);
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n = read();
for(int i = 1; i < n; ++i){
int u = read(), v = read();
g[u].push_back(v);
g[v].push_back(u);
}
p2[0] = 1; for(int i = 1; i <= n; ++i)p2[i] = (p2[i - 1] + p2[i - 1]) % mod;
dfs(1, 0);
for(int i = 1; i <= n; ++i)printf("%d\n",(ans[i] % mod + mod) % mod);
return 0;
}
C. 黑白树
因为有链加子树加这些，考虑使用树剖
那么问题在于如何维护同色连通块
发现对于在同一同色连通块内的点，他们的异色祖先数量相同
于是在线段树的每个区间都维护与区间内所有点 \(lca\) 异色祖先数量相同的信息
于是在进行 \(2 / 3\) 操作时找到当前连通块深度最小的点，对他对应的区间进行修改与查询
具体的维护 \(cnt[2], ctag[2], mx[2], mtag[2], tag\) 表示区间 \(lca\) 两种颜色祖先数量及标记，与区间 \(lca\) 在同一连通块内的点的最大值及标记，区间加标记
特殊标记只对同一连通块内的区间下传
参考博客
https://www.cnblogs.com/siriehn-nx/p/16061623.html
code
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int read(){
int x = 0; bool f = 0; char c = getchar();
while(!isdigit(c)){f = c == '-'; c = getchar();}
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return f ? -x : x;
}
const int maxn = 200005, inf = 0x3f3f3f3f;
int n, m, col[maxn], val[maxn];
vector<int>g[maxn];
int fa[maxn], dep[maxn], si[maxn], son[maxn], dfn[maxn], dfnr[maxn], top[maxn], id[maxn], tim;
struct seg{
struct node{int cnt[2], ctag[2], mx[2], mtag[2], tag;}t[maxn << 2 | 1];
void add_cnt(int x, int col, int val){t[x].cnt[col] += val; t[x].ctag[col] += val;}
void add_mx(int x, int col, int val){t[x].mx[col] += val; t[x].mtag[col] += val;}
void add_all(int x, int val){t[x].mx[0] += val; t[x].mx[1] += val; t[x].tag += val;}
void push_up(int x){
t[x].mx[0] = max(t[x << 1].cnt[1] == t[x].cnt[1] ? t[x << 1].mx[0] : -inf, t[x << 1 | 1].cnt[1] == t[x].cnt[1] ? t[x << 1 | 1].mx[0] : -inf);
t[x].mx[1] = max(t[x << 1].cnt[0] == t[x].cnt[0] ? t[x << 1].mx[1] : -inf, t[x << 1 | 1].cnt[0] == t[x].cnt[0] ? t[x << 1 | 1].mx[1] : -inf);
}
void push_down(int x){
int ls = x << 1, rs = x << 1 | 1;
for(int i = 0; i < 2; ++i){
if(t[x].ctag[i]){add_cnt(ls, i, t[x].ctag[i]); add_cnt(rs, i, t[x].ctag[i]); t[x].ctag[i] = 0;}
if(t[x].mtag[i ^ 1]){
if(t[ls].cnt[i] == t[x].cnt[i])add_mx(ls, i ^ 1, t[x].mtag[i ^ 1]);
if(t[rs].cnt[i] == t[x].cnt[i])add_mx(rs, i ^ 1, t[x].mtag[i ^ 1]);
t[x].mtag[i ^ 1] = 0;
}
}
if(t[x].tag){add_all(ls, t[x].tag); add_all(rs, t[x].tag); t[x].tag = 0;}
}
void rev(int x, int l, int r, int pos){
if(l == r){swap(t[x].mx[0], t[x].mx[1]); return;}
push_down(x); int mid = (l + r) >> 1;
if(pos <= mid)rev(x << 1, l, mid, pos);
else rev(x << 1 | 1, mid + 1, r, pos);
push_up(x);
}
void modify_all(int x, int l, int r, int L, int R, int val){
if(L <= l && r <= R)return add_all(x, val);
push_down(x); int mid = (l + r) >> 1;
if(L <= mid)modify_all(x << 1, l, mid, L, R, val);
if(R > mid)modify_all(x << 1 | 1, mid + 1, r, L, R, val);
push_up(x);
}
void modify_cnt(int x, int l, int r, int L, int R, int col, int val){
if(L <= l && r <= R)return add_cnt(x, col, val);
push_down(x); int mid = (l + r) >> 1;
if(L <= mid)modify_cnt(x << 1, l, mid, L, R, col, val);
if(R > mid)modify_cnt(x << 1 | 1, mid + 1, r, L, R, col, val);
push_up(x);
}
void modify_mx(int x, int l, int r, int L, int R, int col, int cnt, int val){
if(t[x].cnt[col ^ 1] > cnt)return;
if(L <= l && r <= R)return add_mx(x, col, val);
push_down(x); int mid = (l + r) >> 1;
if(L <= mid)modify_mx(x << 1, l, mid, L, R, col, cnt, val);
if(R > mid)modify_mx(x << 1 | 1, mid + 1, r, L, R, col, cnt, val);
push_up(x);
}
int query_mx(int x, int l, int r, int L, int R, int col, int cnt){
if(t[x].cnt[col ^ 1] > cnt)return -inf;
if(L <= l && r <= R)return t[x].mx[col];
push_down(x); int mid = (l + r) >> 1, ans = -inf;
if(L <= mid)ans = max(ans, query_mx(x << 1, l, mid, L, R, col, cnt));
if(R > mid)ans = max(ans, query_mx(x << 1 | 1, mid + 1, r, L, R, col, cnt));
return ans;
}
int query_cnt(int x, int l, int r, int pos, int col){
if(l == r)return t[x].cnt[col];
push_down(x); int mid = (l + r) >> 1;
if(pos <= mid)return query_cnt(x << 1, l, mid, pos, col);
else return query_cnt(x << 1 | 1, mid + 1, r, pos, col);
}
}T;
void dfs1(int x){
si[x] = 1;
for(int v : g[x])if(v != fa[x]){
fa[v] = x; dep[v] = dep[x] + 1;
dfs1(v); si[x] += si[v];
if(si[son[x]] < si[v])son[x] = v;
}
}
set<pii>s[2][maxn];
void dfs2(int x, int tp){
id[dfn[x] = ++tim] = x; top[x] = tp;
if(son[x])dfs2(son[x], tp);
for(int v : g[x])if(v != fa[x] && v != son[x])dfs2(v, v);
dfnr[x] = tim;
}
int find(int x){
pii res; res.first = dep[x]; res.second = x; int c = !col[x];
for(; x; x = fa[top[x]]){
auto it = s[c][top[x]].upper_bound({dep[x], inf});
if(it != s[c][top[x]].begin()){
--it;
if((*it).first + 1 < res.first)res = {1 + (*it).first, son[(*it).second]};
break;
}
res = {dep[top[x]], top[x]};
}
return res.second;
}
void upd(int u, int v, int val){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]])swap(u, v);
T.modify_all(1, 1, n, dfn[top[u]], dfn[u], val);
u = fa[top[u]];
}
if(dep[u] > dep[v])swap(u, v);
T.modify_all(1, 1, n, dfn[u], dfn[v], val);
}
int main(){
freopen("astill.in","r",stdin);
freopen("astill.out","w",stdout);
n = read(), m = read();
for(int i = 1; i < n; ++i){
int u = read(), v = read();
g[u].push_back(v); g[v].push_back(u);
}
for(int i = 1; i <= n; ++i)col[i] = read();
for(int i = 1; i <= n; ++i)val[i] = read();
dfs1(1); dfs2(1, 1);
for(int i = 1; i <= n; ++i)s[col[i]][top[i]].insert({dep[i], i});
for(int i = 1; i <= n; ++i)T.modify_cnt(1, 1, n, dfn[i], dfnr[i], col[i], 1);
for(int i = 1; i <= n; ++i)T.modify_all(1, 1, n, dfn[i], dfn[i], val[i]);
for(int i = 1; i <= m; ++i){
int opt = read(), x = read();
if(opt == 1){
T.modify_cnt(1, 1, n, dfn[x], dfnr[x], col[x], -1);
s[col[x]][top[x]].erase({dep[x], x});
col[x] ^= 1;
s[col[x]][top[x]].insert({dep[x], x});
T.rev(1, 1, n, dfn[x]);
T.modify_cnt(1, 1, n, dfn[x], dfnr[x], col[x], 1);
}else if(opt == 2){
x = find(x);
T.modify_mx(1, 1, n, dfn[x], dfnr[x], col[x], T.query_cnt(1, 1, n, dfn[x], !col[x]), read());
}else if(opt == 3){
x = find(x);
printf("%d\n",T.query_mx(1, 1, n, dfn[x], dfnr[x], col[x], T.query_cnt(1, 1, n, dfn[x], !col[x])));
}else if(opt == 4){int y = read(); upd(x, y, read());
}else T.modify_all(1, 1, n, dfn[x], dfnr[x], read());
}
return 0;
}
省选模拟之辞旧迎新4
A. 逃离藏宝洞
随机走一边，查询，不对就退回去
错误两次就能确定正确方向，此时直接走上去
询问次数远小于步数的随机一次走 \(50\) 步左右，期望下正确
code
#include"escape.h"
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
mt19937 rd((ull)(new char) * (ull)(new char));
int sint(int l, int r){return uniform_int_distribution<>(l, r)(rd);}
int rdr(int from){
int t = sint(0, 2);
while(t == from)t = sint(0, 2);
return t;
}
int res(int x, int y){
if(x > y)swap(x, y);
if(x)return 0;
if(y == 2)return 1;
return 2;
}
void know1(int dep, int from){
int t1 = rdr(from), d1;
move(t1); d1 = query();
if(d1 == dep - 1){
move(t1);
move(t1 = res(from, t1));
}
know1(dep + 1, t1);
}
void solve1(){
int dep, ndep, tt = rdr(-1);
dep = query();
move(tt);
ndep = query();
if(ndep == dep - 1)move(tt), know1(dep, tt);
else know1(dep + 1, tt);
}
int l[100005], lim;
void move50(int from){
l[0] = from;
for(int i = 1; i <= lim; ++i)l[i] = rdr(l[i - 1]);
for(int i = 1; i <= lim; ++i)move(l[i]);
}
void ret(int x){
for(int i = lim; i > x; --i)move(l[i]);
}
void know1_50(int dep, int from){
int ndep;
move50(from);
ndep = query();
int cro = (lim - (dep - ndep)) / 2;
ret(cro);
if(cro == 50)know1_50(dep + 1, l[50]);
if(cro == 0){
move(res(from, l[1]));
know1_50(dep + 1, res(from, l[1]));
}else{
dep = dep + cro;
move(res(l[cro], l[cro + 1]));
know1_50(dep + 1, res(l[cro], l[cro + 1]));
}
}
void solve2(){
int dep, ndep; dep = query();
move50(-1); ndep = query();
int cro = (lim - (dep - ndep)) / 2;
ret(cro);
dep = dep + cro;
know1_50(dep, l[cro]);
}
void escape(int lm, int lq){
lim = 50;
if(lm == 1e7 && lq != 100002)solve2();
else solve1();
}
B. 序列划分
首先 \(DP\) 枚举最后一段
\(f_i = \sum _{j < i} f_j mex_{j, i}\)
套路的用线段树维护 \(mex\)
转换 \(DP\) 为刷表法
\(f_i mex_{i, j}-> [j > i] f_j\)
那么我们有区间覆盖和区间乘对应项两种操作，
首先确定一个顺序，由于区间覆盖会影响对应项，于是他后做
那么考虑如何合并标记，当区间乘发现该区间覆盖过，其实可以转换成加上定值
于是新维护一个加法标记即可
初始化令叶结点区间覆盖标记存在，那么下传标记就不用特判了
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c)) c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 1e6 + 55, mod = 998244353;
int n, a[maxn], mex[maxn], nxt[maxn], pos[maxn];
int f[maxn];
bool vis[maxn];
void add(int &x, int y){x += y; if(x >= mod) x -= mod;}
struct seg{
struct node{
int val, mex, mul, tag;
}t[maxn << 2 | 1];
void push_up(int x){t[x].mex = max(t[x << 1].mex, t[x << 1 | 1].mex);}
void push_down(int x){
int ls = x << 1, rs = x << 1 | 1;
if(t[x].mul){
if(t[ls].tag != -1)add(t[ls].val, 1ll * t[x].mul * t[ls].tag % mod);
else add(t[ls].mul, t[x].mul);
if(t[rs].tag != -1)add(t[rs].val, 1ll * t[x].mul * t[rs].tag % mod);
else add(t[rs].mul, t[x].mul);
t[x].mul = 0;
}
if(t[x].val){
add(t[ls].val, t[x].val);
add(t[rs].val, t[x].val);
t[x].val = 0;
}
if(t[x].tag != -1){
t[ls].tag = t[rs].tag = t[x].tag;
t[ls].mex = t[rs].mex = t[x].tag;
t[x].tag = -1;
}
}
void build(int x, int l, int r){
t[x].tag = -1;
if(l == r){t[x].mex = t[x].tag = mex[l]; return;}
int mid = (l + r) >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
push_up(x);
}
void modify_val(int x, int l, int r, int L, int R, int val){
if(L <= l && r <= R){
if(t[x].tag != -1) add(t[x].val, 1ll * t[x].tag * val % mod);
else add(t[x].mul, val);
return;
}
push_down(x); int mid = (l + r) >> 1;
if(L <= mid)modify_val(x << 1, l, mid, L, R, val);
if(R > mid)modify_val(x << 1 | 1, mid + 1, r, L, R, val);
}
void modify_mex(int x, int l, int r, int L, int R, int mex){
if(L <= l && r <= R){
t[x].mex = t[x].tag = mex;
return;
}
push_down(x); int mid = (l + r) >> 1;
if(L <= mid)modify_mex(x << 1, l, mid, L, R, mex);
if(R > mid)modify_mex(x << 1 | 1, mid + 1, r, L, R, mex);
push_up(x);
}
int find(int x, int l, int r, int val){
if(l == r)return l + (t[x].mex <= val);
push_down(x); int mid = (l + r) >> 1;
if(t[x << 1].mex > val)return find(x << 1, l, mid, val);
else return find(x << 1 | 1, mid + 1, r, val);
}
int query(int x, int l, int r, int pos){
if(l == r)return t[x].val;
push_down(x); int mid = (l + r) >> 1;
if(pos <= mid)return query(x << 1, l, mid, pos);
else return query(x << 1 | 1, mid + 1, r, pos);
}
}T;
int main(){
freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);
n = read(); for(int i = 1; i <= n; ++i)a[i] = read();
for(int i = 0; i <= n; ++i)pos[i] = n + 1;
for(int i = n; i >= 1; --i)if(a[i] <= n){
nxt[i] = pos[a[i]]; pos[a[i]] = i;
}
for(int i = 1; i <= n; ++i){
mex[i] = mex[i - 1];
if(a[i] <= n){
vis[a[i]] = true;
while(vis[mex[i]])++mex[i];
}
}
T.build(1, 1, n); T.modify_val(1, 1, n, 1, n, 1);
for(int i = 1; i < n; ++i){
if(a[i] <= n){
int pl = T.find(1, 1, n, a[i]);
if(pl < nxt[i])T.modify_mex(1, 1, n, pl, nxt[i] - 1, a[i]);
}
T.modify_val(1, 1, n, i + 1, n, T.query(1, 1, n, i));
}
printf("%d\n",T.query(1, 1, n, n));
return 0;
}
C. 重排列
https://www.luogu.com.cn/problem/AT_agc010_e
把不互质的两个数连边，形成一个图
操作的实质是先手对图定向，后手进行字典序最大的拓扑排序
那么先手的最优策略就是对每个连通块定向时，贪心的从最小点开始，按照顺序扫描边，优先走字典序小的边
后手策略就是用大根堆进行拓扑排序
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c)) c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 2005;
bool vis[maxn];
int n, a[maxn], deg[maxn];
vector<int>g[maxn];
priority_queue<int>q;
void dfs(int x){
vis[x] = true;
for(int i = 1; i <= n; ++i)
if(!vis[i] && __gcd(a[i], a[x]) != 1){
++deg[i]; g[x].push_back(i); dfs(i);
}
}
int main(){
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
n = read(); for(int i = 1; i <= n; ++i)a[i] = read();
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; ++i)if(!vis[i])dfs(i);
for(int i = 1; i <= n; ++i)if(deg[i] == 0)q.push(i);
while(!q.empty()){
int x = q.top(); q.pop();
printf("%d ",a[x]);
for(int v : g[x])q.push(v);
}
return 0;
}