并查集

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
struct UF {
  vector<int> fa, sz;
  int n, comp_cnt;

  UF(int _n): n(_n), comp_cnt(_n), fa(_n), sz(_n, 1) {
    iota(fa.begin(), fa.end(), 0);
  }

  int find(int x) {
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
  }

  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    if (sz[x] < sz[y]) {
      swap(x, y);
    }
    fa[y] = x;
    sz[x] += sz[y];
    --comp_cnt;
    return true;
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

树状数组

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
template<class T> struct Fenwick {
  int _n;
  vector<T> data;

  Fenwick() : _n(0) {}
  Fenwick(int n) : _n(n), data(n) {}

  void add(int i, T x) {
    assert(0 <= i && i < _n);
    i++;
    while (i <= _n) {
      data[i - 1] += x;
      i += i & -i;
    }
  }

  T sum(int l, int r) {
    assert(0 <= l && l <= r && r < _n);
    return sum(r) - sum(l - 1);
  }

  T sum(int i) {
    T s = 0;
    i++;
    while (i > 0) {
      s += data[i - 1];
      i -= i & -i;
    }
    return s;
  }
};

一维RMQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int ST[MAX][25], a[MAX], logn[MAX], n, m;

void init_ST() {
  logn[1] = 0; logn[2] = 1;
  for (int i = 3; i <= n; i++) logn[i] = logn[i / 2] + 1;
  for (int i = 1; i <= n; i++) ST[i][0] = a[i];
  for (int j = 1; j <= logn[n]; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      ST[i][j] = max(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
    }
  }
}

int RMQ(int l, int r) {
  int s = logn[r - l + 1];
  return max(ST[l][s], ST[r - (1 << s) + 1][s]);
}

二维RMQ

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
int ST[MAX][MAX][9][9], a[MAX][MAX], n, m;
int logn[MAX];

int calc(int x, int y, int xx, int yy, int p, int q) {
  return max(
    max(ST[x][y][p][q], ST[xx - (1 << p) + 1][yy - (1 << q) + 1][p][q]),
    max(ST[xx - (1 << p) + 1][y][p][q], ST[x][yy - (1 << q) + 1][p][q])
  );
}

void init_ST() {
  logn[1] = 0; logn[2] = 1;
  for (int i = 3; i < MAX; i++) logn[i] = logn[i >> 1] + 1;
  for (int x = 0; x <= logn[n]; x++)
  for (int y = 0; y <= logn[m]; y++)
  for (int i = 1; i + (1 << x) - 1 <= n; i++) {
    for (int j = 1; j + (1 << y) - 1 <= m; j++) {
      if (!x && !y) { ST[i][j][x][y] = a[i][j]; continue; }
      ST[i][j][x][y] = calc(i, j, i + (1 << x) - 1, j + (1 << y) - 1, max(x - 1, 0), max(y - 1, 0));
    }
  }
}

int RMQ(int x, int y, int xx, int yy) {
  return calc(x, y, xx, yy, logn[xx - x + 1], logn[yy - y + 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
int n, m, tot, bel[MAX], L[MAX], R[MAX];
ll a[MAX], sum[MAX], c[MAX];

void init(){
  int persz = (int)sqrt(n);
  for (int i = 1; i <= n; i += persz){
    ++tot; L[tot] = i; R[tot] = min(n, i + persz - 1);
    for (int j = L[tot]; j <= R[tot]; j++){
      bel[j] = tot;
      sum[tot] += a[j];
    }
  }
}

void add(int l, int r, ll x){
  if (bel[l] == bel[r]) {
    for (int i = l; i <= r; i++) a[i] += x, sum[bel[i]] += x;
  } else {
    for (int i = bel[l] + 1; i <= bel[r] - 1; i++) sum[i] += x * (R[i] - L[i] + 1), c[i] += x;
    for (int i = l; i <= R[bel[l]]; i++) a[i] += x, sum[bel[i]] += x;
    for (int i = L[bel[r]]; i <= r; i++) a[i] += x, sum[bel[i]] += x;
  }
}

ll query(int l, int r){
  ll res = 0;
  if (bel[l] == bel[r]){
    for (int i = l; i <= r; i++) res += a[i] + c[bel[i]];
  }else{
    for (int i = bel[l] + 1; i <= bel[r] - 1; i++) res += sum[i];
    for (int i = l; i <= R[bel[l]]; i++) res += a[i] + c[bel[i]];
    for (int i = L[bel[r]]; i <= r; i++) res += a[i] + c[bel[i]];
  }
  return res;
}

jls线段树

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
#include <bits/stdc++.h>
#define ls k << 1
#define rs k << 1 | 1
#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, r
#define ll long long
using namespace std;

const int MAX = 1e6 + 50;
struct Node {
  int l, r, mx, se, mxcnt, tag;
  ll sum;
}tree[MAX << 2];
int a[MAX], n, m;

void pushup(int k) {
  tree[k].sum = tree[ls].sum + tree[rs].sum;
  if (tree[ls].mx == tree[rs].mx) {
    tree[k].mx = tree[ls].mx;
    tree[k].se = max(tree[ls].se, tree[rs].se);
    tree[k].mxcnt = tree[ls].mxcnt + tree[rs].mxcnt;
  } else if (tree[ls].mx > tree[rs].mx) {
    tree[k].mx = tree[ls].mx;
    tree[k].se = max(tree[ls].se, tree[rs].mx);
    tree[k].mxcnt = tree[ls].mxcnt;
  } else {
    tree[k].mx = tree[rs].mx;
    tree[k].se = max(tree[ls].mx, tree[rs].se);
    tree[k].mxcnt = tree[rs].mxcnt;
  }
}

void pushdown(int k) {
  if (tree[k].tag == -1) return;
  if (tree[ls].mx > tree[k].tag) {
    tree[ls].sum -= (ll)(tree[ls].mx - tree[k].tag) * tree[ls].mxcnt;
    tree[ls].mx = tree[ls].tag = tree[k].tag;
  }
  if (tree[rs].mx > tree[k].tag) {
    tree[rs].sum -= (ll)(tree[rs].mx - tree[k].tag) * tree[rs].mxcnt;
    tree[rs].mx = tree[rs].tag = tree[k].tag;
  }
  tree[k].tag = -1;
}

void build(int k, int l, int r) {
  tree[k].l = l; tree[k].r = r;
  tree[k].tag = -1;
  if (l == r) {
    tree[k].sum = tree[k].mx = a[l];
    tree[k].se = -1;
    tree[k].mxcnt = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(lson);
  build(rson);
  pushup(k);
}

void modify(int k, int l, int r, int x) {
  if (tree[k].mx <= x) return;
  if (l > tree[k].r || r < tree[k].l) return;
  if (l <= tree[k].l && tree[k].r <= r && tree[k].se < x) {
    if (tree[k].mx > x) {
      tree[k].sum -= (ll)(tree[k].mx - x) * tree[k].mxcnt;
      tree[k].mx = tree[k].tag = x;
    }
    return;
  }
  pushdown(k);
  int mid = (l + r) >> 1;
  modify(ls, l, r, x);
  modify(rs, l, r, x);
  pushup(k);
}

int querymx(int k, int l, int r) {
  if (tree[k].l == l && tree[k].r == r) return tree[k].mx;
  pushdown(k);
  int mid = (tree[k].l + tree[k].r) >> 1; 
  if (r <= mid) return querymx(ls, l, r);
  else if (l > mid) return querymx(rs, l, r);
  else return max(querymx(lson), querymx(rson));
}

ll querysum(int k, int l, int r) {
  if (tree[k].l == l && tree[k].r == r) return tree[k].sum;
  pushdown(k);
  int mid = (tree[k].l + tree[k].r) >> 1; 
  if (r <= mid) return querysum(ls, l, r);
  else if (l > mid) return querysum(rs, l, r);
  else return querysum(lson) + querysum(rson);
}

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    while (m--) {
      int op, l, r; scanf("%d%d%d", &op, &l, &r);
      if (op == 0) {
        int t; scanf("%d", &t);
        modify(1, l, r, t);
      } else if (op == 1) {
        printf("%d\n", querymx(1, l, r));
      } else {
        printf("%lld\n", querysum(1, l, r));
      }
    }
  }
  return 0;
}

主席树

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
#include<bits/stdc++.h>
using namespace std;

const int MAX = 2e5 + 10;
struct Node {
  int l, r, sum;
}tree[MAX << 5];
int root[MAX], idx;  //每个版本树的根
int a[MAX], b[MAX];

void Insert(int l, int r, int pre, int& now, int x) {
  now = ++idx;
  tree[now] = tree[pre];
  tree[now].sum++;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid) Insert(l, mid, tree[pre].l, tree[now].l, x);
  else Insert(mid+1, r, tree[pre].r, tree[now].r, x);
}

int Query(int l, int r, int L, int R, int k) {
  if (l == r) return l;
  int leftnum = tree[tree[R].l].sum - tree[tree[L].l].sum;
  int mid = (l + r) >> 1;
  if (k <= leftnum) return Query(l, mid, tree[L].l, tree[R].l, k);
  else return Query(mid + 1, r, tree[L].r, tree[R].r, k - leftnum);
}

int main() {
  int n, m; scanf("%d%d", &n, &m);  //n个数,m个查询
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  sort(b + 1, b + n + 1);
  int sz = unique(b + 1, b + n + 1) - (b + 1);  //离散后的大小
  for (int i = 1; i <= n; i++) {
    int inx = lower_bound(b + 1, b + sz + 1, a[i]) - b;
    Insert(1, sz, root[i - 1], root[i], inx);
  }
  while (m--) {
    int l, r, k; scanf("%d%d%d", &l, &r, &k);
    printf("%d\n", b[Query(1, sz, root[l - 1], root[r], k)]);
  }
  return 0;
}

树状数组套权值线段树

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
//动态第k小
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int MAX = 1e5 + 50;
struct Node {
  int l, r, cnt;
}tree[MAX << 9];
int root[MAX], idx;
int a[MAX], n, m;
int X[MAX], Y[MAX], C1, C2;

void modify(int& k, int l, int r, int x, int y) {
  if (!k) k = ++idx;
  tree[k].cnt += y;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid) modify(tree[k].l, l, mid, x, y);
  else modify(tree[k].r, mid + 1, r, x, y);
}

int query1(int l, int r, int k) {
  if (l == r) return l;
  int mid = (l + r) >> 1;
  int sum = 0;
  for (int i = 1; i <= C1; i++) sum -= tree[tree[X[i]].l].cnt;
  for (int i = 1; i <= C2; i++) sum += tree[tree[Y[i]].l].cnt;
  if (k <= sum){
    for (int i = 1; i <= C1; i++) X[i] = tree[X[i]].l;
    for (int i = 1; i <= C2; i++) Y[i] = tree[Y[i]].l;
    return query1(l, mid, k);
  }else{
    for (int i = 1; i <= C1; i++) X[i] = tree[X[i]].r;
    for (int i = 1; i <= C2; i++) Y[i] = tree[Y[i]].r;
    return query1(mid+1, r, k-sum);
  }
}

void add(int pos, int val, int x) {
  for (int i = pos; i <= n; i += lowbit(i)) modify(root[i], 0, 1e9, val, x);
}

int query2(int L, int R, int k) {
  C1 = C2 = 0;
  for (int i = L - 1; i >= 1; i -= lowbit(i)) X[++C1] = root[i];
  for (int i = R; i >= 1; i -= lowbit(i)) Y[++C2] = root[i];
  return query1(0, 1e9, k);
}

int main(){
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    add(i, a[i], 1);
  }
  for (int i = 1; i <= m; i++) {
    char op; scanf(" %c", &op);
    if (op == 'C') {
      int x, y; scanf("%d%d", &x, &y);
      add(x, a[x], -1);
      add(x, y, 1);
      a[x] = y;
    } else {
      int l, r, k; scanf("%d%d%d", &l, &r, &k);
      printf("%d\n", query2(l, r, k));
    }
  }
  return 0;
}

划分树

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
//区间第k小
#include <bits/stdc++.h>
using namespace std;

const int MAX = 2e5 + 50;
int tree[20][MAX], toLeft[20][MAX];
int a[MAX], b[MAX], n, m;

void build(int deep, int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  int x = b[mid], same = mid - l + 1, posL = l, posR = mid + 1;
  for (int i = l; i <= r; i++) if (tree[deep][i] < x) --same;
  for (int i = l; i <= r; i++) {
    int flag = 0;
    if (tree[deep][i] < x || tree[deep][i] == x && same > 0) {
      flag = 1;
      tree[deep + 1][posL++] = tree[deep][i];
      same -= (tree[deep][i] == x);
    } else {
      tree[deep + 1][posR++] = tree[deep][i];
    }
    toLeft[deep][i] = toLeft[deep][i - 1] + flag;
  }
  build(deep + 1, l, mid);
  build(deep + 1, mid + 1, r);
}

int query(int deep, int l, int r, int L, int R, int k) {
  if (L == R) return tree[deep][L];
  int mid = (l + r) >> 1;
  int lx = toLeft[deep][L - 1] - toLeft[deep][l - 1];
  int ly = toLeft[deep][R] - toLeft[deep][l - 1];
  int rx = L - l - lx, ry = R - l + 1 - ly;
  int cnt = ly - lx;
  if (k <= cnt) return query(deep + 1, l, mid, l + lx, l + ly - 1, k);
  else return query(deep + 1, mid + 1, r, mid + rx + 1, mid + ry, k - cnt);
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    tree[0][i] = b[i] = a[i];
  }
  sort(b + 1, b + n + 1);
  build(0, 1, n);
  while (m--) {
    int l, r, k; scanf("%d%d%d", &l, &r, &k);
    printf("%d\n", query(0, 1, n, l, r, k));
  }
  return 0;
}

Splay

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
template<class T> struct Splay {
  struct Node {
    T val, lazy;
    int cnt, siz, fa, son[2];
  };
  vector<Node> tree;
  int root, idx;

  Splay() : root(0), idx(0), tree(1) {}
  Node& operator[](int x) { return tree[x]; }
  int ls(int u) { return tree[u].son[0]; }
  int rs(int u) { return tree[u].son[1]; }

  void pushup(int u) {
    tree[u].siz = tree[ls(u)].siz + tree[rs(u)].siz + tree[u].cnt;
  }

  void pushdown(int u) { /*根据题目定义该函数*/ }

  void rotate(int x) {
    int y = tree[x].fa;
    int z = tree[y].fa;
    int k = (rs(y) == x);
    pushdown(x); pushdown(y);
    tree[z].son[rs(z) == y] = x;
    tree[x].fa = z;
    tree[y].son[k] = tree[x].son[k ^ 1];
    tree[tree[x].son[k ^ 1]].fa = y;
    tree[x].son[k ^ 1] = y;
    tree[y].fa = x;
    pushup(y); pushup(x);
  }

  void splay(int x, int goal) {  // 将x旋转到goal的下面
    while (tree[x].fa != goal) {
      int y = tree[x].fa;
      int z = tree[y].fa;
      if (z != goal) {
        ((ls(y) == x) ^ (ls(z) == y)) ? rotate(x) : rotate(y);
      }
      rotate(x);
    }
    if (!goal) {
      root = x;
    }
  }

  int findKth(int k) {  // 查找中序遍历第k个元素
    int u = root;
    while (true) {
      pushdown(u);
      if (k <= tree[ls(u)].siz) {
        u = ls(u);
      } else if (k <= tree[ls(u)].siz + tree[u].cnt) {
        return u;
      } else {
        k -= tree[ls(u)].siz + tree[u].cnt;
        u = rs(u);
      }
    }
    return -1;
  }

  int getPrev(T val) {  // 查找val的前驱
    int u = root, p = -1;
    while (u) {
      pushdown(u);
      if (tree[u].val >= val) {
        u = ls(u);
      } else {
        p = u;
        u = rs(u);
      }
    }
    return p;
  }

  int getNext(T val) {  // 查找val的后继 
    int u = root, p = -1;
    while (u) {
      pushdown(u);
      if (tree[u].val <= val) {
        u = rs(u);
      } else {
        p = u;
        u = ls(u);
      }
    }
    return p;
  }

  int getRank(T val) {  // 返回比val小的元素个数+1
    // if (count(val) == 0) return -1;
    int u = root, rank = 0;
    while (u) {
      pushdown(u);
      if (tree[u].val == val) {
        rank += tree[ls(u)].siz;
        splay(u, 0);
        return rank;
      } else if (tree[u].val < val) {
        rank += tree[ls(u)].siz + tree[u].cnt;
        u = rs(u);
      } else {
        u = ls(u);
      }
    }
    return rank;
  }

  void insert(T val, int cnt = 1) {  // 插入cnt个val
    int u = root, fa = 0;
    while (u) {
      pushdown(u);
      if (tree[u].val == val) {
        tree[u].cnt += cnt;
        tree[u].siz += cnt;
        splay(u, 0);
        return;
      }
      fa = u;
      u = tree[u].son[val > tree[u].val];
    }
    u = ++idx;
    tree.push_back(Node());
    if (fa) {
      tree[fa].son[val > tree[fa].val] = u;
    }
    tree[u].val = val;
    tree[u].fa = fa;
    tree[u].cnt = cnt;
    tree[u].siz = cnt;
    splay(u, 0);
  }

  void erase(T val, int cnt = 1) {  // 删除cnt个val
    int pre = getPrev(val), suf = getNext(val);
    splay(pre, 0);
    splay(suf, pre);
    int u = ls(suf);
    if (tree[u].cnt > cnt) {
      tree[u].cnt -= cnt;
      splay(u, 0);
    } else {
      tree[suf].son[0] = 0;
    }
  }
};

可持久化字典树

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
#include <bits/stdc++.h>
using namespace std;

const int MAX = 6e5 + 50;
int trie[MAX * 30][2], root[MAX], cnt[MAX * 30], idx;
int a[MAX], sum[MAX], n, m;

void Insert(int pre, int now, int x) {
  for (int i = 25; i >= 0; i--) {
    int t = (x >> i) & 1;
    trie[now][0] = trie[pre][0];
    trie[now][1] = trie[pre][1];
    trie[now][t] = ++idx;
    cnt[now] = cnt[pre] + 1;
    pre = trie[pre][t];
    now = trie[now][t];
  }
  cnt[now] = cnt[pre] + 1;
}

int query(int pre, int now, int x) {
  int res = 0;
  for (int i = 25; i >= 0; i--) {
    int t = (x >> i) & 1;
    if (cnt[trie[now][t ^ 1]] - cnt[trie[pre][t ^ 1]]) {
      res |= 1 << i;
      pre = trie[pre][t ^ 1];
      now = trie[now][t ^ 1];
    } else {
      pre = trie[pre][t], now = trie[now][t];
    }
  }
  return res;
}

int main() {
  scanf("%d%d", &n, &m); ++n;
  for (int i = 2; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) {
    sum[i] = sum[i-1] ^ a[i];
    root[i] = ++idx;
    Insert(root[i-1], root[i], sum[i]);
  }
  while (m--) {
    char opt; scanf(" %c", &opt);
    if (opt == 'A') {
      scanf("%d", &a[++n]);
      sum[n] = sum[n - 1] ^ a[n];
      root[n] = ++idx;
      Insert(root[n - 1], root[n], sum[n]);
    } else {
      int l, r, x; scanf("%d%d%d", &l, &r, &x);
      printf("%d\n", query(root[l - 1], root[r], sum[n] ^ x));
    }
  }
  return 0;
}

手写hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
namespace HASH {
  int to[MAX], cnt[MAX], nxt[MAX], head[MAX], tot;
  void init() { memset(head, tot = 0, sizeof(head)), memset(cnt, 0, sizeof(cnt)); }
  void add(int x) {
    int k = x % MOD;
    for (int i = head[k]; i; i = nxt[i]) if (to[i] == x) { ++cnt[i]; return; }
    to[++tot] = x, cnt[tot] = 1, nxt[tot] = head[k], head[k] = tot;
  }
  int query(int x) {
    int k = x % MOD;
    for (int i = head[k]; i; i = nxt[i]) if (to[i] == x) return cnt[i];
    return 0;
  }
}

deque带翻转操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct deQue {
  int buffer[MAX << 1];
  int head = MAX, tail = MAX - 1;
  bool rev;
  bool empty() { return tail < head; }
  int size() { return tail - head + 1; }
  int front() { return rev ? buffer[tail] : buffer[head]; }
  int back() { return rev ? buffer[head] : buffer[tail]; }
  void push_front(int x) { rev ? buffer[++tail] = x : buffer[--head] = x; }
  void push_back(int x) { rev ? buffer[--head] = x : buffer[++tail] = x; }
  void pop_back() { rev ? head++ : tail--; }
  void pop_front() { rev ? tail-- : head++; }
  void reverse() { rev ^= 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
#include <bits/stdc++.h>
#define ls k << 1
#define rs k << 1 | 1
#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, r
using namespace std;

const double eps = 1e-8;
const int MOD1 = 39989;
const int MOD2 = 1000000000;
const int MAX = 4e4 + 5;
struct Line {
  int id;
  double k, b;
  Line() {}
  Line(int _id, double _k, double _b) : id(_id), k(_k), b(_b) {}
};
struct Node {
  bool have;
  Line line;
}tree[MAX << 2];
int n;

double calc(Line l, int x) {
  return l.k * x + l.b;
}

void build(int k, int l, int r) {
  tree[k].have = false;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(lson);
  build(rson);
}

void modify(int k, int l, int r, int L, int R, Line x) {
  if (r < L || l > R) return;
  if (L <= l && r <= R) {
    if (!tree[k].have) {
      tree[k].line = x;
      tree[k].have = true;
    } else if (calc(x, l) > calc(tree[k].line, l) && calc(x, r) > calc(tree[k].line, r)) {
      tree[k].line = x;
    } else if (calc(x, l) > calc(tree[k].line, l) || calc(x, r) > calc(tree[k].line, r)) {
      int mid = (l + r) >> 1;
      if (calc(x, mid) > calc(tree[k].line, mid)) swap(tree[k].line, x);
      if (calc(x, l) > calc(tree[k].line, l)) modify(lson, L, R, x);
      else modify(rson, L, R, x);
    }
    return;
  }
  int mid = (l + r) >> 1;
  modify(lson, L, R, x);
  modify(rson, L, R, x);
}

Line query(int k, int l, int r, int x) {
  if (l == r) return tree[k].line;
  Line ans = tree[k].line, nw;
  int mid = (l + r) >> 1;
  if (x <= mid) nw = query(lson, x);
  else nw = query(rson, x);
  if (nw.id) {
    if (!ans.id) ans = nw;
    else if (calc(nw, x) > calc(ans, x)) swap(ans, nw);
    else if (fabs(calc(nw, x) - calc(ans, x)) <= eps && nw.id < ans.id) {
      swap(ans, nw);
    }
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  build(1, 1, 40000);
  int lastans = 0, id = 0;
  while (n--) {
    int op;
    cin >> op;
    if (op == 0) {
      int k;
      cin >> k;
      int x = (k + lastans - 1) % MOD1 + 1;
      Line ans = query(1, 1, 40000, x);
      lastans = ans.id;
      cout << ans.id << "\n";
    } else {
      int x, y, xx, yy;
      cin >> x >> y >> xx >> yy;
      x = (x + lastans - 1) % MOD1 + 1;
      xx = (xx + lastans - 1) % MOD1 + 1;
      y = (y + lastans - 1) % MOD2 + 1;
      yy = (yy + lastans - 1) % MOD2 + 1;
      double k, b;
      if (x != xx) {
        if (x > xx) {
          swap(x, xx);
          swap(y, yy);
        }
        k = (double)(yy - y) / (xx - x);
        b = (double)y - k * x;
      } else {
        k = 0;
        b = max(yy, y);
      }
      modify(1, 1, 40000, x, xx, Line(++id, k, b));
    }
  }
  return 0;
}