#BZOJ3787. Gty的文艺妹子序列
-
ID: 2347
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
Gty的文艺妹子序列
No submission language available for this problem.
题目描述
Autumn终于会求区间逆序对了!Bakser神犇决定再考验一下他，他说道：
“在Gty的妹子序列里，某个妹子的美丽度可也是会变化的呢。你还能求出某个区间
中妹子们美丽度的逆序对数吗？当然，为了方便，这次我们规定妹子们的美丽度在
[1,n]中。仍然强制在线。”
Autumn需要你的帮助。
给定一个正整数序列a(1<=ai<=n)，支持单点修改，对于每次询问，输出al...ar中
的逆序对数，强制在线。
输入格式
第一行包括一个整数n(1<=n<=50000),表示数列a中的元素数。
第二行包括n个整数a1...an(1<=ai<=n)。
接下来一行包括一个整数m(1<=m<=50000),表示操作的个数。
接下来m行,每行包括3个整数。
0 L R (1<=L<=R<=n) 询问[L,R]中的逆序对数。
1 p v (1<=p<=n,1<=v<=n) 将p位置的数修改为v。
L,R,p,v 都需要异或上一次的答案，保证异或之后的值是合法的。
保证涉及的所有数在int内。
输出格式
对每个询问，单独输出一行，表示al...ar中的逆序对数。对每个询问，单独输出一行，表示al...ar中的逆序对数。
10
1 7 5 6 9 4 9 4 4 7
10
0 4 6
0 5 8
0 1 10
1 25 19
0 19 25
1 14 4
0 12 12
0 2 5
1 8 7
1 1 10
2
3
16
13
0
2