[AT_abc431_g] [ABC431G] One Time Swap 2 题解
aeiouaoeiu
·
·
题解
先考虑套路地按位确定，对于一个 l，操作 (l,r) 有三种可能：使字典序减小、不变或增大，不妨将这三种情况对应的 r 集合设为 C_l,E_l,D_l，则 C_l=\{r\mid a_l>a_r,r>l\},E_l=\{r\mid a_l=a_r,r>l\},D_l=\{r\mid a_l<a_r,r>l\}。
根据字典序比较的顺序，字典序从小到大分别来自 C_1,C_2,C_3,\ldots,C_n，接下来是整个 E，再接下来是 D_n,D_{n-1}\ldots,D_1。于是可以分为三段处理。接下来考虑 C 段如何处理。
显然 |C_l| 就是 l 贡献的顺序对数量，可以树状数组预处理，对于一个 k，其对应的 l 应该满足 \sum_{i=1}^{l-1}|C_i|<k\le \sum_{i=1}^l|C_i|，让 l 从小到大扫一遍即可确定。
接下来考虑如何求出 r，对于操作 (l,r_1),(l,r_2)，先比较 a_{r_1} 与 a_{r_2} 的大小，哪个小，哪个操作得到的序列字典序就会小。如果相等，则比较 r_1 与 r_2 的大小关系，哪个小，哪个操作换过来的 a_l 就会靠前，由于 a_l>a_r，得到的序列字典序就会大。于是将 r 以 a_r 为第一关键字，-r 为第二关键字升序排序，第 k-\sum_{i=1}^{l-1}|C_i| 小的就是所要求的 r。
具体实现时，可以使用线段树二分，先把所有 (a_i,-i) 排序求出排名，扫到一个 l 就把 l 删掉，由于 a_r>a_l 的 r 一定比 a_r<a_l 的 r 靠后，所以不用删，直接查找第 k-\sum_{i=1}^{l-1}|C_i| 个 1 在哪里即可。
$D$ 段与 $C$ 段大致相同，注意查找时应该加上所有 $a_r\le a_l,r>l$ 的 $r$ 的数量，因为这些值一定比我们要找的 $r$ 靠前。
将查询的 $k$ 离线下来从小到大找即可。时间复杂度 $\mathcal{O}(q\log q+(n+q)\log n)$。
:::info[code]
```cpp
#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
const ll maxn=200007,ee=1e18;
ll n,m,a[maxn],c[maxn],d[maxn],e,f[maxn],buc[maxn],hd,cur;
ll lst[maxn],rev[maxn],id[maxn];
pair<ll,ll> Q[maxn],cc[maxn],ans[maxn],tar;
struct BIT{
ll val[maxn];
void add(ll x,ll k){for(;x<=n;x+=x&(-x)) val[x]+=k;}
ll qry(ll x){ll E=0; for(;x;x-=x&(-x)) E+=val[x]; return E;}
}BIT;
struct Tree{
ll val[maxn<<2];
void build(ll l,ll r,ll k,ll rt){
val[rt]=k*(r-l+1);
if(l==r) return;
ll mid=(l+r)>>1;
build(l,mid,k,rt<<1),build(mid+1,r,k,rt<<1|1);
}
void modify(ll l,ll r,ll x,ll z,ll rt){
val[rt]+=z;
if(l==r) return;
ll mid=(l+r)>>1;
if(x<=mid) modify(l,mid,x,z,rt<<1);
else modify(mid+1,r,x,z,rt<<1|1);
}
ll qry(ll l,ll r,ll k,ll rt){
if(l==r) return l;
ll mid=(l+r)>>1;
if(val[rt<<1]>=k) return qry(l,mid,k,rt<<1);
else return qry(mid+1,r,k-val[rt<<1],rt<<1|1);
}
}tree;
int main(void){
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(ll i=1;i<=n;i++) cin>>a[i];
for(ll i=1,x;i<=m;i++) cin>>x,Q[i]=mp(x,i);
sort(Q+1,Q+1+m),hd=1;
for(ll i=n;i>=1;i--){
c[i]=BIT.qry(a[i]-1),e+=buc[a[i]];
d[i]=n-i-c[i]-buc[a[i]],f[i]=c[i]+buc[a[i]];
BIT.add(a[i],1),buc[a[i]]++;
}
for(ll i=1;i<=n;i++) cc[i]=mp(a[i],-i),id[i]=i;
sort(id+1,id+1+n,[&](ll x,ll y){return cc[x]<cc[y];});
for(ll i=1;i<=n;i++) rev[id[i]]=i;
tree.build(1,n,1,1);
for(ll l=1;l<=n;l++){
tree.modify(1,n,rev[l],-1,1);
for(;hd<=m;hd++){
if(cur+c[l]<Q[hd].first) break;
ans[Q[hd].second]=mp(l,id[tree.qry(1,n,Q[hd].first-cur,1)]);
}
cur+=c[l];
}
for(ll i=1;i<=n;i++){
if(lst[a[i]]){tar=mp(lst[a[i]],i); break;}
lst[a[i]]=i;
}
for(;hd<=m;hd++){
if(cur+e<Q[hd].first) break;
ans[Q[hd].second]=tar;
}
cur+=e;
for(ll i=1;i<=n;i++) cc[i]=mp(a[i],i),id[i]=i;
sort(id+1,id+1+n,[&](ll x,ll y){return cc[x]<cc[y];});
for(ll i=1;i<=n;i++) rev[id[i]]=i;
tree.build(1,n,0,1);
for(ll l=n;l>=1;l--){
for(;hd<=m;hd++){
if(cur+d[l]<Q[hd].first) break;
ans[Q[hd].second]=mp(l,id[tree.qry(1,n,Q[hd].first-cur+f[l],1)]);
}
tree.modify(1,n,rev[l],1,1);
cur+=d[l];
}
for(ll i=1;i<=m;i++) cout<<ans[i].first<<" "<<ans[i].second<<"\n";
return 0;
}
```
:::