[Ynoi2011] 竞赛实验班

题目背景

中考的时候好像是没什么实感的,随随便便就考上了cdqz,考前几天晚上还在偷偷用itouch看修仙小说。 考上cdqz之后,我就天天去听OI课了,虽然不太听得懂,但反正也没事干。 当时听于神介绍数据结构,他大概是这么写的: 初级:树状数组,线段树 中级:平衡树,可并堆,莫队 高级:主席树,动态树 前沿:动态仙人掌 感觉有好多听起来就好厉害的树,还有“仙人掌”?数据结构真的是太厉害了(伏笔)! 那一年cdqz突然决定搞一个竞赛实验班,专门搞竞赛,由于挺不喜欢文化课的,所以我决定去参加。 想去竞赛班要经过一个学科夏令营的选拔,当时有个朋友f321dd觉得很毒瘤就跑路了,我还不太能理解,现在一定程度上能理解了。 这个学科夏令营大概就是每天请不同学科的竞赛老师来讲课,数学,物理都不太感兴趣,所以上课就很无聊,无所事事的,经常偷偷跑去机房写点代码。 仔细想想,我当时也对未来没什么打算,也谈不上有多热爱竞赛,也谈不上有多讨厌文化课,只是听说这个实验班好,可以上好大学,就去了,感觉和听到“学计算机挣钱多”而选择去计算机系的人差不多。 不过大家不都是这样的吗。 我最后进入了竞赛实验班,也认识了将要一起学习两年oi的大家,同时还进行了一次摸底考试,当时好像zms拿了350第一,我拿了310第二,记得我还用“动态spfa”水了个最短路题,看到AC的时候开心地叫了出来。 当时的竞赛组: zms:初中同学,之前有提到,大家都叫他“小白”,感觉是一个挺稳重的人,是公认的我们那届OI最强选手,和yjq关系很好,被当时的我视为目标。 f321dd:初中同学,朋友,初中经常一起逃课打牌(自己搞了个叫化学杀的东西),感觉是个有趣的人。 grh:四中来的,高高瘦瘦的,喜欢看本子和动画片。 ziliuziliu:四中来的,瘦瘦的,喜欢玩坦克世界,练了KV3这条线,天天AP打不穿WZ111,水平不错。 cyz:喜欢玩坦克世界,印象中第一次看到他玩是在玩四号防空车,然后我觉得好玩也入坑了,水平挺高的,感觉经常无法理解他在想什么。 Flaze:女oier,感觉挺可爱的。 zyx:外地生,没学过oi。 cx:胖胖的,会写oj。 zqq:和Flaze一个初中的,感觉挺踏实的(最开始是这样的),什么知识点都会去学。 学长: yjq:特别强,天天比赛早早做完AK。 Karl_duan:感觉一直在学习,很踏实努力。 zcy:特别会乱搞,平时也经常乱搞过题,NOIP暴力拿了600。 mhy:集训队学长,瘦瘦的。 写下这个回忆录的时候我还是挺有感触的,回忆起当时的事情让我很开心~ 学oi的那一阵子虽然我很菜,天天被吊打,但无疑还是快乐的。 【记得配图,内容oj7】 由于这是Ynoi,不是出题人拿来写怀旧的文字的地方,所以你需要做一个数据结构题:

题目描述

有一个长度为 $n$ 的数组 $A$。下标从 $1$ 开始标号。有 $m$ 个操作需要处理,操作有如下四种: 1. 在数组 $A$ 的末尾添加一个数 $x$。 2. 输出 $\sum_{i=l}^{r}A_i$。 3. 将数组 $A$ 中的每个数 $A_i$ 都改为 $A_i\oplus x$。($\oplus$ 表示异或操作)。 4. 将数组 $A$ 从小到大排序。

输入输出格式

输入格式


第一行一个数 $n$ 表示 $A$ 的初始大小。 接下来一行 $n$ 个非负整数 $A_i$,表示 $A$ 的中的每个元素。 接下来一行一个数 表示询问的数量。 接下来 $m$ 行,每行表示一个操作: - `1 x`: 表示第一种操作,在末尾插入数 $x$。 - `2 l r`:表示第二种操作,询问 $\sum_{i=l}^{r}A_i$。保证有 $1\le l\le r\le n'$,其中 $n'$ 为操作时刻序列的长度。 - `3 x`:表示第三种操作,给每个数 $\oplus$ 上 $x$。 - `4`:表示第四种操作,将数组 $A$ 排序。

输出格式


对于每个第二种操作,输出答案。

输入输出样例

输入样例 #1

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

输出样例 #1

15
23

说明

Idea:WJMZBMR,Solution:WJMZBMR,Code:WJMZBMR,Data:WJMZBMR $1\le n,\,m\le 10^5, 0\le x,A_i\le 10^9$