bnu 51636 Squared Permutation 线段树

Squared Permutation

Time Limit: 6000ms

Memory Limit: 262144KB

64-bit integer IO format: %lld      Java class name: Main

最近，无聊的过河船同学在玩一种奇怪的名为“小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

第十四届北京师范大学程序设计竞赛决赛

思路：很显然用线段树，但是发现线段树在更新两点会有后效；

　　　最多更新四个点；注意的是先更新flag数组；

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define mod 1000000007
#define inf 999999999
int scan()
{
    int res = 0 , ch ;
    while( !( ( ch = getchar() ) >= '0' && ch <= '9' ) )
    {
        if( ch == EOF ) return 1 << 30 ;
    }
    res = ch - '0' ;
    while( ( ch = getchar() ) >= '0' && ch <= '9' )
        res = res * 10 + ( ch - '0' ) ;
    return res ;
}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll a[100010],flag[100010];
struct is
{
    ll l,r;
    ll sum;
}tree[100010*5];
void buildtree(ll l,ll r,ll pos)
{
    tree[pos].l=l;
    tree[pos].r=r;
    if(l==r)
    {
        tree[pos].sum=a[a[l]];
        return;
    }
    ll mid=(l+r)/2;
    buildtree(l,mid,pos*2);
    buildtree(mid+1,r,pos*2+1);
    tree[pos].sum=tree[pos*2].sum+tree[pos*2+1].sum;
}
void update(ll point,ll change,ll pos)
{
    if(tree[pos].l==point&&tree[pos].r==point)
    {
        tree[pos].sum=change;
        return;
    }
    ll mid=(tree[pos].l+tree[pos].r)/2;
    if(point<=mid)
    update(point,change,pos*2);
    else
    update(point,change,pos*2+1);
    tree[pos].sum=tree[pos*2].sum+tree[pos*2+1].sum;
}
ll query(ll l,ll r,ll pos)
{
    if(tree[pos].l==l&&tree[pos].r==r)
    {
        return tree[pos].sum;
    }
    ll mid=(tree[pos].l+tree[pos].r)/2;
    if(mid>=r)
    return query(l,r,pos*2);
    else if(mid<l)
    return query(l,r,pos*2+1);
    else
    return query(l,mid,pos*2)+query(mid+1,r,pos*2+1);
}
int main()
{
    ll x,y,z,i,t;
    int gg;
    scanf("%d",&gg);
    while(gg--)
    {
        scanf("%lld",&x);
        for(i=1;i<=x;i++)
        {
            scanf("%lld",&a[i]);
            flag[a[i]]=i;
        }
        buildtree(1,x,1);
        scanf("%lld",&y);
        while(y--)
        {
            ll op,l,r;
            scanf("%lld%lld%lld",&op,&l,&r);
            if(op==1)
            {
                ll hh=query(l,l,1);
                ll kk=query(r,r,1);
                ll hhh=query(flag[l],flag[l],1);
                ll kkk=query(flag[r],flag[r],1);
                update(l,kk,1);
                update(r,hh,1);
                flag[a[l]]=r;
                flag[a[r]]=l;
                update(flag[l],kkk,1);
                update(flag[r],hhh,1);
                swap(a[l],a[r]);
                /*for(i=1;i<=x;i++)
                cout<<a[i]<<" ";
                cout<<endl;
                for(i=1;i<=x;i++)
                cout<<flag[i]<<" ";
                cout<<endl;
                for(i=1;i<=x;i++)
                cout<<query(i,i,1)<<" ";
                cout<<endl;*/
            }
            else
            {
                printf("%lld
",query(l,r,1));
            }
        }
    }
    return 0;
}