7787: BZOJ3787：Gty的文艺妹子序列

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

提示

没有写明提示

题目来源

By Autumn