专栏文章

[AT_abc431_g] [ABC431G] One Time Swap 2 题解

aaeiouaoeiu
AT_abc431_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzrw3w
此快照首次捕获于
2025/12/01 18:13
3 个月前
此快照最后确认于
2025/12/01 18:13
3 个月前
查看原文
先考虑套路地按位确定，对于一个 ll，操作 (l,r)(l,r) 有三种可能：使字典序减小、不变或增大，不妨将这三种情况对应的 rr 集合设为 Cl,El,DlC_l,E_l,D_l，则 Cl={r∣al>ar,r>l},El={r∣al=ar,r>l},Dl={r∣al<ar,r>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\}。
根据字典序比较的顺序，字典序从小到大分别来自 C1,C2,C3,…,CnC_1,C_2,C_3,\ldots,C_n，接下来是整个 EE，再接下来是 Dn,Dn−1…,D1D_n,D_{n-1}\ldots,D_1。于是可以分为三段处理。接下来考虑 CC 段如何处理。
显然 ∣Cl∣|C_l| 就是 ll 贡献的顺序对数量，可以树状数组预处理，对于一个 kk，其对应的 ll 应该满足 ∑i=1l−1∣Ci∣<k≤∑i=1l∣Ci∣\sum_{i=1}^{l-1}|C_i|<k\le \sum_{i=1}^l|C_i|，让 ll 从小到大扫一遍即可确定。
接下来考虑如何求出 rr，对于操作 (l,r1),(l,r2)(l,r_1),(l,r_2)，先比较 ar1a_{r_1} 与 ar2a_{r_2} 的大小，哪个小，哪个操作得到的序列字典序就会小。如果相等，则比较 r1r_1 与 r2r_2 的大小关系，哪个小，哪个操作换过来的 ala_l 就会靠前，由于 al>ara_l>a_r，得到的序列字典序就会大。于是将 rr 以 ara_r 为第一关键字，−r-r 为第二关键字升序排序，第 k−∑i=1l−1∣Ci∣k-\sum_{i=1}^{l-1}|C_i| 小的就是所要求的 rr。
具体实现时，可以使用线段树二分，先把所有 (ai,−i)(a_i,-i) 排序求出排名，扫到一个 ll 就把 ll 删掉，由于 ar>ala_r>a_l 的 rr 一定比 ar<ala_r<a_l 的 rr 靠后，所以不用删，直接查找第 k−∑i=1l−1∣Ci∣k-\sum_{i=1}^{l-1}|C_i| 个 11 在哪里即可。
EE 段是简单的，从找到任意一对 al=ara_l=a_r 的即可。
DD 段与 CC 段大致相同，注意查找时应该加上所有 ar≤al,r>la_r\le a_l,r>l 的 rr 的数量，因为这些值一定比我们要找的 rr 靠前。
将查询的 kk 离线下来从小到大找即可。时间复杂度 O(qlog⁡q+(n+q)log⁡n)\mathcal{O}(q\log q+(n+q)\log n)。
codeCPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...