智商持续掉线。
考虑题目其实是让维护$a[a[i]]$的和，那就直接用BIT维护。
发现当我们swap的时候（以$a[l]$）为例：只有两种情况的点权值（设点编号为$x$）会发生改变：
$1. a[x] = a[l], 即x = l$
$2. a[x] = l, 即a[a[x]] = a[l]$
维护一个pos即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
typedef long long Int;
int n, m;
int a[N] , pool[N];
Int pre[N], c[N];
void pu(int u, Int w) {for(; u <= n; u += (u & -u)) c[u] += w;}
Int query(int u) {Int ans = 0;for(; u; u -= (u & -u)) ans += c[u]; return ans;}
void solve() {
memset(c, 0, sizeof(c));
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) pu(i, a[a[i]]), pool[a[i]] = i;
scanf("%d", &m);
while(m--) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
if(l > r) swap(l, r);
if(op == 1) {
// #1 : 修改l,r
// l -> a[a[l]] a[l] -> a[r]
if(pool[l] != l && pool[l] != r) pu(pool[l], -a[l]),pu(pool[l], a[r]);
if(pool[r] != l && pool[r] != r)pu(pool[r], -a[r]), pu(pool[r], a[l]);
pu(l, -a[a[l]]); pu(r, -a[a[r]]);
swap(a[l], a[r]);
pu(l, a[a[l]]); pu(r, a[a[r]]);
pool[a[l]] = l;
pool[a[r]] = r;
}
else if(op == 2) {
printf("%lld\n", query(r) - query(l - 1));
}
}
}
int main(){
int t; scanf("%d", &t);
while(t--) solve();
return 0;
}