ZR 集训 Day30模拟赛

前言 今天是集训最后一天。。。 题目： 排列游戏 我们发现，想要字典序最小，肯定第一个填 $1$ 是最优的，这样以来后面每个位置的奇偶性都确定了，我们直接按照从小到大放就行。 但是有一个特例，就是当 $n \mod 4=3$ 的时候，第一个放 $1$ 没有合法解，只能放 $2$。 代码： C++#include using namespace std; int c,T,n; signed main(){ scanf("%d%d",&c,&T); while(T--){ scanf("%d",&n); if(n%4==3){ for(int i=1;i*4#include using namespace std; int c,T,n; signed main(){ scanf("%d%d",&c,&T); while(T--){ scanf("%d",&n); if(n%4==3){ for(int i=1;i*4n;i++) printf("%d %d %d %d ",4*i-2,4*i-3,4*i-1,4*i); printf("%d %d %d\n",n-(n%4)+2,n-(n%4)+1,n-(n%4)+3); } else{ for(int i=1;i*4n;i++) printf("%d %d %d %d ",4*i-3,4*i-2,4*i,4*i-1); if(n%4==1) printf("%d\n",n-(n%4)+1); else if(n%4==2) printf("%d %d\n",n-(n%4)+1,n-(n%4)+2); else printf("\n"); } } return 0; } 时间线 当我们固定 $r1$ 时，需要寻找一个 $r2$ 使得： $$\min_{i=1}^{r1} a_i = \max_{i=r2+1}^n a_i - \text{mex}_{i=r1+1}^{r2} a_i$$ 易证 $\max_{i=r2+1}^n a_i - \text{mex}_{i=r1+1}^{r2} a_i$ 具有单调性，所以二分找到满足条件的 $r2$ 的区间即可。 代码： C++#include using namespace std; #define int long long const int N=1e6+5; int c,T,n; int a[N],cnt[N],pre[N],mex[N],lg[N],st[20][N]; int qmax(int l,int r){ int k=lg[r-l+1]; return max(st[k][l],st[k][r-(1cT; while(T--){ cinn; for(int i=1;ia[i]; pre[1]=a[1]; for(int i=2;i=1;i--){ if(a[i]=1) mex[i-1]=now; } for(int i=2;i1]+1; for(int i=1;i1; int F=qmax(i+1,mid)-mex[mid]; if(F=L) fl=mid,r=mid-1; else l=mid+1; } if(fl==-1) continue; if(qmax(i+1,fl)-mex[fl]!=L) continue; l=i+1,r=n-1; while(l1; int F=qmax(i+1,mid)-mex[mid]; if(F#include using namespace std; #define int long long const int N=1e6+5; int c,T,n; int a[N],cnt[N],pre[N],mex[N],lg[N],st[20][N]; int qmax(int l,int r){ int k=lg[r-l+1]; return max(st[k][l],st[k][r-(1k)+1]); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cincT; while(T--){ cinn; for(int i=1;in;i++) cina[i]; pre[1]=a[1]; for(int i=2;in;i++) pre[i]=min(pre[i-1],a[i]); for(int i=0;in+2;i++) cnt[i]=0; int now=0; for(int i=n;i=1;i--){ if(a[i]n) cnt[a[i]]++; while(cnt[now]) now++; if(i-1=1) mex[i-1]=now; } for(int i=2;in;i++) lg[i]=lg[i1]+1; for(int i=1;in;i++) st[0][i]=a[i]; for(int k=1;klg[n];k++) for(int i=1;i+(1k)-1n;i++) st[k][i]=max(st[k-1][i],st[k-1][i+(1(k-1))]); int ans=0; for(int i=1;in-2;i++){ int L=pre[i],l=i+1,r=n-1,fl=-1,fr=-1; while(lr){ int mid=(l+r)1; int F=qmax(i+1,mid)-mex[mid]; if(F=L) fl=mid,r=mid-1; else l=mid+1; } if(fl==-1) continue; if(qmax(i+1,fl)-mex[fl]!=L) continue; l=i+1,r=n-1; while(lr){ int mid=(l+r)1; int F=qmax(i+1,mid)-mex[mid]; if(FL) fr=mid,l=mid+1; else r=mid-1; } if(fr==-1) continue; ans+=fr-fl+1; } coutans"\n"; } return 0; } 暂存 对于一个二元组 $(i,j) \ (ji)$，考虑计算如果想要 $a_i$ 换到 $a_j$ 后面又多少种可能性。 首先，对于 $i=1$，我们只需暂存 $a_i$，并保证 $a_{i+1}$ 到 $a_j$ 都不被暂存即可，可能性为 $2^{n-1-(j-i)}$。 对于 $i1$，我们不仅需要满足以上条件，还要保证 $a_{i-1}$ 不会被暂存，可能性就是 $2^{n-2-(j-i)}$。 所以对于 $a_i,a_j$，如果 $a_ia_j$，贡献就是总可能性减去交换的可能性。 对于 $i=1$ 我们可以直接记录答案；对于 $i1$，我们会发现，固定 $j$ 时乘法分配律一下就变成单点修改区间查询问题了，用一个树状数组维护即可。 代码： C++#include using namespace std; #define int long long const int N=2e5+5; const int mod=998244353; int c,T,n; int a[N],b[N],p2[N],inv[N]; inline int fpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y=1; } return res; } inline int qpow(int x,int y){ if(x==2){ if(y=0) return p2[y]; return inv[-y]; } if(y=0) return fpow(x,y); return fpow(fpow(x,-y),mod-2); } struct BIT{ int tr[N]; void add(int x,int k){ for(;x0;x-=x&-x) (res+=tr[x])%=mod; return res; } void clear(){ for(int i=1;icT; p2[0]=1,inv[0]=1; int inv2=fpow(2,mod-2); for(int i=1;in; num.clear(),bit.clear(); for(int i=1;ia[i],b[i]=a[i]; sort(b+1,b+1+n); for(int i=1;ia[i]) ans=((ans+qpow(2,n-1)-swp)%mod+mod)%mod; } bit.add(a[2],qpow(2,2)); num.add(a[2],1); for(int i=3;i#include using namespace std; #define int long long const int N=2e5+5; const int mod=998244353; int c,T,n; int a[N],b[N],p2[N],inv[N]; inline int fpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y=1; } return res; } inline int qpow(int x,int y){ if(x==2){ if(y=0) return p2[y]; return inv[-y]; } if(y=0) return fpow(x,y); return fpow(fpow(x,-y),mod-2); } struct BIT{ int tr[N]; void add(int x,int k){ for(;xn;x+=x&-x) (tr[x]+=k)%=mod; } int get(int x){ if(x0) return 0; int res=0; for(;x0;x-=x&-x) (res+=tr[x])%=mod; return res; } void clear(){ for(int i=1;in;i++) tr[i]=0; } }bit,num; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cincT; p2[0]=1,inv[0]=1; int inv2=fpow(2,mod-2); for(int i=1;iN;i++){ p2[i]=(p2[i-1]*2)%mod; inv[i]=(inv[i-1]*inv2)%mod; } while(T--){ int ans=0; cinn; num.clear(),bit.clear(); for(int i=1;in;i++) cina[i],b[i]=a[i]; sort(b+1,b+1+n); for(int i=1;in;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b; if(n==1){ cout"0\n"; continue; } for(int i=2;in;i++){ int swp=qpow(2,n-i); if(a[1]a[i]) (ans+=swp)%=mod; if(a[1]a[i]) ans=((ans+qpow(2,n-1)-swp)%mod+mod)%mod; } bit.add(a[2],qpow(2,2)); num.add(a[2],1); for(int i=3;in;i++){ int sum=bit.get(n)-bit.get(a[i]),ni=num.get(n)-num.get(a[i]); ans=((ans-((qpow(2,n-2-i)*sum)%mod))%mod+mod)%mod; ans=(ans+((qpow(2,n-1)*ni)%mod))%mod; sum=bit.get(a[i]-1); ans=(ans+((qpow(2,n-2-i)*sum)%mod))%mod; bit.add(a[i],qpow(2,i)); num.add(a[i],1); } coutans"\n"; } return 0; }