【LG4585】[FJOI2015]火星商店问题

时间：2023-03-09 13:32:45
【LG4585】[FJOI2015]火星商店问题

【LG4585】[FJOI2015]火星商店问题

题面

bzoj权限题

洛谷

\(Notice:\)

关于题面的几个比较坑的地方：

  • “一天”不是一个操作，而是有0操作就相当于一天开始了，然后下面的紧跟着的1操作都算这一天的，直到再次出现0操作为止。当然第一个操作可能会是1操作这个时候也算第一天（比如样例……）

  • 0操作是在这个位置添加一个数而不是改成这个数

  • d=0的时候不算这一天

垃圾题面，害我被坑

题解

显然对于每个人他的可购买商品的时间都是一个区间。

这样我们按照线段树分治的套路在线段树上打一个那个人的标

记。

我们将所有操作离线, 并将修改和询问分开存下来。

对于每一个修改, 我们按照其在线段树上分治, 存下当前区间所

对应的修改序列, 这个过程可以像整体二分那样处理。

将这段区间内的修改建可持久化\(\text{Trie}\), 而且此时这个时间范围内

的询问你是知道的, 直接在\(\text{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\n", ans[i]);

	return 0;

}

相关文章