CF1834F 题解

dAniel_lele · 2023-12-30 10:03:56 · 题解

先考虑单词询问怎么做。对于每一个 p_i<i，我们需要一次操作将他移到前面，设共有 k 个，则我们至少要 k 次操作。同时，我们观察到对于任意一个置换环，均可以将其分为若干段，使得最后一段 i\to j 满足 j<i，于是对着置换环构造即可说明存在一种方案只用 k 次回去的操作。于是答案就是 p_i<i 的位置个数。

观察到本质不同的询问只有 O(n) 种（左右移动可以对 n 取模），我们考虑预处理出来。容易发现，i 位置产生贡献的一定是一个对 n 取模的区间。把所有区间算出来，差分即可。总复杂度 O(n+q)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[500005],b[500005],prea[500005],preb[500005];
signed main(){
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
    reverse(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        if(a[i]<i){
            prea[0]++,prea[i-a[i]]--;
            prea[i]++;
        }
        else{
            prea[i]++,prea[i+n-a[i]]--;
        }
        if(b[i]<i){
            preb[0]++,preb[i-b[i]]--;
            preb[i]++;
        }
        else{
            preb[i]++,preb[i+n-b[i]]--;
        }
    }
    for(int i=1;i<=n;i++) prea[i]+=prea[i-1],preb[i]+=preb[i-1];
//  for(int i=0;i<n;i++) cout<<prea[i]<<" "; cout<<"\n";
//  for(int i=0;i<n;i++) cout<<preb[i]<<" "; cout<<"\n";
    cout<<prea[0]<<"\n";
    int q; cin>>q;
    int sta=0,posa=0,posb=0;
    while(q--){
        int opt; cin>>opt;
        if(opt==1){
            int num;
            cin>>num;
            if(sta==0){
                (posa+=num)%=n;
                (posb+=n-num%n)%=n;
            }
            else{
                (posa+=n-num%n)%=n;
                (posb+=num)%=n;
            }
        }
        if(opt==2){
            int num;
            cin>>num;
            if(sta==0){
                (posa+=n-num%n)%=n;
                (posb+=num)%=n;
            }
            else{
                (posa+=num)%=n;
                (posb+=n-num%n)%=n;
            }
        }
        if(opt==3){
            sta^=1;
        }
        if(sta==0) cout<<prea[posa];
        else cout<<preb[posb];
        cout<<"\n";
    }
    return 0;
}