[Ynoi2011]竞赛实验班

本文主要是介绍[Ynoi2011]竞赛实验班，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

竞赛实验班

题解

虽然这是Ynoi，但这并不需要分块，所以出题人也并没卡分块。
然而笔者最开始打了个分块，过了，才发现根本不需要分块。

事实上如果没有最后的排序操作，大家应该很容易想到用差分去做。
我们可以记录下每一个位置之前的某一位为$0/1$的数的个数，顺便记录个懒标记。
假设我们插入数$x$前，执行操作$3$的数的异或和为$lzy$，那么我们就将$x\otimes lzy$插入数列。
查询时我们的异或和为$lz{y}^{\prime }$，我们查询时就查询所有数异或$lz{y}^{\prime }$后的和，这样就不用每次都对数列中的数进行修改了。
由于我们维护的是区间值，所以我们需要记录它们的前缀和差分得到区间答案。
我们查询时对所有数异或上$lz{y}^{\prime }$并不需要真的对每个数异或上$lz{y}^{\prime }$，只在$lz{y}^{\prime }$的某一位为$0$是差分那一位为$1$的数的个数，为$1$的时候差分那一位为$0$的数的个数。

但加上排序的操作后我们又该怎么办呢？
做过[Ynoi2018]天降之物的读者应该很容易想到将排序之后新加入，也就是未经理排序这一步的数单独维护，排序后再将它们插入到我们排序的数组中。
对于排序后的数组的维护我们可以考虑$trie$树，树上每个节点维护该节点的区间和。
我们异或一个数，如果数的某一位为一，相当于改变那一层的所有节点的左右儿子顺序。
我们查询区间和可以用查询区间第$k$大的方式来实现，只是我们的第$k$大不一定是真的第$k$大，我们应该考虑的是在异或之前的第$k$大。
由于它每次异或都是全局性的更改，所以我们对左右儿子枚举顺序的影响也是固定的，如果我们异或的某一位的和为$1$，那么这一位就应该先枚举$1$再枚举$0$，反之先枚举$0$再枚举$1$。
排序时我们只需要将所有对枚举顺序的更改全部去掉即可。
由于我们$trie$树的更改是需要懒标记的，所以我们只能记录下来每一个节点上某一位为$0/1$的数的数量，通过交换两个值来实现全局的修改。
同理查询时也需要将每一位都枚举一遍，这样$trie$树部分就需要${\log }^{2}n$了。

时间复杂度$O\left(n{\log }^{2}n\right)$。

源码

#include<bits/stdc++.h> 
using namespace std;
#define MAXN 200005
#define MAXM 6000005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int inv2=499122177;
const int jzm=2333;
const int zero=10000;
const int lim=200000;
const int n1=500;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
const int M=lim/n1+5;
int n,m,a[MAXN],ch[MAXM][2],siz[MAXM],summ[MAXM][31][2],tot;
int sum[MAXN][31][2],lzy,cnt,rev[MAXM],pow2[31],ord[31],sumt;
LL ans;
void pushdown(int rt,int dp){int lim=(1<<dp)-1;if(!(rev[rt]&lim))return ;if(ch[rt][0])rev[ch[rt][0]]^=rev[rt];if(ch[rt][1])rev[ch[rt][1]]^=rev[rt];if(rev[rt]&(1<<dp-1))swap(ch[rt][0],ch[rt][1]);for(int i=0;i<dp-1;i++)if((rev[rt]>>i)&1)swap(summ[ch[rt][0]][i][0],summ[ch[rt][0]][i][1]),swap(summ[ch[rt][1]][i][0],summ[ch[rt][1]][i][1]);rev[rt]=0;
}
LL query(int rt,int k,int dp){if(k==0||dp==0||!rt)return 0;LL res=0;pushdown(rt,dp);if(!ord[dp-1]){if(siz[ch[rt][0]]<=k){res+=query(ch[rt][1],k-siz[ch[rt][0]],dp-1);res+=1ll*(k-siz[ch[rt][0]])*pow2[dp-1];for(int i=0;i<dp-1;i++) res+=1ll*pow2[i]*summ[ch[rt][0]][i][1];}else res+=query(ch[rt][0],k,dp-1);}else{if(siz[ch[rt][1]]<=k){res+=query(ch[rt][0],k-siz[ch[rt][1]],dp-1);res+=1ll*siz[ch[rt][1]]*pow2[dp-1];for(int i=0;i<dp-1;i++)res+=1ll*pow2[i]*summ[ch[rt][1]][i][1];}else res+=query(ch[rt][1],k,dp-1)+1ll*k*pow2[dp-1];}return res;
}
void insert(int &rt,int dp,int aw){if(!rt)rt=++cnt;siz[rt]++;for(int j=0;j<30;j++)summ[rt][j][(aw>>j)&1]++;if(dp==0)return ;pushdown(rt,dp);insert(ch[rt][(aw>>dp-1)&1],dp-1,aw);
}
signed main(){read(n);int root=++cnt;pow2[0]=1;for(int i=1;i<30;i++)pow2[i]=pow2[i-1]+pow2[i-1];for(int i=1,x;i<=n;i++){read(x),a[++tot]=x;for(int j=0;j<30;j++)sum[tot][j][0]=sum[tot-1][j][0],sum[tot][j][1]=sum[tot-1][j][1],sum[tot][j][(x>>j)&1]++;}read(m);for(int i=1;i<=m;i++){int opt;read(opt);if(opt==1){int x;read(x);a[++tot]=x^lzy;for(int j=0;j<30;j++)sum[tot][j][0]=sum[tot-1][j][0],sum[tot][j][1]=sum[tot-1][j][1],sum[tot][j][(a[tot]>>j)&1]++;}if(opt==2){int l,r;read(l);read(r);ans=0;if(l<=sumt)ans+=query(root,min(r,sumt),30)-query(root,l-1,30);if(r>sumt){int al=max(1,l-sumt),ar=r-sumt;for(int j=0;j<30;j++){int t=((lzy>>j)&1)^1;ans+=1ll*pow2[j]*(sum[ar][j][t]-sum[al-1][j][t]);}}printf("%lld\n",ans);}if(opt==3){int x;read(x);lzy^=x;for(int j=0;j<30;j++)if((x>>j)&1)swap(summ[root][j][0],summ[root][j][1]),ord[j]^=1;rev[root]^=x;}if(opt==4){for(int j=0;j<30;j++)ord[j]=0;for(int j=1;j<=tot;j++)insert(root,30,a[j]^lzy),a[j]=0;sumt+=tot;tot=lzy=0;}}return 0;
}

谢谢！！！

这篇关于[Ynoi2011]竞赛实验班的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---