9042: NoCruelty
内存限制：1024 MB
时间限制：3 S
题面：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
Given a sequence of integers a1,…,ana_1,\dots,a_na1,…,an , you need to process mmm operations.
In an operation l,r,xl,r,xl,r,x , you need to update the sequence first, and then query how many different values are there in a1,…,axa_1,\dots,a_xa1,…,ax .When l≤rl\le rl≤r , the update is sort al,…,ara_l,\dots,a_ral,…,ar according to ascending order, or the update is sort ar,…,ala_r,\dots,a_lar,…,al according to descending order.
1≤ai≤n1\le a_i\le n1≤ai≤n
1≤l,r,x≤n1\le l,r,x\le n1≤l,r,x≤n
1≤n,m≤1051\le n,m\le 10^51≤n,m≤105
输入格式
The first line contains two integers n,mn,mn,m .
The next line contains nnn integers a1,…,ana_1,\dots,a_na1,…,an .
For the next mmm lines, each line contains three integers l⊕c,r⊕c,x⊕cl\oplus c,r\oplus c,x\oplus cl⊕c,r⊕c,x⊕c , means an operation l,r,xl,r,xl,r,x. Where ⊕\oplus⊕ is bitwise XOR, and ccc is the answer to the last operation (especially, c=0c=0c=0 for the first operation).
The next line contains nnn integers a1,…,ana_1,\dots,a_na1,…,an .
For the next mmm lines, each line contains three integers l⊕c,r⊕c,x⊕cl\oplus c,r\oplus c,x\oplus cl⊕c,r⊕c,x⊕c , means an operation l,r,xl,r,xl,r,x. Where ⊕\oplus⊕ is bitwise XOR, and ccc is the answer to the last operation (especially, c=0c=0c=0 for the first operation).
输出格式
For each operation, output an integer in a line representing the answer.
输入样例 复制
9 7
2 2 8 8 2 8 2 1 3
2 2 2
3 7 6
6 7 1
9 6 7
10 11 10
7 0 5
5 1 7输出样例 复制
1
2
1
2
3
2
2