【LG4585】[FJOI2015]火星商店问题
题面
bzoj权限题
(Notice:)
关于题面的几个比较坑的地方：
-
“一天”不是一个操作，而是有0操作就相当于一天开始了，然后下面的紧跟着的1操作都算这一天的，直到再次出现0操作为止。当然第一个操作可能会是1操作这个时候也算第一天（比如样例……）
-
0操作是在这个位置添加一个数而不是改成这个数
-
d=0的时候不算这一天
垃圾题面，害我被坑
题解
显然对于每个人他的可购买商品的时间都是一个区间。
这样我们按照线段树分治的套路在线段树上打一个那个人的标
记。
我们将所有操作离线, 并将修改和询问分开存下来。
对于每一个修改, 我们按照其在线段树上分治, 存下当前区间所
对应的修改序列, 这个过程可以像整体二分那样处理。
将这段区间内的修改建可持久化( ext{Trie}), 而且此时这个时间范围内
的询问你是知道的, 直接在( ext{Trie})上查即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 1e5 + 5;
namespace Trie {
struct Trie { int ch[2], v; } t[MAX_N << 5]; int tot, rt[MAX_N];
void insert(int &o, int p, int v, int i) {
o = ++tot, t[o] = t[p], ++t[o].v;
if (i == -1) return ;
bool c = (v >> i) & 1;
insert(t[o].ch[c], t[p].ch[c], v, i - 1);
}
int query(int v, int u, int w, int i) {
if (i == -1) return 0;
bool c = (w >> i) & 1;
int res = t[t[u].ch[c ^ 1]].v - t[t[v].ch[c ^ 1]].v;
if (res) return query(t[v].ch[c ^ 1], t[u].ch[c ^ 1], w, i - 1) + (1 << i);
else return query(t[v].ch[c], t[u].ch[c], w, i - 1);
}
}
struct Mdy { int s, v, t; } q[MAX_N], lq[MAX_N], rq[MAX_N];
bool operator < (const Mdy &l, const Mdy &r) { return l.s < r.s; }
struct Qry { int l, r, tl, tr, v; } p[MAX_N];
int m_cnt, q_cnt;
int N, M, ans[MAX_N];
#define lson (o << 1)
#define rson (o << 1 | 1)
vector<int> vec[MAX_N << 2];
void modify(int o, int l, int r, int ql, int qr, int pos) {
if (ql > qr) return ;
if (ql <= l && r <= qr) return (void)vec[o].push_back(pos);
int mid = (l + r) >> 1;
if (ql <= mid) modify(lson, l, mid, ql, qr, pos);
if (qr > mid) modify(rson, mid + 1, r, ql, qr, pos);
}
int stk[MAX_N], top;
void calc(int o, int l, int r) {
top = Trie::tot = 0;
for (int i = l; i <= r; i++) {
stk[++top] = q[i].s;
Trie::insert(Trie::rt[top], Trie::rt[top - 1], q[i].v, 17);
}
for (vector<int>::iterator ite = vec[o].begin(); ite != vec[o].end(); ++ite) {
int k = *ite;
int l = upper_bound(&stk[1], &stk[top + 1], p[k].l - 1) - stk - 1;
int r = upper_bound(&stk[1], &stk[top + 1], p[k].r) - stk - 1;
ans[k] = max(ans[k], Trie::query(Trie::rt[l], Trie::rt[r], p[k].v, 17));
}
}
void Div(int o, int lval, int rval, int st, int ed) {
if (st > ed) return ;
calc(o, st, ed);
if (lval == rval) return ;
int mid = (lval + rval) >> 1, lt = 0, rt = 0;
for (int i = st; i <= ed; i++)
if (q[i].t <= mid) lq[++lt] = q[i];
else rq[++rt] = q[i];
for (int i = 1; i <= lt; i++) q[st + i - 1] = lq[i];
for (int i = 1; i <= rt; i++) q[st + lt + i - 1] = rq[i];
Div(lson, lval, mid, st, st + lt - 1);
Div(rson, mid + 1, rval, st + lt, ed);
}
int main () {
N = gi(), M = gi();
for (int i = 1; i <= N; i++) Trie::insert(Trie::rt[i], Trie::rt[i - 1], gi(), 17);
for (int i = 1; i <= M; i++) {
int op = gi();
if (op == 0) { int s = gi(), v = gi(); q[++m_cnt] = (Mdy){s, v, m_cnt}; }
else {
int l = gi(), r = gi(), v = gi(), d = gi();
p[++q_cnt] = (Qry){l, r, max(1, m_cnt - d + 1), m_cnt, v};
ans[q_cnt] = Trie::query(Trie::rt[l - 1], Trie::rt[r], v, 17);
}
}
for (int i = 1; i <= q_cnt; i++) modify(1, 1, m_cnt, p[i].tl, p[i].tr, i);
sort(&q[1], &q[m_cnt + 1]);
Div(1, 1, m_cnt, 1, m_cnt);
for (int i = 1; i <= q_cnt; i++) printf("%d
", ans[i]);
return 0;
}