BNUOJ 51636
最近，无聊的过河船同学在玩一种奇怪的名为“小Q的恶作剧”的纸牌游戏。
现在过河船同学手有张牌，分别写着，打乱顺序之后排成一行，位置从左往右按照标号。
接下来小Q同学会给出个操作，分为以下两种：
1.给定，交换从左往右数的第和第张牌，
2.给定，对从左往右数的第张牌，记下位置是这张牌上的数字的牌的数字，询问所有记下的数字加起来的结果。
虽然无聊的过河船同学精通四则运算，但是要完成这么大的计算量还是太辛苦了，希望你能帮他处理这些操作。
Input
第一行是一个正整数，表示测试数据的组数，
对于每组测试数据，
第一行是一个整数，
第二行包含一个的排列，其中第个数表示第张牌上的数字，
第三行是一个整数，表示操作数，
接下来行，每行包含三个整数，其中表示操作的类型。
Output
对于每组测试数据，依次输出所有查询操作的结果，每个结果一行。
Sample Input
1
3
1 2 3
3
2 1 2
1 1 3
2 2 3
Sample Output
3
5
Hint
对于样例，
第二次操作后牌上的数字从左往右依次是3,2,1，
第三次操作的结果是位置是第2张牌上的数字的牌的数字加上位置是第3张牌上的数字的牌的数字，也就是第2张牌上的数字加上第1张牌上的数字，结果是5。
Source
第十四届北京师范大学程序设计竞赛决赛
思路：使用树状数组可以方便的求某个连续序列的和；
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
long long s[
100100];
int a[
100100],b[
100100],flag[
100100],t,n,m,Time;
int f[
10],tot;
int lowbit(
int x)
{
return x & (-
x);
}
void update(
int x,
long long y)
{
while(x <=
n)
{
s[x] +=
y;
x +=
lowbit(x);
}
}
long long getsum(
int x)
{
long long tmp =
0;
while(x >
0)
{
tmp +=
s[x];
x -=
lowbit(x);
}
return tmp;
}
int main(){
scanf("%d",&
t);
while(t--
)
{
scanf("%d",&
n);
for(
int i =
1;i <= n;i++
)
{
scanf("%d",&
a[i]);
b[a[i]] =
i;
s[i] =
0;
}
for(
int i =
1;i <= n;i++
)update(i,a[a[i]]);
scanf("%d",&
m);
for(
int i =
1;i <= m;i++
)
{
int op,l,r;
scanf("%d%d%d",&op,&l,&
r);
if(op ==
1)
{
Time++
;
tot =
2;
f[1] =
l;
f[2] =
r;
flag[l] =
Time;
flag[r] =
Time;
if(flag[b[l]] !=
Time)
{
++
tot;
f[tot] =
b[l];
flag[b[l]] =
Time;
}
if(flag[b[r]] !=
Time)
{
++
tot;
f[tot] =
b[r];
flag[b[r]] =
Time;
}
for(
int i =
1;i <= tot;i++
)
update(f[i],-
a[a[f[i]]]);
swap(a[l],a[r]);
b[a[l]] =
l;
b[a[r]] =
r;
for(
int i =
1;i <= tot;i++
)
update(f[i],a[a[f[i]]]);
}
else printf(
"%lld\n",getsum(r)-getsum(l-
1));
}
}
return 0;
}
转载于:https://www.cnblogs.com/chen9510/p/5497458.html
