本文共 2284 字，大约阅读时间需要 7 分钟。

链接：https://ac.nowcoder.com/acm/problem/14113

来源：牛客网

题目描述

最近，无聊的过河船同学在玩一种奇怪的名为“小Q的恶作剧”的纸牌游戏。 现在过河船同学手有n张牌，分别写着1,2,3,…,n，打乱顺序之后排成一行，位置从左往右按照1,2,3,…,n标号。 接下来小Q同学会给出q个操作，分为以下两种： 1.给定l,r(1 ≤ l<r ≤ n)，交换从左往右数的第l和第r张牌， 2.给定l,r(1 ≤ l ≤ r ≤ n)，对从左往右数的第i(l ≤ i ≤ r)张牌，记下位置是这张牌上的数字的牌的数字，询问所有记下的数字加起来的结果。 虽然无聊的过河船同学精通四则运算，但是要完成这么大的计算量还是太辛苦了，希望你能帮他处理这些操作。 输入描述: 第一行是一个正整数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， 第三次操作的结果是位置是第2张牌上的数字的牌的数字加上位置是第3张牌上的数字的牌的数字，也就是第2张牌上的数字加上第1张牌上的数字，结果是5。 很扯淡的一道题，卡了很久。 一开始就是单纯的把两个位置的交换过来。但是wa了之后手画了几组样例，发现单纯的交换不行，会有后效性，于是手动模拟了几组样例，发现除了交换l,r两个位置上的数字不行，还要交换l和r两个数字在数组中的位置posl,posr上的数字。自己找的规律，不知道咋证明。路过的大佬指点一波。 代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=1e5+100;struct node{
   	int l;	int r;	ll sum;}p[maxx<<2];int a[maxx];int b[maxx];int n,m;inline void pushup(int cur){
   	p[cur].sum=p[cur<<1].sum+p[cur<<1|1].sum;}inline void build(int l,int r,int cur){
   	p[cur].l=l;	p[cur].r=r;	p[cur].sum=0;	if(l==r)	{
   		p[cur].sum=1ll*a[a[l]];		return ;	}	int mid=l+r>>1;	build(l,mid,cur<<1);	build(mid+1,r,cur<<1|1);	pushup(cur);}inline void update(int pos,int cur){
   	int L=p[cur].l;	int R=p[cur].r;	if(L==R)	{
   		p[cur].sum=1ll*a[a[L]];		return ;	}	int mid=L+R>>1;	if(pos<=mid) update(pos,cur<<1);	else update(pos,cur<<1|1);	pushup(cur);}inline ll query(int l,int r,int cur){
   	int L=p[cur].l;	int R=p[cur].r;	if(l<=L&&R<=r) return p[cur].sum;	int mid=L+R>>1;	if(r<=mid) return query(l,r,cur<<1);	else if(l>mid) return query(l,r,cur<<1|1);	else return (query(l,mid,cur<<1)+query(mid+1,r,cur<<1|1));}int main(){
   	int t,op,l,r;	scanf("%d",&t);	while(t--)	{
   		scanf("%d",&n);		for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[a[i]]=i;		build(1,n,1);		scanf("%d",&m);		while(m--)		{
   			scanf("%d%d%d",&op,&l,&r);			if(op==1)			{
   				int x=a[l];				a[l]=a[r];				a[r]=x;				b[a[r]]=r;b[a[l]]=l;				update(l,1);				update(r,1);				update(b[l],1);				update(b[r],1);//b[i]代表着i这个数在数组中的位置。			}			else if(op==2)			{
   				printf("%lld\n",query(l,r,1));			}		}	}	return 0;}
   

努力加油a啊，(^o)/~

转载地址：http://gytvi.baihongyu.com/