AT_ijpc_training 魔法の訓練 (Magical Training)

いもす是14岁时就进行了魔法觉醒的魔法少女。 いもす为了打倒161天以后即将来临的强敌「ウォーターリークス」，开始进行提高魔力的训练。这个训练是这样的： 一开始，有$N$个魔力值已给出的魔法石排成一列。 现在选择连续的一些魔法石，将它们按照魔力值从小到大排序，也就是说，将魔力值小的魔法石放在较小的编号上这样的训练，可以提高いもす的魔力。每一块魔法石都很重，所以排序的时候只能用魔法交换相邻的两块魔法石。 但是，魔法石有很多，交换魔法石的顺序是相当艰难的。又因为交换的方案有很多，所以いもす选择的是最轻松的方案。而且，魔法石的魔力值会在某些时间点突然发生变化。十分幸运的是，这些变化已经全部被预测了。 为了帮助いもす的魔法训练，请你写一个程序支持如下操作： 题目将给出一个包含$N$个整数的排列$A(A_0…A_{N-1})$，其中从左往右第$i+1$个魔法石的编号为$i$，$A_i$表示$i$号魔法石的魔力值。 要实现的操作如下： + 含有参数的过程$init(N,A)$: + $N$——魔法石的个数。魔法石的编号从左至右依次为$0...N-1$ + $A$——表示魔法值的整数的序列。保证对$0\le i< N$有$1\le A_i\le N$            这个过程只在update和train之前出现一次，没有返回值。 + 含有参数的过程$update(i,x)$: + $i$——魔力值变动的魔法石编号 + $x$——魔力变动后魔法石$i$的魔力值。保证$1\le x\le N$            这个过程被多次调用，一次调用对应一次魔力值的变化，没有返回值。 + 含有参数的过程$train(p,q)$: + $p$——选择的魔法石序列的左端魔法石编号。保证$1\le p< N$ + $q$——选择的魔法石序列的右端魔法石编号。保证$p\le q< N$            这个过程被多次调用，一次调用对应从魔法石$p$到魔法石$q$（两端也包含），通过更换相邻的魔法石，达到升序排列的训练。需要返回作为对应的训练所需的最小的魔法石交换次数。但是，实际不进行魔法石的交换，只要求交换的次数。 #### 举个例子 当$N=6$时，$A$为$(4,1,2,2,6,5)$时，进行如下的$7$次操作 |操作 | 输出 | | :----------- | :----------- | | $train(0, 5)$ | $4$ | | $train(2, 3)$ | $0$ | | $update(1, 5)$ | 无 | | $train(0, 5)$ | $5$ | | $train(1, 4)$ | $2$ | | $update(5, 1)$ | 无 | | $train(0, 5)$ | $9$ | ## 数据规模 设$update$和$train$的调用次数为$P,Q$ ### 部分1（12分） $1\le N\le 100$ $1\le P+Q\le 200$ ### 部分2（18分） $1\le N\le 5000$ $1\le P+Q\le 10000$ ### 部分3（30分） $1\le N\le 30000$ $P=0$ $1\le Q\le 20000$ ### 部分4（40分） $1\le N\le 30000$ $1\le P+Q\le 20000$

第一行包含一个数$N$，表示魔法石总数。 第二行包含$N$个整数$A_0...A_{N-1}$，表示魔法石的魔法值。 第三行包含一个数$M$，表示操作个数。 接下来的$M$行，每行有三个整数$T_i,X_i,Y_i$。$T_i=0$时调用$update(X_i,Y_i)$，$T_i=1$时调用$train(X_i,Y_i)$。

对于每一个$train$操作，输出一行，包含一个数，为最少交换次数。 ## 输入输出样例 ### 输入样例#1 6 4 1 2 2 6 5 7 1 0 5 1 2 3 0 1 5 1 0 5 1 1 4 0 5 1 1 0 5 ### 输出样例#1 4 0 5 2 9