[BZOJ4137][FJOI2015]火星商店问题

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }
	return x * f;
}

#define maxn 100010
#define maxN 1800010
#define maxnode 20000010
#define maxlog 17
#define oo 2147483647

int s_val[maxn];

int num[maxlog], cnt;
int tot, rt[maxn], to[maxN][2], siz[maxN];
void upd(int& y, int x, int p) {
	siz[y = ++tot] = siz[x] + 1;
	if(p < 0) return ;
	memcpy(to[y], to[x], sizeof(to[x]));
	upd(to[y][num[p]], to[x][num[p]], p - 1);
	return ;
}
void Insert_(int& y, int x, int v) {
	memset(num, 0, sizeof(num)); cnt = 0; while(v) num[cnt++] = v & 1, v >>= 1;
	upd(y, x, maxlog - 1);
	return ;
}
int Que_(int lrt, int rrt, int v) {
	memset(num, 0, sizeof(num)); cnt = 0; while(v) num[cnt++] = v & 1, v >>= 1;
	int ans = 0;
	for(int i = maxlog - 1; i >= 0; i--) {
		int x = num[i];
		if(siz[to[rrt][x^1]] - siz[to[lrt][x^1]]) lrt = to[lrt][x^1], rrt = to[rrt][x^1], ans = ans << 1 | 1;
		else lrt = to[lrt][x], rrt = to[rrt][x], ans <<= 1;
	}
	return ans;
}
int ToT, ch[maxnode][2], tim[maxnode];
void Insert(int& o, int v, int t) {
	if(!o) o = ++ToT;
	memset(num, 0, sizeof(num)); cnt = 0; while(v) num[cnt++] = v & 1, v >>= 1;
	int u = o;
	for(int i = maxlog - 1; i >= 0; i--) {
		int x = num[i];
		tim[u] = max(tim[u], t);
		if(!ch[u][x]) ch[u][x] = ++ToT;
		u = ch[u][x];
	}
	tim[u] = max(tim[u], t);
	return ;
}
int Que(int u, int deadline, int v) {
	memset(num, 0, sizeof(num)); cnt = 0; while(v) num[cnt++] = v & 1, v >>= 1;
	int ans = 0;
	for(int i = maxlog - 1; i >= 0; i--) {
		int x = num[i];
		if(tim[ch[u][x^1]] >= deadline) ans = ans << 1 | 1, u = ch[u][x^1];
		else ans <<= 1, u = ch[u][x];
	}
	return ans;
}

int Rt[maxn<<2];
void update(int o, int l, int r, int p, int v, int day) {
	Insert(Rt[o], v, day);
	if(l == r) return ;
	int mid = l + r >> 1, lc = o << 1, rc = lc | 1;
	if(p <= mid) update(lc, l, mid, p, v, day);
	else update(rc, mid + 1, r, p, v, day);
	return ;
}
int query(int o, int l, int r, int ql, int qr, int d, int day, int v) {
	if(ql <= l && r <= qr) {
//		printf("%d: %d %d %d\n", o, Rt[o], Que(Rt[o], v), rt[o].size());
		return Que(Rt[o], day - d + 1, v);
	}
	int mid = l + r >> 1, lc = o << 1, rc = lc | 1, ans = 0;
	if(ql <= mid) ans = max(ans, query(lc, l, mid, ql, qr, d, day, v));
	if(qr > mid) ans = max(ans, query(rc, mid + 1, r, ql, qr, d, day, v));
	return ans;
}

int main() {
	int n = read(), q = read();
	for(int i = 1; i <= n; i++) Insert_(rt[i], rt[i-1], read());
//	printf("tot: %d\n", tot);
	int day = 0, cnt = 0;
	while(q--) {
		int tp = read();
		cnt++;
		if(!tp) {
			int x = read(), v = read();
			update(1, 1, n, x, v, ++day);
		}
		else {
			int l = read(), r = read(), v = read(), d = read();
			printf("%d\n", max(query(1, 1, n, l, r, d, day, v), Que_(rt[l-1], rt[r], v)));
		}
	}
//	printf("ToT: %d\n", ToT);
	
	return 0;
}