NC14113. Squared Permutation
描述
输入描述
第一行是一个正整数T(≤ 10)，表示测试数据的组数，
对于每组测试数据，
第一行是一个整数n(1 ≤ n ≤ 100000)，
第二行包含一个1,2,3,...,n的排列，其中第i个数表示第i张牌上的数字，
第三行是一个整数q(0 ≤ q ≤ 100000)，表示操作数，
接下来q行，每行包含三个整数op(1 ≤ op ≤ 2),l,r，其中op表示操作的类型。
输出描述
对于每组测试数据，依次输出所有查询操作的结果，每个结果一行。
示例1
输入:
1 3 1 2 3 3 2 1 2 1 1 3 2 2 3
输出:
3 5
说明:
第二次操作后牌上的数字从左往右依次是3,2,1，C++(clang++ 11.0.1) 解法, 执行用时: 391ms, 内存消耗: 7596K, 提交时间: 2023-07-18 15:18:25
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,M=2e5+10;
ll n,q,a[N],num[N],op,l,r,b[N];
inline ll lb(ll x){return (x&(-x));}
void add(ll x,ll y){for(;x<=n;x+=lb(x))a[x]+=y;}
ll query(ll x){ll s=0;for(;x;x-=lb(x))s+=a[x];return s;}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll T;cin>>T;while(T--){
cin>>n;
memset(a,0,sizeof a);
for(ll i=1;i<=n;i++)cin>>num[i],b[num[i]]=i;
for(ll i=1;i<=n;i++)add(i,num[num[i]]);
cin>>q;
while(q--){
cin>>op>>l>>r;
if(op==1){
if(b[l]!=l&&b[l]!=r){
add(b[l],-num[l]);
add(b[l],num[r]);
}
if(b[r]!=r&&b[r]!=l){
add(b[r],-num[r]);
add(b[r],num[l]);
}
add(r,-num[num[r]]);
add(l,-num[num[l]]);
swap(num[l],num[r]);
add(r,num[num[r]]);
add(l,num[num[l]]);
b[num[r]]=r;
b[num[l]]=l;
}else cout<<query(r)-query(l-1)<<'\n';
}
}
return 0;
}
//By _frog
//sto Froggy orz