P5312 [Ynoi2011] Contest Experimental Class

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:

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.

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$.

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

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