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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
| const unsigned Mod(1000000007);
unsigned m, n, Last;
unsigned Stack[600005], STop(0);
unsigned A, B, C, D, Opt, OV;
unsigned Cnt(0), Ans(0), Tmp(0);
inline void Mn(unsigned& x) { x -= ((x >= Mod) ? Mod : 0); }
struct Node {
Node* LS, * RS;
unsigned Size, Val, Tag, Def, Num, Use;
char Flp;
inline void PsUp() {
Val = LS->Val + RS->Val, Mn(Val);
Size = LS->Size + RS->Size;
}
inline Node* Copy() {
int Del(Stack[STop] - Num);
Node* Cur(this + Del);
--Use, * Cur = *this, Cur->Use = 1, Cur->Num = Stack[STop--];
if (Cur->LS) ++(Cur->LS->Use);
if (Cur->RS) ++(Cur->RS->Use);
return Cur;
}
inline void Cycle() {
if (LS) { --(LS->Use); if (!(LS->Use)) LS->Cycle(); }
if (RS) { --(RS->Use); if (!(RS->Use)) RS->Cycle(); }
Stack[++STop] = Num;
}
inline void PsDw() {
if (LS) {
if (LS->Use > 1) LS = LS->Copy();
if (~Def) LS->Def = Def, LS->Val = ((unsigned long long)Def * LS->Size) % Mod, LS->Tag = 0;
LS->Tag += Tag, Mn(LS->Tag), LS->Val = (LS->Val + (unsigned long long)LS->Size * Tag) % Mod;
if (Flp) LS->Flp ^= 1, swap(LS->LS, LS->RS);
}
if (RS) {
if (RS->Use > 1) RS = RS->Copy();
if (~Def) RS->Def = Def, RS->Val = ((unsigned long long)Def * RS->Size) % Mod, RS->Tag = 0;
RS->Tag += Tag, Mn(RS->Tag), RS->Val = (RS->Val + (unsigned long long)RS->Size * Tag) % Mod;
if (Flp) RS->Flp ^= 1, swap(RS->LS, RS->RS);
}
Tag = Flp = 0, Def = 0xffffffff;
}
inline Node* Rotate() {
PsDw();
if (Size <= 5) return this;
Node* Cur(NULL);
if ((LS->Size * 3) < RS->Size) (Cur = RS)->PsDw(), RS = Cur->RS, Cur->RS = Cur->LS, Cur->LS = LS, (LS = Cur)->PsUp();
if ((RS->Size * 3) < LS->Size) (Cur = LS)->PsDw(), LS = Cur->LS, Cur->LS = Cur->RS, Cur->RS = RS, (RS = Cur)->PsUp();
if (Cur) Cur->Rotate();
return this;
}
inline void Split(unsigned Left) {
PsDw();
if (LS->Size == Left) return;
Node* Cur;
if (LS->Size > Left) (Cur = LS)->Split(Left), LS = Cur->LS, Cur->LS = Cur->RS, Cur->RS = RS, RS = Cur;
else (Cur = RS)->Split(Left - LS->Size), RS = Cur->RS, Cur->RS = Cur->LS, Cur->LS = LS, LS = Cur;
Cur->PsUp();
}
inline void SPLIT(unsigned Left, Node*& LP, Node*& RP) {
if (!Left) { LP = NULL, RP = this; return; }
if (Left == Size) { LP = this, RP = NULL; return; }
Split(Left), LP = LS, RP = RS;
}
inline void Prt() {
if (Size == 1) { printf("%u ", Val); return; }
PsDw();
if (LS) LS->Prt();
if (RS) RS->Prt();
}
}N[600005], * CntN(N), * Root(N);
inline void Build(Node* x, unsigned L, unsigned R) {
x->Def = 0xffffffff, x->Num = x - N, x->Use = 1;
if (L == R) { x->Val = RD(), x->LS = NULL, x->RS = NULL, x->Size = 1; return; }
unsigned Mid((L + R) >> 1);
Build(x->LS = ++CntN, L, Mid);
Build(x->RS = ++CntN, Mid + 1, R);
x->PsUp();
}
inline Node* MERGE(Node* Rt, Node* L, Node* R) {
if (L && R) { Rt->LS = L, Rt->RS = R, Rt->PsUp(); return Rt->Rotate(); }
if (L) return L->Rotate();
return R->Rotate();
}
signed main() {
n = RD(), m = RD(), Build(N, 1, n);
for (unsigned i(1); i <= m; ++i) {
Opt = RD(), A = (RD() ^ Last), B = (RD() ^ Last);
Node* Part1(NULL), * Part2(NULL), * Part3(NULL), * Rt1(NULL), * Rt2(NULL);
(Rt1 = Root)->SPLIT(A - 1, Part1, Part2);
(Rt2 = Part2)->SPLIT(B - A + 1, Part2, Part3);
switch (Opt) {
case(1): {
printf("%u\n", Last = Part2->Val);
break;
}
case(2): {
Part2->Def = (RD() ^ Last), Part2->Tag = 0, Part2->Val = (unsigned long long)Part2->Size * Part2->Def % Mod;
break;
}
case(3): {
Part2->Tag += (OV = (RD() ^ Last)), Mn(Part2->Tag), Part2->Val = (Part2->Val + (unsigned long long)Part2->Size * OV) % Mod;
break;
}
case(6): {
Part2->Flp = 1, swap(Part2->LS, Part2->RS);
break;
}
default: {
Node* Part4(NULL), * Part5(NULL), * Rt3(NULL), * Rt4(NULL);
C = (RD() ^ Last), D = (RD() ^ Last);
if (C > B) (Rt3 = Part3)->SPLIT(C - B - 1, Part3, Part4);
else (Rt3 = Part1)->SPLIT(C - 1, Part1, Part4);
(Rt4 = Part4)->SPLIT(D - C + 1, Part4, Part5);
if (Opt & 1) swap(Part4, Part2);
else Part4->Cycle(), ++((Part4 = Part2)->Use);
Part4 = MERGE(Rt4, Part4, Part5);
if (C > B) Part3 = MERGE(Rt3, Part3, Part4);
else Part1 = MERGE(Rt3, Part1, Part4);
break;
}
}
Part2 = MERGE(Rt2, Part2, Part3);
Root = MERGE(Rt1, Part1, Part2);
}
Root->Prt(), putchar(0x0A);
return Wild_Donkey;
}
|
