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;
}