Solution
线段树套 trie,秒了!
\(O(n\log^2 n)\)
Code
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 1e5 + 10;
struct Operation {
int op, l, r, x, d;
} Oper[N];
int n, m;
#define lc (u << 1)
#define rc ((u << 1) | 1)
#define mid ((l + r) >> 1)
struct BinaryTrie {
int tot;
vector<array<int, 2>> ch;
vector<int> Time;
BinaryTrie() {
tot = 1, ch.assign(2, {0, 0}), Time.assign(2, 0);
}
void Ins(int x, int d) {
int pos = 1;
reo(p, 16, 0) {
int now = (x >> p) & 1;
if (!ch[pos][now]) ch[pos][now] = ++tot, ch.push_back({0, 0}), Time.push_back(0);
pos = ch[pos][now];
Time[pos] = max(Time[pos], d);
}
}
} Trie[N << 2];
void Upd(int u, int l, int r, int x, int v, int d) {
if (x < l || r < x) return;
Trie[u].Ins(v, d);
if (l == r) return;
Upd(lc, l, mid, x, v, d), Upd(rc, mid + 1, r, x, v, d);
}
vector<array<int, 2>> nodes;
void Get(int u, int l, int r, int x, int y) {
if (y < l || r < x || x > y) return;
if (x <= l && r <= y) return nodes.push_back({u, 1});
Get(lc, l, mid, x, y), Get(rc, mid + 1, r, x, y);
}
#undef lc
#undef rc
#undef mid
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n >> m;
rep(i, 1, n) {
int x;
cin >> x, Upd(1, 1, n, i, x, 100001);
}
rep(i, 1, m) {
cin >> Oper[i].op;
if (Oper[i].op == 0) {
cin >> Oper[i].l >> Oper[i].x;
} else {
cin >> Oper[i].l >> Oper[i].r >> Oper[i].x >> Oper[i].d;
}
}
for (int day = 1, i = 1; i <= m; ++day) {
if (Oper[i].op == 0)
Upd(1, 1, n, Oper[i].l, Oper[i].x, day), ++i;
for (; i <= m && Oper[i].op == 1; ++i) {
int l = Oper[i].l, r = Oper[i].r, x = Oper[i].x, d = day - Oper[i].d + 1, ans = 0;
Get(1, 1, n, l, r);
reo(t, 16, 0) {
int now = !((x >> t) & 1), ok = 0;
for (auto p : nodes) {
int v = Trie[p[0]].ch[p[1]][now];
if (v && Trie[p[0]].Time[v] >= d) {
ok = 1;
break;
}
}
if (ok) {
ans |= (1 << t);
for (auto & p : nodes) {
int v = Trie[p[0]].ch[p[1]][now];
if (v && Trie[p[0]].Time[v] >= d) {
p[1] = v;
} else {
p[1] = 0;
}
}
} else {
now = !now;
for (auto & p : nodes) {
int v = Trie[p[0]].ch[p[1]][now];
if (v && Trie[p[0]].Time[v] >= d) {
p[1] = v;
} else {
p[1] = 0;
}
}
}
}
nodes.clear();
cout << ans << '\n';
}
}
return 0;
}
标签:Oper,ch,商店,int,题解,pos,Time,now,火星
From: https://www.cnblogs.com/laijinyi/p/18449774