三年之后第一次打比赛，用小号打了场 \(Div.3\) ，居然没有AK，感觉实力退步到小学了。
A. How Much Does Daytona Cost?
若只判断题，只要判断 \(\{ a_n \}\) 中是否存在 \(k\) 即可。
B. Aleksa and Stack
构造方法不唯一，我直接输出奇数列，显然正确。
C. Vasilije in Cacak
若只判断题，只要判断前 \(k\) 个数的和会不会超过 \(x\) ，以及后 \(k\) 个数的和会不会小于 \(x\) 就行了。
D. Reverse Madness
易知 \(\{ r_n \}\) 单调增， 故可以二分 \(x\) 的位置。至于调换操作直接用一颗平衡树解决就行了。
const int Maxn = 2e5 + 5;
int T, n, k, q, l[Maxn], r[Maxn], x[Maxn];
char str[Maxn];
struct FHQTreap {
int lson[Maxn], rson[Maxn], data[Maxn], tag[Maxn];
int rnd[Maxn], sze[Maxn], seed, root, tot;
FHQTreap(void) {
Ms(lson, 0), Ms(data, 0), Ms(tag, 0);
Ms(sze, 0), Ms(rnd, 0), root = 0;
Ms(rson, 0), tot = 0, seed = 1;
}
void clear(void) {
root = 0, tot = 0, seed = 1;
}
inline int _rand(void) { return seed *= 482711; }
inline int newnode(int val) { tot++; data[tot] = val, rnd[tot] = _rand(), sze[tot] = 1, lson[tot] = rson[tot] = 0, tag[tot] = 0; return tot; }
inline void pushup(int pos) { sze[pos] = sze[lson[pos]] + sze[rson[pos]] + 1; }
inline void pushdown(int pos) {
if (!pos || !tag[pos]) return;
swap(lson[pos], rson[pos]);
tag[lson[pos]] ^= 1, tag[rson[pos]] ^= 1;
tag[pos] = 0; return;
}
inline void split(int pos, int val, int &x, int &y) {
if (!pos) { x = y = 0; return; } pushdown(pos);
if (sze[lson[pos]] + 1 <= val) x = pos, split(rson[pos], val - sze[lson[pos]] - 1, rson[pos], y);
else y = pos, split(lson[pos], val, x, lson[pos]); pushup(pos);
}
inline int merge(int x, int y) {
if (!x || !y) return x + y; pushdown(x), pushdown(y);
if (rnd[x] < rnd[y]) return rson[x] = merge(rson[x], y), pushup(x), x;
else return lson[y] = merge(x, lson[y]), pushup(y), y;
}
inline void insert(int val) {
int x, y, pos = newnode(val);
split(root, val, x, y);
root = merge(merge(x, pos), y);
}
inline void remove(int val) {
int x, y, z;
split(root, val - 1, x, y);
split(y, val, y, z); if (!y) return;
y = merge(lson[y], rson[y]);
root = merge(merge(x, y), z);
}
inline void reverse(int l, int r) {
int x, y, z;
split(root, r, x, y);
split(x, l - 1, x, z);
tag[z] ^= 1; root = merge(merge(x, z), y);
}
inline void search(int pos) {
if (!pos) return;
pushdown(pos);
search(lson[pos]);
putchar(str[data[pos]]);
search(rson[pos]);
}
} treap;
signed main(void) {
// ios :: sync_with_stdio(false);
read(T); while (T--) {
read(n), read(k); readstr(str + 1);
treap.clear(); for (int i = 1; i <= n; i++) treap.insert(i);
for (int i = 1; i <= k; i++) read(l[i]);
for (int i = 1; i <= k; i++) read(r[i]);
read(q);
for (int i = 1; i <= q; i++) {
read(x[i]);
int m = lower_bound(r + 1, r + k + 1, x[i]) - r;
int L = min(x[i], l[m] + r[m] - x[i]),
R = max(x[i], l[m] + r[m] - x[i]);
treap.reverse(L, R);
// reverse(str + L, str + R + 1);
}
treap.search(treap.root); putchar('\n');
}
// fwrite(pf, 1, o1 - pf, stdout);
return 0;
}
当然更简单的方法是打交换标记，贴一段 \(jiangly\) 的代码：
void solve() {
int n, k;
std::cin >> n >> k;
std::string s;
std::cin >> s;
std::vector<int> l(k), r(k);
for (int i = 0; i < k; i++) {
std::cin >> l[i];
l[i]--;
}
for (int i = 0; i < k; i++) {
std::cin >> r[i];
r[i]--;
}
int q;
std::cin >> q;
std::vector<int> f(n);
while (q--) {
int x;
std::cin >> x;
x--;
f[x] ^= 1;
}
for (int i = 0; i < k; i++) {
int rev = 0;
for (int j = l[i]; j <= l[i] + r[i] - j; j++) {
rev ^= f[j] ^ f[l[i] + r[i] - j];
if (rev) {
std::swap(s[j], s[l[i] + r[i] - j]);
}
}
}
std::cout << s << "\n";
}
E. Iva & Pav
考试时候脑子坏了，写了两个log的做法。实际上用ST表维护区间按位与和就行。
贴一段脑残二分线段树做法：
const int Maxn = 2e5 + 5;
int T, n, a[Maxn], q, k;
struct SegmentTree {
int t[Maxn << 2];
SegmentTree(void) { Ms(t, 0); }
void clear(void) { Ms(t, 0); }
inline void pushup(int pos) { t[pos] = t[pos << 1] & t[pos << 1 | 1]; }
inline void build(int pos, int l, int r) {
if (l == r) return (void) (t[pos] = a[l]);
int mid = l + r >> 1;
build(pos << 1, l, mid);
build(pos << 1 | 1, mid + 1, r);
pushup(pos);
}
inline int query(int pos, int l, int r, int L, int R) {
if (L <= l && R >= r) return t[pos];
int mid = l + r >> 1, ret = INT_MAX;
if (L <= mid) ret &= query(pos << 1, l, mid, L, R);
if (R > mid) ret &= query(pos << 1 | 1, mid + 1, r, L, R);
return ret;
}
} sgt;
inline int check(int x, int y) {
int l = x, r = y, ans = x;
while (l <= r) {
int mid = l + r >> 1;
if (sgt.query(1, 1, n, x, mid) >= k) l = mid + 1, ans = mid;
else r = mid - 1;
} return ans;
}
signed main(void) {
int l;
for (read(T); T; T--) {
read(n);
for (int i = 1; i <= n; i++) read(a[i]);
sgt.build(1, 1, n); read(q);
for (int i = 1; i <= q; i++) {
read(l), read(k);
if (a[l] < k) {
writeln(-1, i == q ? '\n' : ' ');
} else {
int r = check(l, n);
writeln(r, i == q ? '\n' : ' ');
}
}
}
// fwrite(pf, 1, o1 - pf, stdout);
return 0;
}
F. Vasilije Loves Number Theory
由题意知只要满足 \(n \equiv 0 \pmod{d(n)}\) 就存在满足条件的 \(a\) 可是累乘 \(x\) 会导致 \(n\) 爆炸，所以记录当前的唯一分解的指数，并时刻保持取余运算：
int T, q, n;
const int Maxn = 1e6 + 5;
int prime[80000], cnt;
int vis[Maxn], d, sum[Maxn];
inline void doit(int x, int t = 1) {
while (x > 1) {
int p = vis[x];
x /= p;
d /= sum[p] + 1;
sum[p] += t;
d *= sum[p] + 1;
}
}
vector <int> vec;
signed main(void) {
vis[1] = 0; d = 1;
for (int i = 2, upEdge = 1e6 + 1; i <= upEdge; i++) {
if (!vis[i]) prime[++cnt] = i, vis[i] = i;
for (int j = 1; j <= cnt; j++) {
if (i > upEdge / prime[j]) break;
vis[i * prime[j]] = prime[j];
if (prime[j] == vis[i]) break;
}
}
for (read(T); T; T--) {
read(n), read(q); vec.push_back(n); doit(n);
for (int opt, x; q; q--) {
read(opt);
if (opt == 1) {
read(x); vec.push_back(x); doit(x);
int ret = 1;
for (auto v : vec) ret = 1ll * ret * v % d;
if (ret != 0) {
puts("NO");
} else {
puts("YES");
}
} else {
while (vec.size() > 1) doit(vec.back(), -1), vec.pop_back();
puts("");
}
}
while (!vec.empty()) doit(vec.back(), -1), vec.pop_back();
}
// fwrite(pf, 1, o1 - pf, stdout);
return 0;
}
G. wxhtzdy ORO Tree
赛时没来得及想出来，先鸽了，咕咕咕。
标签：900,int,void,pos,tot,Codeforces,Maxn,vec,Div From： https://www.cnblogs.com/EternalEpic/p/18379185