[ZJ b379][NPSC 2014] D. 蚯蚯(扭)

剛好ZJ的解題數到30%了，NPSC 2014的題目又還沒傳到ZJ，所以就先試試看怎麼新增題目，把這年決賽的題目都加進去了。

這題我比賽時寫的作法是離線作，把每個操作記錄起來，然後每遇到一個詢問就循著這些操作往回推，輸出解。根據目前詢問的區間和被操作的區間會分成很多種可能，還要考慮現在這一段有沒有被反過來，還蠻麻煩的不過細心一點應該就OK了。

官方解是可持久化Treap，而他也是可持久化Treap的標準題型，之後可能有空(?)會補上code。關於可持久化Treap，可以看看：

随机平衡二叉查找树Treap 的分析与应用

可持久化平衡树

可持久化数据结构研究

code :

#include<bits/stdc++.h>
using namespace std;
 
struct P{int tp,l,r ;};
vector<P> v ;
char s[20001] ;
 
void query(int x,int l,int r,int inv)
{
    //printf("\nquery %d %d %d %d\n",x,l,r,inv) ;
    if(l>r) return ;
    if(x==0)
    {
        if(!inv) for(int i=l;i<=r;i++) putchar(s[i]) ;
        else for(int i=r;i>=l;i--) putchar(s[i]) ;
        return ;
    }
    int tp=v[x-1].tp , L=v[x-1].l , R=v[x-1].r ;
    if(tp==2)
    {
        if(l>R) query(x-1,l-(R-L+1),r-(R-L+1),inv) ;
        else if(r<=R) query(x-1,l,r,inv) ;
        else if(!inv)
        {
            query(x-1,l,R,0) ;
            query(x-1,R+1-(R-L+1),r-(R-L+1),0) ;
        }
        else
        {
            query(x-1,R+1-(R-L+1),r-(R-L+1),1) ;
            query(x-1,l,R,1) ;
        }
    }
    else if(tp==3)
    {
        if(r<L) query(x-1,l,r,inv) ;
        else if(l>R) query(x-1,l,r,inv) ;
        else if(l<L && r>=L && r<=R)
        {
            if(!inv)
            {
                query(x-1,l,L-1,0) ;
                query(x-1,L+R-r,R,1) ;
            }
            else
            {
                query(x-1,L+R-r,R,0) ;
                query(x-1,l,L-1,1) ;
            }
        }
        else if(l>=L && l<=R && r>R)
        {
            if(!inv)
            {
                query(x-1,L,L+R-l,1) ;
                query(x-1,R+1,r,0) ;
            }
            else
            {
                query(x-1,R+1,r,1) ;
                query(x-1,L,L+R-l,0) ;
            }
        }
        else if(l<L && r>R)
        {
            if(!inv)
            {
                query(x-1,l,L-1,0) ;
                query(x-1,L,R,1) ;
                query(x-1,R+1,r,0) ;
            }
            else
            {
                query(x-1,R+1,r,1) ;
                query(x-1,L,R,0) ;
                query(x-1,l,L-1,1) ;
            }
        }
        else if(l>=L && l<=R && r>=L && r<=R)
        {
            if(!inv) query(x-1,L+R-r,L+R-l,1) ;
            else query(x-1,L+R-r,L+R-l,0) ;
        }
    }
}
 
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int n,m ; scanf("%d%d%s",&n,&m,s+1) ;
        v.clear() ; int cnt=0 ;
        for(int i=1;i<=m;i++)
        {
            int tp,l,r ; scanf("%d%d%d",&tp,&l,&r) ;
            if(tp==2 || tp==3) v.push_back((P){tp,l,r}) , cnt++ ;
            else
            {
                query(cnt,l,r,0) ;
                printf("\n") ;
            }
        }
    }
}