[DS记录]P5312 [Ynoi2011] 竞赛实验班
command_block
2021-06-29 09:55:32
**题意** : 给出长为 $n$ 的数组 $A$ ，支持下列操作 ：
1. 在数组 $A$ 的末尾添加一个数 $x$。
2. 区间求和。
3. 将数组 $A$ 中的每个数 $A_i$ 都改为 $A_i\oplus x$。（$\oplus$ 表示异或操作）。
4. 将数组 $A$ 从小到大排序。
$n,m\leq 10^5$ ，时限$\texttt{1s}$，空限$\texttt{500M}$。
------------
若不存在操作 3 ，序列肯定形如一段排好序的以及一段未排序的，而且排好序的段只会延长。
对于排好序的数，用权值线段树维护，区间求和可以转化为前 $k$ 小求和。
对于未排序的部分，直接用树状数组维护。
接下来考虑操作 3。
记下两类标记，一类是全局异或标记 $t$，一类是排序段排序时的异或标记 $t'$。
当 `push_bacl` 一个数 $x$ 时，要将其异或 $t$。
用 01Trie 维护排好序的部分，查询前 $k$ 小时根据 $t'$ 将行走的方向取反。
我们要支持查询子树在异或 $t$ 后的和，于是要维护每一位的 $1$ 的个数。为了节省空间，只有一个儿子的点的信息可以引用儿子的信息。即压缩 Trie。
对于未排序的部分，用前缀和维护即可。
在全局排序时，只需将未排序的部分插入 Trie 中。
时间复杂度 $O(nw^2)$ ，空间复杂度 $O(nw)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 100500
using namespace std;
struct Buf{
int c[30],tot;
void clr()
{tot=0;for (int i=0;i<30;i++)c[i]=0;}
ll calc(int x){
ll ret=0;
for (int i=0;i<30;i++)
ret+=((ll)(x>>i&1 ? tot-c[i] : c[i]))<<i;
return ret;
}
}t[MaxN<<2];int tot;
Buf get(int x){
Buf C;C.tot=1;
for (int k=0;k<30;k++)
C.c[k]=x>>k&1;
return C;
}
Buf operator + (const Buf &A,const Buf &B){
Buf C;C.tot=A.tot+B.tot;
for (int i=0;i<30;i++)C.c[i]=A.c[i]+B.c[i];
return C;
}
struct Node{int l,r,p;}a[MaxN<<6];
int tn;
inline void up(int u){
if (a[u].l&&a[u].r){
if (a[u].p==a[a[u].l].p||a[u].p==a[a[u].r].p||!a[u].p)a[u].p=++tot;
t[a[u].p]=t[a[a[u].l].p]+t[a[a[u].r].p];
}else a[u].p=a[a[u].l|a[u].r].p;
}
void add(int &u,int k,int x)
{
if (!u)u=++tn;
if (k==-1){
if (!a[u].p)a[u].p=++tot;
t[a[u].p].tot++;
for (int i=0;i<30;i++)
t[a[u].p].c[i]+=x>>i&1;
return ;
}
if (x>>k&1)add(a[u].r,k-1,x);
else add(a[u].l,k-1,x);
up(u);
}
int wfk,tag,tag2;ll ret;
void qry(int u,int k,int x)
{
if (k==-1){ret+=1ll*(tag^x)*wfk;return ;}
if (tag2>>k&1){
int rc=t[a[a[u].r].p].tot;
if (wfk>rc){
wfk-=rc;
ret+=t[a[a[u].r].p].calc(tag);
qry(a[u].l,k-1,x);
}else qry(a[u].r,k-1,x|(1<<k));
}else {
int lc=t[a[a[u].l].p].tot;
if (wfk>lc){
wfk-=lc;
ret+=t[a[a[u].l].p].calc(tag);
qry(a[u].r,k-1,x|(1<<k));
}else qry(a[u].l,k-1,x);
}
}
Buf o[MaxN<<1];
int n,m,p1,p2,rt,x[MaxN<<1];
int main()
{
scanf("%d",&n);p2=n;
for (int i=1;i<=n;i++){
scanf("%d",&x[i]);
o[i]=o[i-1]+get(x[i]);
}
scanf("%d",&m);
for (int qt=1,op,l,r,val;qt<=m;qt++){
scanf("%d",&op);
if (op==1){
scanf("%d",&x[++p2]);
o[p2]=o[p2-1]+get(x[p2]^=tag);
}
if (op==2){
scanf("%d%d",&l,&r);
int tl=l,tr=min(r,p1);
ll ans=0;
if (tl<=tr){
wfk=tl-1;ret=0;qry(rt,29,0);ans-=ret;
wfk=tr;ret=0;qry(rt,29,0);ans+=ret;
}
tl=max(p1+1,l);tr=r;
if (tl<=tr){
ans-=o[tl-1].calc(tag);
ans+=o[tr].calc(tag);
}printf("%lld\n",ans);
}
if (op==3){scanf("%d",&val);tag^=val;}
if (op==4){
for (int i=p1+1;i<=p2;i++)add(rt,29,x[i]);
p1=p2;tag2=tag;
}
}return 0;
}
```