出题人题解|魔术

T5_魔术 题解

$C\in{[1,2]}$

暴力模拟即可。时间复杂度：$O(NM)$

$C\in[3,5]$

没有交换操作，考虑对 $a$ 作前缀和达到 $O(1)$ 查询即可。

    for(int i = 1;i<=n;++i){					
        cin>>a[i];					
        sum[i] = sum[i-1]+a[i];					
    }					
//----------------//中间省略不写					
    while(m--){					
        int opt,l,r;					
        cin>>opt>>l>>r;					
        cout<<sum[r]-sum[l-1]<<'\n';					
    }					

$C\in[6,10]$

留给平衡树的分，应该没人用这个，省略掉。重点讲后面的。

$C\in[11,20](\tt{AC})$

题目需要支持区间交叉交换以及区间查询，考虑线段树。然后考虑如何维护线段树信息和 $tag$。

首先考虑在线段树的节点处维护三个序列在对应区间的和。然后对于区间交叉交换操作维护一个置换，这个置换的初值为 $\{0,1,2\}$，表示不交换。

举个例子，当我们要交换 $a,b$ 时，除了对维护的和交换，还需将置换 $\{1,0,2\}$，表示交换前两个值。其他交换如此。这样 $tag$ 的下传就可以看作根据父节点的置换对子节点的信息进行交换或者复合。就解决了交叉互换问题。

#include<bits/stdc++.h>					
using namespace std;					
typedef long long ll;					
const int N = 500005;					
int n,q,a[3][N];					
struct node{int a[3];					
	inline node operator*(node b){				
        node c;					
		for(int i = 0;i<=2;++i){			
            c.a[i] = a[b.a[i]];				//打置换	
        }					
		return c;			
	}				
}tr[N<<2],tg[N<<2],A,B,C,O;					
inline void add(int u,node x){					
	tr[u] = tr[u]*x;				
    tg[u] = tg[u]*x;					
}					
inline void tag(int u){					
	add(u<<1,tg[u]);				
    add(u<<1|1,tg[u]);					
    tg[u] = O;					
}					
inline void push(int u){					
	for(int i = 0;i<=2;++i){				
    	tr[u].a[i] = tr[u<<1].a[i]+tr[u<<1|1].a[i];				
    }					
}					
inline void build(int u,int l,int r){					
    tg[u] = O;					
	if(l == r){				
		for(int i = 0;i<=2;++i){			
    		tr[u].a[i] = a[i][l];			
        }					
        return;					
	}				
    int mid = l+r>>1;					
	build(u<<1,l,mid);				
    build(u<<1|1,mid+1,r);					
    push(u);					
}					
inline void upd(int u,int l,int r,int L,int R,node x){					
	if(R<l||r<L) return;				
	if(L<=l&&r<=R){				
        add(u,x);					
        return;					
    }					
	int mid = l+r>>1;				
    tag(u);					
	upd(u<<1,l,mid,L,R,x);				
	upd(u<<1|1,mid+1,r,L,R,x);				
    push(u);					
}					
inline int query(int u,int l,int r,int L,int R){					
	if(R<l||r<L) return 0;				
	if(L<=l&&r<=R) return tr[u].a[0];				
	int mid = l+r>>1;				
    tag(u);					
	return query(u<<1,l,mid,L,R)+query(u<<1|1,mid+1,r,L,R);				
}					
int Cid;					
int main(){					
    scanf("%d%d%d",&Cid,&n,&q);					
	O.a[0] = 0,O.a[1] = 1,O.a[2] = 2;				
	A.a[0] = 1,A.a[1] = 0,A.a[2] = 2;				
	B.a[0] = 2,B.a[1] = 1,B.a[2] = 0;				
	C.a[0] = 0,C.a[1] = 2,C.a[2] = 1;				//预处理所有置换情况
	for(int i = 0;i<=2;++i){				
        for(int j = 1;j<=n;++j){					
            scanf("%d",&a[i][j]);					
        }					
    }					
	build(1,1,n);				
	while(q--){				
        int opt,l,r;					
        scanf("%d%d%d",&opt,&l,&r);					
		if(opt == 0) upd(1,1,n,l,r,A);			
		if(opt == 1) upd(1,1,n,l,r,B);			
		if(opt == 2) upd(1,1,n,l,r,C);			
		if(opt == 3) printf("%d\n",query(1,1,n,l,r));			
	}				
}					

时间复杂度：$O(NlogN)$