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
| #define REP(i, s, e) for (int i = s; i <= e; i++)
#define DREP(i, s, e) for (int i = s; i >= e; i--)
#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 100000 + 10, maxN = maxn * 18, D = 16;
int n, m, tim, Q;
int bin[17], rt[maxn], ans[maxn], st[maxn];
struct question{int l, r, tl, tr, x;}q[maxn];
struct event
{
int id, v, t;
inline bool operator < (event B) const {return id < B.id;}
}e[maxn], e1[maxn], e2[maxn];
int cur, ch[maxN][2], cnt[maxN];
#define flag (!!(num & bin[d]))
void insert(int pre, int &p, int num, int d)
{
p = ++cur;
ch[p][0] = ch[pre][0];
ch[p][1] = ch[pre][1];
cnt[p] = cnt[pre] + 1;
if (d == -1) return;
insert(ch[pre][flag], ch[p][flag], num, d - 1);
}
int query(int x, int y, int num, int d) {return d == -1 ? 0 : cnt[ch[y][flag ^ 1]] - cnt[ch[x][flag ^ 1]] ? query(ch[x][flag ^ 1], ch[y][flag ^ 1], num, d - 1) + bin[d] : query(ch[x][flag], ch[y][flag], num, d - 1);}
vector<int> events[maxn << 2];
#define mid (l + r >> 1)
#define ls p << 1
#define rs p << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
void pushdown(int p, int l, int r, int L, int R, int id)
{
if (l > r) return;
if (L <= l && r <= R) return events[p].push_back(id), void();
if (L <= mid) pushdown(lson, L, R, id);
if (R > mid) pushdown(rson, L, R, id);
}
void work(int p, int l, int r)
{
cur = 0;
int top(0), i1(0), i2(0);
REP(i, l, r)
{
st[++top] = e[i].id;
insert(rt[top-1], rt[top], e[i].v, D);
}
int siz = (int)events[p].size() - 1;
REP(i, 0, siz)
chkmax(ans[events[p][i]], query(rt[lower_bound(st + 1, st + 1 + top, q[events[p][i]].l) - st - 1], rt[upper_bound(st + 1, st + 1 + top, q[events[p][i]].r) - st - 1], q[events[p][i]].x, D));
if (l == r) return;
REP(i, l, r)
if(e[i].t <= mid) e1[++i1] = e[i];
else e2[++i2] = e[i];
copy(e1 + 1, e1 + 1 + i1, e + l);
copy(e2 + 1, e2 + 1 + i2, e + l + i1);
work(lson);work(rson);
}
int opt, l, r, x, d;
int main()
{
#ifdef CraZYali
freopen("4137.in", "r", stdin);
freopen("4137.out", "w", stdout);
#endif
bin[0] = 1;
REP(i, 1, D) bin[i] = bin[i-1] << 1;
cin >> n >> m;
REP(i, 1, n)
{
scanf("%d", &x);
insert(rt[i-1], rt[i], x, D);
}
tim=1;
REP(i, 1, m)
{
scanf("%d", &opt);
if(opt)
{
scanf("%d%d%d%d", &l, &r, &x, &d);
q[++Q] = question{l, r, max(1, tim - d + 1), tim, x};
ans[Q] = query(rt[l-1], rt[r], x, D);
}
else
{
scanf("%d%d", &l, &r);
e[++tim] = event{l, r, tim};
}
}
REP(i, 1, Q) pushdown(1, 1, tim, q[i].tl, q[i].tr, i);
sort(e + 1, e + 1 + tim);
work(1, 1, tim);
REP(i, 1, Q) printf("%d\n", ans[i]);
return 0;
}
|
