考试总结

估：100 + 100 + 30 + 100

实：100 + 100 + 50 + 100 rk1

1 年前的 max ak 了。 /bx

演出

小柯共有 \(n\) 个朋友，所有朋友编号为 \(1\) 到 \(n\) ，当且仅当小柯给了第 \(i\) 个朋友门票或编号为 \([l_i, r_i]\) 中的朋友中至少有一人去了，第 \(i\) 个朋友才会去。小柯希望所有朋友都能来看，请问小柯至少要给多少人门票呢？ \(n \le 5 \times 10 ^ 5\)

做法很显然。将 \([l_i, r_i]\) 中的点对 \(i\) 连边，最终求一边塔尖。我们发现最后没有入度的强联通分量显然一定会占用一张票，直接数即可。线段树优化建图可以做到 \(O(n \log n)\)，做完了。

#include 
using namespace std;
#define int int
#define ll long long
#define usd unsigned
#define el putchar('\n')
#define lowbit(x) (x & (-x))
#define AC return 
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define void inline void
#define il inline
#define Mod(x) (((x) % mod + mod) % mod)
#define pii pair 
#define pll pair 
il char gc() { char c; while((c = getchar()) <= ' ') ; return c; }
il int rd() {char c; int x, f = 1;while(!isdigit(c = getchar())) if(c == '-') f *= -1;x = c ^ 48;while(isdigit(c = getchar())) x = (x << 3) + (x << 1) + (c ^ 48);return x * f;
}
void ACehomoxue();
signed main() {srand(time(0));// freopen("performance.in", "r", stdin);// freopen("performance.out", "w", stdout);int t = 1;// t = rd();while(t--) ACehomoxue();AK;
}
const int mod = 998244353, maxn = 2 * 1e6 + 18;int n, ans = 0;vector  vec[maxn];
vector  e;
void add(int u, int v) { vec[u].push_back(v); e.push_back({u, v}); }
int tot;
class xds {struct tree {int l, r, id;} t[maxn << 2];
public:void build(int i, int l, int r) {t[i].l = l, t[i].r = r, t[i].id = ++tot;if(l == r) {add(l, t[i].id);AC;}int mid = l + r >> 1;build(i << 1, l, mid);build(i << 1 | 1, mid + 1, r);add(t[i << 1].id, t[i].id);add(t[i << 1 | 1].id, t[i].id);}void updata(int i, int l, int r, int x) {if(t[i].l >= l && t[i].r <= r) {add(t[i].id, x);AC;}int mid = t[i].l + t[i].r >> 1;if(l <= mid) updata(i << 1, l, r, x);if(r > mid) updata(i << 1 | 1, l, r, x);}
} ds;int be[maxn], dfn[maxn], dn, low[maxn], m, in[maxn];
vector  stk;
bool vis[maxn];
void tarjan(int x) {vis[x] = true;stk.push_back(x);dfn[x] = low[x] = ++dn;for(int to : vec[x]) {if(vis[to]) low[x] = min(low[x], dfn[to]);if(!dfn[to]) {tarjan(to);low[x] = min(low[x], low[to]);} }if(dfn[x] == low[x]) {  be[x] = ++m;vis[x] = false;while(stk.back() != x) {int i = stk.back();be[i] = m;vis[i] = false;stk.pop_back();}stk.pop_back();}
}queue  qu;void ACehomoxue() {n = rd();tot = n;ds.build(1, 1, n);for(int i = 1, l, r; i <= n; i++) {l = rd(), r = rd();ds.updata(1, l, r, i);}for(int i = 1; i <= tot; i++) if(!dfn[i]) tarjan(i);for(pii tmp : e) {int u = be[tmp.first], v = be[tmp.second];if(u == v) continue;in[v]++;}for(int i = 1; i <= m; i++) if(!in[i]) ans++;cout << ans;el;
}   

指挥

改编自：P12846

把原题中的改变硬币翻面换成了全部翻上来或翻下去。

我们考虑全是操作全翻转和查询那么就是区间修改线段树，加上 \(l + 2k\) 或 \(l + 3k\)，我们将每个数按照对 \(6\) 取模后的余数分类，类似开 \(6\) 个线段树，我们发现就可以将其全部转化为只有全翻转和全查询。做完了。

#include 
using namespace std;
#define int int
#define ll long long
#define usd unsigned
#define el putchar('\n')
#define lowbit(x) (x & (-x))
#define AC return 
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define void inline void
#define il inline
#define Mod(x) (((x) % mod + mod) % mod)
#define pii pair 
#define pll pair 
il char gc() { char c; while((c = getchar()) <= ' ') ; return c; }
il int rd() {char c; int x, f = 1;while(!isdigit(c = getchar())) if(c == '-') f *= -1;x = c ^ 48;while(isdigit(c = getchar())) x = (x << 3) + (x << 1) + (c ^ 48);return x * f;
}
void ACehomoxue();
signed main() {srand(time(0));// freopen("command.in", "r", stdin);// freopen("command.out", "w", stdout);int t = 1;// t = rd();while(t--) ACehomoxue();AK;
}
const int mod = 998244353, maxn = 5 * 1e5 + 18;class xds {struct tree {int l, r, c[6], t[6], f[6];} t[maxn << 2];void push_up(int i) {for(int j = 0; j < 6; j++) {t[i].c[j] = t[i << 1].c[j] + t[i << 1 | 1].c[j];}}#define mdf(i, j, x) t[i].f[j] = x; t[i].c[j] = t[i].t[j] * x;void push_down(int i) {for(int j = 0; j < 6; j++) {if(t[i].f[j] == -1) continue;mdf(i << 1, j, t[i].f[j]);mdf(i << 1 | 1, j, t[i].f[j]);t[i].f[j] = -1;}}
public:void build(int i, int l, int r) {t[i].l = l, t[i].r = r;for(int j = 0; j < 6; j++) t[i].c[j] = 0, t[i].f[j] = -1;if(l == r) {t[i].t[l % 6] = 1;AC;}int mid = l + r >> 1;build(i << 1, l, mid);build(i << 1 | 1, mid + 1, r);for(int j = 0; j < 6; j++) t[i].t[j] = t[i << 1].t[j] + t[i << 1 | 1].t[j];}void updata(int i, int l, int r, int j, int x) {if(t[i].l >= l && t[i].r <= r) {mdf(i, j, x);AC;}push_down(i);int mid = t[i].l + t[i].r >> 1;if(l <= mid) updata(i << 1, l, r, j, x);if(r > mid) updata(i << 1 | 1, l, r, j, x);push_up(i);}il int query(int i, int l, int r) {if(t[i].l >= l && t[i].r <= r) {int res = 0;for(int j = 0; j < 6; j++) res += t[i].c[j];return res;}push_down(i);int mid = t[i].l + t[i].r >> 1, res = 0;if(l <= mid) res += query(i << 1, l, r);if(r > mid) res += query(i << 1 | 1, l, r);return res;}
} ds;int n, q;void ACehomoxue() {n = rd(), q = rd();ds.build(1, 1, n);for(int opt, l, r, k; q--; ) {opt = rd(), l = rd(), r = rd();if(opt == 4) { cout << ds.query(1, l, r), el; continue; }k = rd();if(opt == 1) {for(int j = 0; j < 6; j++) {ds.updata(1, l, r, j, k);}}if(opt == 2) {for(int x = l; x <= l + 4; x += 2) {int j = x % 6;ds.updata(1, l, r, j, k);}}if(opt == 3) {for(int x = l; x <= l + 3; x += 3) {int j = x % 6;ds.updata(1, l, r, j, k);}}}
}

配对

原题：P12729 [KOI 2021 Round 2] 最长公共括号子串

#include 
using namespace std;
#define int int
#define ll long long
#define usd unsigned
#define el putchar('\n')
#define lowbit(x) (x & (-x))
#define AC return 
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define void inline void
#define il inline
#define Mod(x) (((x) % mod + mod) % mod)
#define pii pair 
#define pll pair 
il char gc() { char c; while((c = getchar()) <= ' ') ; return c; }
il int rd() {char c; int x, f = 1;while(!isdigit(c = getchar())) if(c == '-') f *= -1;x = c ^ 48;while(isdigit(c = getchar())) x = (x << 3) + (x << 1) + (c ^ 48);return x * f;
}
void ACehomoxue();
signed main() {srand(time(0));// freopen(".in", "r", stdin);// freopen(".out", "w", stdout);int t = 1;t = rd();while(t--) ACehomoxue();AK;
}
const int mod = 998244353, maxn = 2 * 1e6 + 18, maxk = 25;int n, m, a[maxn], Log[maxn], nxt[maxn][maxk], ans = 0;
il int get(int l, int r) {int k = Log[r - l + 1];return min(nxt[l][k], nxt[r - (1 << k) + 1][k]);
}
vector  pos[maxn];
string aa, bb;int tot = 0, from = 0, to = 0;
struct state {int link, len, pos;bool has1, has2;map  ch;void clr() { has1 = false, has2 = false; link = len = 0; ch.clear(); }
} s[maxn * 2];
vector  vec[maxn];
int ask[maxn];
void init() { for(; tot + 1; tot--) s[tot].clr(), vec[tot].clear(); tot = 0, from = 0, to = 0; s[0].link = -1; }
void insert(char c, int type, int id) {int i;if(c == '(') i = 0;else if(c == ')') i = 1;else i = 2;to = ++tot;s[to].pos = id;s[to].len = s[from].len + 1;int q = 0, clone = 0;for(int p = from; p != -1; p = s[p].link) {if(q) {if(s[p].ch[i] == q) { s[p].ch[i] = clone; continue; }else break;}if(!s[p].ch[i]) { s[p].ch[i] = to; continue; }q = s[p].ch[i];if(s[p].len + 1 == s[q].len) { s[to].link = q; break; }clone = ++tot;s[clone] = s[q];s[clone].len = s[p].len + 1;s[to].link = s[q].link = clone;s[p].ch[i] = clone;}from = to;if(type == 1) s[to].has1 = true;if(type == 2) s[to].has2 = true;
}
void dfs(int x) {for(int to : vec[x]) {dfs(to);s[x].has1 |= s[to].has1;s[x].has2 |= s[to].has2;}
}
void solve() {for(int i = 0; i <= tot; i++) {if(s[i].link != i) {vec[s[i].link].push_back(i);}}dfs(0);for(int p = 1; p <= tot; p++) {if(!s[p].has1 || !s[p].has2) continue;int i = s[p].pos, len = s[p].len;ask[i] = max(ask[i], len);}
}void ACehomoxue() {init(), ans = 0;cin >> aa >> bb;n = aa.length(), m = bb.length();Log[0] = -1;nxt[0][0] = 1e6;for(int i = 1; i <= n; i++) {Log[i] = Log[i / 2] + 1;if(aa[i - 1] == '(') a[i] = 1;else a[i] = -1;nxt[i][0] = nxt[i - 1][0] + a[i];}for(int k = 1; k < maxk; k++) {for(int i = 0; i + (1 << k) <= n + 1; i++) {nxt[i][k] = min(nxt[i][k - 1], nxt[i + (1 << k - 1)][k - 1]);}}for(int i = 1; i <= n; i++) insert(aa[i - 1], 1, i);insert('+', 0, 0);for(int i = 1; i <= m; i++) insert(bb[i - 1], 2, i);solve();pos[nxt[0][0]].push_back(0);for(int i = 1, sum, l, r; i <= n; i++) {sum = nxt[i][0];r = pos[sum].size() - 1, l = lower_bound(pos[sum].begin(), pos[sum].end(), i - ask[i]) - pos[sum].begin();ask[i] = 0;while(l <= r) {int mid = l + r >> 1, p = pos[sum][mid];if(get(p, i) >= sum) {ans = max(ans, i - p);r = mid - 1;} else l = mid + 1;}pos[sum].push_back(i);}for(int i = 0; i <= n; i++) pos[nxt[i][0]].clear();cout << ans;el;
}

台阶

原题：ReTravel

code