牛客小白月赛115 G

离散化+离线处理+线段树维护最小值+树状数组+二分查找

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
#define int long long
const int N=2e5+5;
struct node{
    int data,cnt;
    node(){
        data=0,cnt=0;
    }
    node(int x,int y){
        data=x,cnt=y;
    }
    bool operator<(const node &x) const{
        if(data==x.data) return cnt<x.cnt;
        return data<x.data;
    }
};
node b[N];
int a[N];
int tree[N<<2];
int tag[N<<2];
int n,m;
int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }

void push_up(int p) {
    tree[p] = min(tree[ls(p)], tree[rs(p)]); 
}

void addtag(int p, int pl, int pr, int d) {
    tag[p] += d;
    tree[p] += d; 
}

void push_down(int p, int pl, int pr) {
    if (tag[p]) {
        int mid = (pl + pr) >> 1;
        addtag(ls(p), pl, mid, tag[p]);
        addtag(rs(p), mid + 1, pr, tag[p]);
        tag[p] = 0;
    }
}

void build(int p, int pl, int pr) {
    if (pl == pr) {
        tree[p] = a[pl];
        return;
    }
    int mid = (pl + pr) >> 1;
    build(ls(p), pl, mid);
    build(rs(p), mid + 1, pr);
    push_up(p);
}

void update(int L, int R, int p, int pl, int pr, int d) {
    if (L <= pl && pr <= R) {
        addtag(p, pl, pr, d);
        return;
    }
    push_down(p, pl, pr);
    int mid = (pl + pr) >> 1;
    if (L <= mid) update(L, R, ls(p), pl, mid, d);
    if (R > mid) update(L, R, rs(p), mid + 1, pr, d);
    push_up(p);
}

int query(int L, int R, int p, int pl, int pr) {
    if (L <= pl && pr <= R) {
        return tree[p];
    }
    push_down(p, pl, pr);
    int mid = (pl + pr) >> 1;
    int res = 1e9;
    if (L <= mid) res = min(res, query(L, R, ls(p), pl, mid));
    if (R > mid) res = min(res, query(L, R, rs(p), mid + 1, pr));
    return res;
}
#define lowbit(x) ((x)&-(x))
int t[N];
void add(int x,int d){
    while(x<=n){
        t[x]+=d;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0;
    while(x){
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
signed main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>b[i].data;
        b[i].cnt=i;
    }
    vector<int> v(n+1);
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++){
        v[b[i].cnt]=v[b[i-1].cnt];
        if(b[i].data!=b[i-1].data) v[b[i].cnt]++;
    }
    // for(int i=1;i<=n;i++){
    //     cout<<v[i]<<" ";
    // }
    // cout<<endl;
    for(int i=n;i>=1;i--){
        a[i]=sum(n)-sum(v[i]);
        add(v[i],1);
    }
    // for(int i=1;i<=n;i++){
    //     cout<<a[i]<<" ";
    // }
    build(1, 1, n);
    int q;
    cin>>q;
    vector<pii> ask(q+1);
    for(int i=1;i<=q;i++){
        cin>>ask[i].first;
        ask[i].second=i;
    }
    for(int i=1;i<=n;i++){
        v[i]=b[i].data;
    }
    sort(ask.begin()+1,ask.end());
    vector<int> ans(q+1);
    int pre=n;
    for(int i=q;i>=1;i--){
        auto [x,p]=ask[i];
        int pos=lower_bound(v.begin()+1,v.end(),x+1)-v.begin();
        // cout<<x<<" "<<pos<<endl;
        // cout<<pos<<pre<<endl;
        for(int j=pos;j<=pre;j++){
            // cout<<query(1,n,1,1,n)<<endl;
            // cout<<query(4,4,1,1,n)<<endl;
            // cout<<b[j].cnt<<endl;
            update(b[j].cnt+1,n,1,1,n,1);
            // cout<<query(1,n,1,1,n)<<endl;
            // cout<<query(4,4,1,1,n)<<endl;
        }
        // cout<<query(1,n,1,1,n)<<endl;
        ans[p]=query(1,n,1,1,n);
        pre=pos-1;
    }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}