No Abstract.

T1

Des.

有一个初始为空的01序列, 支持以下操作:

在序列末尾添加一个0或1, 询问$[l, r]$所有区间前缀与非和的异或.

与非是把两个元素与起来再非, 并且只能按顺序做.

Sol.

一开始以为是一堆数与起来再非, 以为只要找一个0就行了, 怎么可能这么简单.

后来观察发现, 连续的1总表现为0101交替, 连续的0不必说, 全是1.

所以我们维护一个段, 两边维护极大连续1段, 再维护一个结果的异或值, 两边接起来的时候更新异或值.

最后出结果的时候也要讨论一下两边的连续1.

细节繁多(考场就不想写, 下来还是不想写只能膜膜膜).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e+6 + 5;

struct question {
int l, r, t;
}q[100005];
struct node {
int lmax, rmax;
unsigned short xrv, emp;
}t[maxn << 2][2];
unsigned short tag[maxn << 2];
int a[maxn], n, m, cnt, lstans;

inline int rd() {
register int x = 0, c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
return x;
}
inline void pushup(node &cur, node ls, node rs) {
cur.xrv = ls.xrv ^ rs.xrv;
if (ls.emp && rs.emp) {
cur.xrv ^= (((ls.rmax + rs.lmax) >> 1) & 1) ^ 1;
}
cur.emp = ls.emp | rs.emp;
cur.lmax = ls.lmax; cur.rmax = rs.rmax;
if (!ls.emp) cur.lmax += rs.lmax;
if (!rs.emp) cur.rmax += ls.rmax;
}
void build(int cur, int l, int r) {
if (l == r) {
if (a[l]) t[cur][0].lmax = t[cur][0].rmax = 1, t[cur][1].emp = 1;
else t[cur][1].lmax = t[cur][1].rmax = 1, t[cur][0].emp = 1;
return;
}
int mid = (l + r) >> 1;
build(cur << 1, l, mid);
build(cur << 1|1, mid + 1, r);
pushup(t[cur][0], t[cur << 1][0], t[cur << 1|1][0]);
pushup(t[cur][1], t[cur << 1][1], t[cur << 1|1][1]);
}
inline void tagon(int cur) {
swap(t[cur][0], t[cur][1]);
tag[cur] ^= 1;
}
inline void pushdown(int cur) {
if (tag[cur]) {
tagon(cur << 1); tagon(cur << 1|1);
tag[cur] = 0;
}
}
void modify(int cur, int l, int r, int L, int R) {
if (L <= l && r <= R) {
tagon(cur);
return;
}
pushdown(cur);
int mid = (l + r) >> 1;
if (L <= mid) modify(cur << 1, l, mid, L, R);
if (R > mid) modify(cur << 1|1, mid + 1, r, L, R);
pushup(t[cur][0], t[cur << 1][0], t[cur << 1|1][0]);
pushup(t[cur][1], t[cur << 1][1], t[cur << 1|1][1]);
}
node query(int cur, int l, int r, int L, int R) {
if (L == l && r == R) {
return t[cur][0];
}
pushdown(cur);
int mid = (l + r) >> 1;
if (R <= mid) return query(cur << 1, l, mid, L, R);
else if (L > mid) return query(cur << 1|1, mid + 1, r, L, R);
else {
node ret = (node){0, 0, 0, 0};
pushup(ret, query(cur << 1, l, mid, L, mid), query(cur << 1|1, mid + 1, r, mid + 1, R));
return ret;
}
}

int main() {
n = rd();
int opt, x, y;
for (int i = 1; i <= n; ++i) {
opt = rd();
if (opt == 1) {
x = rd();
a[++m] = x;
} else {
x = rd(); y = rd();
q[++cnt] = (question){x, y, m};
}
}
build(1, 1, m);
for (int i = 1; i <= cnt; ++i) {
if (lstans) {
q[i].l = q[i].t - q[i].l + 1;
q[i].r = q[i].t - q[i].r + 1;
swap(q[i].l, q[i].r);
}
if (!a[q[i].l]) q[i].l++;
if (q[i].l > q[i].r) lstans = 0;
else {
node res = query(1, 1, m, q[i].l, q[i].r);
if (!res.emp) {
lstans = (((q[i].r - q[i].l) >> 1) & 1) ^ 1;
} else {
//puts("emp");
lstans = (((res.lmax + 1) >> 1) & 1) ^ res.xrv ^ (((res.rmax >> 1) & 1) ^ 1);
}
}
printf("%d\n", lstans);
if (lstans) {
if (q[i].t + 1 <= q[i + 1].t)
modify(1, 1, m, q[i].t + 1, q[i + 1].t);
for (int j = q[i].t + 1; j <= q[i + 1].t; ++j)
a[j] ^= 1;
}

}
return 0;
}

T2

Des.

Sol.

推导过长, 一会补.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define mod 998244353

using namespace std;
typedef long long ll;

const int maxn = 5e+5 + 5;

int n, m, cnt;
int npr[maxn], u[maxn], pr[maxn >> 1], N = 5e+5;
ll uid[maxn], h[maxn], l[maxn], f[maxn], s[maxn];

void euler() {
u[1] = 1; uid[1] = 1;
for (int i = 2; i <= N; ++i) {
if (!npr[i]) {
pr[++cnt] = i; u[i] = -1;
uid[i] = (u[i] * i + mod) % mod;
}
for (int j = 1; j <= cnt && i * pr[j] <= N; ++j) {
npr[i * pr[j]] = 1;
if (!(i % pr[j])) {
u[i * pr[j]] = 0;
uid[i * pr[j]] = 0;
break;
}
u[i * pr[j]] = -u[i];
uid[i * pr[j]] = (u[i * pr[j]] * (i * pr[j]) % mod + mod) % mod;
}
}
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
inline ll H(int y) {
ll sum = 0;
for (int dj = 1; dj <= m / y; ++dj)
if (gcd(dj, y) == 1) sum = (sum + uid[dj]) % mod;
sum = (sum * u[y] % mod + mod) % mod;
return sum;
}

int main() {
euler();
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) h[i] = H(i);
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= m; j += i)
l[i] = (h[j] + l[i]) % mod;
}
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; j += i)
f[j] = (f[j] + u[i] * l[i] % mod + mod) % mod;
}
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; j += i) {
s[j] = (s[j] + u[j] * i * f[i] % mod + mod + mod) % mod;
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i)
ans = (ans + s[i] + mod) % mod;
printf("%lld\n", ans);
return 0;
}

T3

Des.

平面上有若干个点, 每次询问一个点, 求最小的$k$, 使得底边平行于$x$轴, 边长为$k$的正三角形能包含至少$s$个点.

Sol.

一定是二分答案. 问题是如何Check.

二维数点问题是解决矩形的, 似乎不太好用. 我们做一下转化.

考虑一个三角形, 左下和右下顶点的坐标为$(x_0, y_0), (x_0 + L, y_0)$,以及一个单点$(x,y)$, 控制点的关系使得单点在三角形内, 得到三个不等式, $(-y, y - \sqrt{3}x.y+\sqrt{3}x)$满足小于即合法, 可以三维数点, 每次二分边长即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#pragma GCC optimize("Ofast", "inline")
#include <bits/stdc++.h>

using namespace std;
typedef double db;

const int maxn = 3e+4 + 5;
const db fac = sqrt(3.0);
const db eps = 1e-5;

int d;
struct Point {
db coe[3];
db& operator[](int x) {
return coe[x];
}
}pts[maxn];
struct KDNode {
db p[3], mn[3], mx[3];
int ch[2], sum;
KDNode() {}
KDNode(int x) {
for (int i = 0; i < 3; ++i)
p[i] = mn[i] = mx[i] = pts[x].coe[i];
ch[1] = ch[0] = 0;
}
}t[maxn];

int n, m, k, x[maxn], y[maxn], rt, tot;
db qry[3];

inline int DCMP(db x, db y) {
db tmp = x - y;
return tmp < -eps ? -1 : tmp > 0;
}
inline bool cmp(Point lhs, Point rhs) {
if (d == 1) {
return lhs[0] < rhs[0];
} else if (d == 2) {
return lhs[1] < rhs[1];
} else {
return lhs[2] < rhs[2];
}
}

inline int rd() {
register int x = 0, c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
return x;
}
#define ls t[cur].ch[0]
#define rs t[cur].ch[1]
inline void pushup(const int &x, const int &y) {
for (int i = 0; i < 3; ++i) {
t[x].mn[i] = min(t[x].mn[i], t[y].mn[i]);
t[x].mx[i] = max(t[x].mx[i], t[y].mx[i]);
}
t[x].sum += t[y].sum;
}
int build(int l, int r, int dim) {
int cur = ++tot;
int mid = (l + r) >> 1;
d = dim;
nth_element(pts + l, pts + mid, pts + r, cmp);
t[cur] = KDNode(mid); t[cur].sum = 1;
if (l < mid) ls = build(l, mid - 1, (dim + 1) % 3), pushup(cur, ls);
if (r > mid) rs = build(mid + 1, r, (dim + 2) % 3), pushup(cur, rs);
return cur;
}
inline bool CheckAllIn(const int &x, db *qe) {
for (int i = 0; i < 3; ++i) {
if (DCMP(t[x].mx[i], qe[i]) > 0) return false;
}
return true;
}
inline bool CheckPartIn(const int &x, db *qe) {
for (int i = 0; i < 3; ++i) {
if (DCMP(t[x].mn[i], qe[i]) > 0) return false;
}
return true;
}
inline bool CheckSinglePoints(const int &x, db *qe) {
for (int i = 0; i < 3; ++i) {
if (DCMP(t[x].p[i], qe[i]) > 0) return false;
}
return true;
}

int query(int cur, db *qe) {
if (CheckAllIn(cur, qe)) return t[cur].sum;
int res = CheckSinglePoints(cur, qe) ? 1 : 0;
if (ls && CheckPartIn(ls, qe)) res += query(ls, qe);
if (rs && CheckPartIn(rs, qe)) res += query(rs, qe);
return res;
}

int main() {
n = rd(); m = rd(); k = rd();
for (int i = 1; i <= n; ++i) {
x[i] = rd(); y[i] = rd();
pts[i].coe[0] = -y[i];
pts[i].coe[1] = y[i] - fac * x[i];
pts[i].coe[2] = y[i] + fac * x[i];
}
rt = build(1, n, 0);
while (m--) {
x[0] = rd(); y[0] = rd();
qry[0] = -y[0];
qry[1] = y[0] - fac * x[0];
int L = 0, R = 1e8, ans = -1;
while (L <= R) {
int mid = (L + R) >> 1;
qry[2] = y[0] + fac * (x[0] + mid);
if (query(rt, qry) >= k) {
ans = mid;
R = mid - 1;
} else L = mid + 1;
}
printf("%d\n", ans);
}
return 0;
}