Background

During the high school entrance exam, it felt like nothing special. I got into cdqz casually. A few nights before the exam, I was still secretly reading xianxia novels on an itouch.

After getting into cdqz, I went to OI classes every day. I did not really understand much, but I had nothing else to do anyway.

At that time, I listened to Yu Shen introduce data structures, and he roughly wrote it like this:

Beginner: Binary Indexed Tree, Segment Tree

Intermediate: Balanced Tree, Mergeable Heap, Mo's Algorithm

Advanced: Persistent Segment Tree, Dynamic Tree

Frontier: Dynamic Cactus

It felt like there were so many “trees” that sounded amazing, and even “cactus”? Data structures are really awesome (foreshadowing)!

That year, cdqz suddenly decided to set up a contest experimental class, focusing on competitions. Since I did not like cultural courses much, I decided to join.

To enter the contest class, you had to pass a selection summer camp for a subject. At that time, a friend f321dd felt it was very “toxic” and ran away. I did not quite understand then, but now I understand to some extent.

This summer camp was basically inviting different competition teachers every day to give lectures. I was not interested in math or physics, so the classes were boring. With nothing to do, I often sneaked into the computer room to write some code.

Thinking carefully, I had no real plan for the future back then. I cannot say I loved competitions a lot, and I cannot say I hated cultural courses a lot either. I just heard that this experimental class was good and could help you get into a good university, so I went. It felt similar to people choosing a CS major after hearing “computer science makes a lot of money”.

But is that not how everyone is?

In the end, I entered the contest experimental class and met everyone who would study OI together for the next two years. We also had a placement test. It seemed that zms got 350 and ranked first, and I got 310 and ranked second. I remember I used “dynamic spfa” to cheese a shortest path problem, and I shouted happily when I saw AC.

The contest group at that time:

zms: A middle school classmate, mentioned before. Everyone called him “Xiao Bai”. He felt like a steady person, recognized as the strongest OI contestant of our grade, and he was close with yjq. I saw him as my goal at the time.

f321dd: A middle school classmate and friend. In middle school we often skipped classes to play cards together (we even made something called “Chemistry Kill”). He felt like a funny person.

grh: Came from No. 4 Middle School, tall and thin, liked doujinshi and anime.

ziliuziliu: Came from No. 4 Middle School, thin, liked playing World of Tanks. He grinded the KV3 line, and his AP shells could not penetrate WZ111 every day. Pretty good skill.

cyz: Also liked playing World of Tanks. I think the first time I saw him play, he was playing the Wirbelwind. I thought it was fun and also started playing. He was quite strong, and I often could not understand what he was thinking.

Flaze: A female OIer, seemed pretty cute.

zyx: A student from another place, had not learned OI before.

cx: Chubby, could write an OJ.

zqq: From the same middle school as Flaze, seemed very down-to-earth (at first it was like that). He would learn every knowledge point.

Seniors:

yjq: Extremely strong, always finished contests early and AK.

Karl_duan: Felt like he was always studying, very steady and hardworking.

zcy: Very good at messing around, and often solved problems in a messy way. In NOIP he got 600 with brute force.

mhy: A senior from the National Training Team, thin.

When writing this memoir, I still feel quite emotional. Remembering what happened back then makes me very happy~

During that period of learning OI, although I was very weak and got crushed every day, it was undoubtedly still fun.

[Remember to add pictures, content oj7]

Since this is Ynoi, not a place for the author to write nostalgic text, you need to solve a data structure problem:

Problem Description

There is an array $A$ of length $n$, indexed starting from $1$. You need to process $m$ operations of the following four types:

1. Append a number $x$ to the end of array $A$.
2. Output $\sum_{i=l}^{r}A_i$.
3. Change every number $A_i$ in array $A$ to $A_i\oplus x$. ($\oplus$ denotes the XOR operation.)
4. Sort array $A$ in non-decreasing order.

Input Format

The first line contains an integer $n$, the initial size of $A$.
The next line contains $n$ non-negative integers $A_i$, representing each element in $A$.
The next line contains an integer $m$, the number of operations.
The next $m$ lines each describe one operation:

• 1 x: the first operation, append $x$ to the end.
• 2 l r: the second operation, query $\sum_{i=l}^{r}A_i$. It is guaranteed that $1\le l\le r\le n'$, where $n'$ is the length of the sequence at the time of the operation.
• 3 x: the third operation, XOR every element with $x$.
• 4: the fourth operation, sort array $A$.

Output Format

For each operation of the second type, output the answer.

5
5 2 6 2 0
5
2 1 5
1 2
3 7
2 2 6
4

15
23

Hint

Idea: WJMZBMR, Solution: WJMZBMR, Code: WJMZBMR, Data: WJMZBMR

$1\le n,\,m\le 10^5, 0\le x,A_i\le 10^9$

Translated by ChatGPT 5