P3157题解

· · 题解

其实u1s1,这题我也没想到自己一遍就能过,其实想法很简单,就是我们做逆序对的时候用的是线段树去维护,这里也一样,这样的话就完全可以做到O(n \log^2 n)只是这里需要用一点小科技,就是pbds,然后这个代码就非常通俗易懂了.

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> Tree;
ll n, m, a[100005], c[100005], back[100005], sum=0;
Tree b[400005];
void build(ll p,ll l, ll r){
    if(l==r){b[p].insert(a[l]); return;}
    ll mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    ll l1=l, l2=mid+1;
    for(ll i=l; i<=r; i++){
        if(l1==mid+1){
            c[i]=a[l2];
            l2++;
        }
        else{
            if(l2==r+1){
                c[i]=a[l1];
                l1++;
            }
            else{
                if(a[l1]<=a[l2]){
                    c[i]=a[l1];
                    l1++;
                    sum+=r+1-l2;
                }
                else{
                    c[i]=a[l2];
                    l2++;
                }
            }
        }
    }
    for(ll i=l; i<=r; i++){a[i]=c[i];}
    for(auto y:b[2*p]) b[p].insert(y);
    for(auto y:b[2*p+1]) b[p].insert(y);
    return;
}
ll query(ll x, ll p, ll l, ll r, ll tar){
    ll ans;
    if(x==0){ans=b[p].order_of_key(tar);}
    if(x==1){ans=b[p].size()-b[p].order_of_key(tar);}
    return ans;
}
ll dell(ll p, ll l, ll r, ll q, ll tar){
    b[p].erase(tar);
    if(l==r){return 0;}
    ll mid=(l+r)/2;
    if(q<=mid) return query(0,2*p+1,mid+1,r,tar)+dell(2*p,l,mid,q,tar);
    else return query(1,2*p,l,mid,tar)+dell(2*p+1,mid+1,r,q,tar);
}
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>m;
    for(ll i=1; i<=n; i++){cin>>a[i]; back[a[i]]=i;}
    build(1,1,n);
    sum=n*(n-1)/2-sum;
    cout<<sum<<'\n';
    for(ll i=1, x; i<=m; i++){
        cin>>x;
        sum-=dell(1,1,n,back[x],x);
        if(i!=m)cout<<sum<<'\n';
    }
    return 0;
}

最后小小插播一句,这道题的正解是CDQ分治,但是我觉得我的想法其实本质上和它差不多,只是写起来好写多了