决战
题目背景
Steve成功突破了水晶防御,即将和黑暗势力进行决战
题目描述
然而黑暗势力具有改变地形的能力,给军队的前进造成了很大困难
为了使军队更快前进,Steve将核武器带到了前线,用来破坏地形
另外,Steve很关心当前的地形情况
具体地说,前线的地形可分为$n$段,初始高度为0,决战时会发生$m$个事件,事件可以是:
1.Steve询问区间$[l,r]$内,有几段小于给定的高度$h$
2.Steve使用核武器,使得区间$[l,r]$内高度大于$h$的段的高度减少到$h$
3.黑暗势力改变地形,使得区间$[l,r]$内高度小于$h$的段的高度增加到$h$
由于战事非常紧迫,所以部分测试点强制在线
对于$k=1$的测试点,设上次事件1的答案为$lastans$,你需要将$l,r,h$分别与$lastans$取异或后得到实际数值,如果还没有回答过事件1,那么$lastans=0$
输入输出格式
输入格式
第一行$3$个整数$n,m,k$
接下来$m$行,每行$4$个整数,描述一个事件
第一个整数$opt$表示事件种类
接下来$3$个整数$l,r,h$,含义如题所述
输出格式
对于每个事件$1$,输出一行一个整数,表示询问的答案
输入输出样例
输入样例 #1
10 8 0
1 1 5 1
3 1 3 5
1 1 5 3
2 2 3 3
1 1 5 3
1 1 5 5
3 3 4 2
1 1 5 3
输出样例 #1
5
2
2
4
2
说明
样例解释:
```
[00000]00000=>5[TTTTT]
[000]0000000
[55500]00000=>2[FFFTT]
5[55]0000000
[53300]00000=>2[FFFTT]
[53300]00000=>4[FTTTT]
53[30]000000
[53320]00000=>2[FFFTT]
```
数据范围:
对于所有数据,保证$1\le l \le r \le n,0\le h \le 10^9$
Subtask1是比赛时的数据
测试点| 分值| n | m| 特殊性质
:-: | :-: | :-: | :-: | :-:
1| 4| 1000| 1000| |
2| 14| 100000| 100000| $h\le 1$|
3| 11| 100000| 100000| |
4| 10| $10^9$| 1000| |
5| 12| $10^9$| 100000| $k=1,h\le 1$|
6| 14| $10^9$| 100000| *|
7| 16| $10^9$| 100000| |
8| 19| $10^9$| 100000| $k=1$|
对于第$6$个测试点,保证所有事件$1$都在事件$2$和$3$之后
Subtask2为不计分的Hack数据
现在仅包含一组数据,满足#8的性质
$\color{white}\texttt{不保证数据随机}$