解题报告

这题好像挺水的……手玩下会发现如果两个相邻元素没有正确排序，那么他们就会在最终序列里并起来。

比如：4 1 3 2 -> (4 1) (3 2) -> (3 2) (4 1) -> 3 2 4 1。

因为对于 $(x,y),x>y$ ，轮到 $x$ 归并的时候 $y$ 肯定是下一个，即两个会一直相邻。

所以我们对于 $x$ ，分类讨论一下，讨论 $x$ 有没有和相邻元素正确排序，以及 $x$ 和相邻元素的大小关系，就可以计算出每种情况下比 $x$ 小的中有多少个需要被比 $x$ 大的绑起来，变成一个二维偏序问题，可以树套树解决。

不过这道题的二维偏序问题可以转成序列问题，是可以不用树套树的……

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1<<16,maxt=1e7,MOD=1e9+7;

int n,te,a[maxn],ro[maxn+5],si,ls[maxt+5],rs[maxt+5],sum[maxt+5],ans;
int pw[maxn+5],INV[maxn+5],fac[maxn+5],m;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Make(int n){
    pw[0]=1;for (int i=1;i<=n;i++) pw[i]=((LL)pw[i-1]<<1)%MOD;m=Pow(pw[n>>1],MOD-2);
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD;
}
#define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD)
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
void Insert(int &p,int pos,int k,int l=1,int r=n){
    if (!p) p=++si;sum[p]+=k;if (l==r) return;int mid=l+(r-l>>1);
    if (pos<=mid) Insert(ls[p],pos,k,l,mid); else Insert(rs[p],pos,k,mid+1,r);
}
int Ask(int p,int L,int R,int l=1,int r=n){
    if (!p) return 0;if (L==l&&r==R) return sum[p];int mid=l+(r-l>>1);
    if (R<=mid) return Ask(ls[p],L,R,l,mid); else if (L>mid) return Ask(rs[p],L,R,mid+1,r);
    else return Ask(ls[p],L,mid,l,mid)+Ask(rs[p],mid+1,R,mid+1,r);
}
inline void Update(int x,int y,int f) {for (int i=x;i<=n;i+=i&-i) Insert(ro[i],y,f);}
inline int Sum(int x,int L,int R) {int sum=0;for (int i=x;i;i-=i&-i) sum+=Ask(ro[i],L,R);return sum;}
inline void Change(int x,int y,int f) {if (x<y) Update(x,y,f); else Update(y,x,f);}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);for (int i=0;i<n;i++) readi(a[i]);for (int i=0;i<n;i+=2) Change(a[i],a[i^1],1);
    for (Make(n),readi(te);te;te--){
        int tp,x,y;readi(tp);readi(x);readi(y);x--;ans=0;
        if (tp==2){
            if (a[x]>a[x^1]){
                int k=a[x],num=Sum(k-1,k+1,n),cnt;
                cnt=k-y;if (0<=cnt&&cnt<=num) AMOD(ans,(LL)C(num,cnt)*pw[(n>>1)-num-1]%MOD);
                cnt=k-y-1;if (y<n&&0<=cnt&&cnt<=num) AMOD(ans,(LL)C(num,cnt)*pw[(n>>1)-num-1]%MOD);
            } else{
                int k=a[x],num=Sum(k-1,k+1,n),cnt;
                cnt=k-y;if (0<=cnt&&cnt<=num) AMOD(ans,(LL)C(num,cnt)*pw[(n>>1)-num-1]%MOD);
                k=a[x^1];y--;num=Sum(k-1,k+1,n);
                cnt=k-y-1;if (y&&0<=cnt&&cnt<=num) AMOD(ans,(LL)C(num,cnt)*pw[(n>>1)-num-1]%MOD);
            }ans=(LL)ans*m%MOD;printf("%d\n",ans);
        } else{
            y--;if (x==y) continue;
            Change(a[x],a[x^1],-1);Change(a[y],a[y^1],-1);
            swap(a[x],a[y]);Change(a[x],a[x^1],1);Change(a[y],a[y^1],1);
        }
    }return 0;
}