前言
今天是集训最后一天。。。
题目：
排列游戏
我们发现，想要字典序最小，肯定第一个填 $1$ 是最优的，这样以来后面每个位置的奇偶性都确定了，我们直接按照从小到大放就行。
但是有一个特例，就是当 $n \mod 4=3$ 的时候，第一个放 $1$ 没有合法解，只能放 $2$。
代码：
C++
#include<bits/stdc++.h>
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<=n;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*4<=n;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<bits/stdc++.h>
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-(1<<k)+1]);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>c>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
pre[1]=a[1];
for(int i=2;i<=n;i++) pre[i]=min(pre[i-1],a[i]);
for(int i=0;i<=n+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;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++) st[0][i]=a[i];
for(int k=1;k<=lg[n];k++) for(int i=1;i+(1<<k)-1<=n;i++)
st[k][i]=max(st[k-1][i],st[k-1][i+(1<<(k-1))]);
int ans=0;
for(int i=1;i<=n-2;i++){
int L=pre[i],l=i+1,r=n-1,fl=-1,fr=-1;
while(l<=r){
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(l<=r){
int mid=(l+r)>>1;
int F=qmax(i+1,mid)-mex[mid];
if(F<=L) fr=mid,l=mid+1;
else r=mid-1;
}
if(fr==-1) continue;
ans+=fr-fl+1;
}
cout<<ans<<"\n";
}
return 0;
}暂存
对于一个二元组 $(i,j) \ (j>i)$，考虑计算如果想要 $a_i$ 换到 $a_j$ 后面又多少种可能性。
首先，对于 $i=1$，我们只需暂存 $a_i$，并保证 $a_{i+1}$ 到 $a_j$ 都不被暂存即可，可能性为 $2^{n-1-(j-i)}$。
对于 $i>1$，我们不仅需要满足以上条件，还要保证 $a_{i-1}$ 不会被暂存，可能性就是 $2^{n-2-(j-i)}$。
所以对于 $a_i,a_j$，如果 $a_i<a_j$，贡献就是交换的可能性；如果 $a_i>a_j$，贡献就是总可能性减去交换的可能性。
对于 $i=1$ 我们可以直接记录答案；对于 $i>1$，我们会发现，固定 $j$ 时乘法分配律一下就变成单点修改区间查询问题了，用一个树状数组维护即可。
代码：
C++
#include<bits/stdc++.h>
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(;x<=n;x+=x&-x) (tr[x]+=k)%=mod;
}
int get(int x){
if(x<=0) return 0;
int res=0;
for(;x>0;x-=x&-x) (res+=tr[x])%=mod;
return res;
}
void clear(){
for(int i=1;i<=n;i++) tr[i]=0;
}
}bit,num;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>c>>T;
p2[0]=1,inv[0]=1;
int inv2=fpow(2,mod-2);
for(int i=1;i<N;i++){
p2[i]=(p2[i-1]*2)%mod;
inv[i]=(inv[i-1]*inv2)%mod;
}
while(T--){
int ans=0;
cin>>n;
num.clear(),bit.clear();
for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
sort(b+1,b+1+n);
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
if(n==1){
cout<<"0\n";
continue;
}
for(int i=2;i<=n;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;i<=n;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);
}
cout<<ans<<"\n";
}
return 0;
}
Comments NOTHING