【jzoj5222】【GDOI2018模擬7.12】【A】【資料結構】

【jzoj5222】【GDOI2018模擬7.12】【A】【資料結構】

題目大意

這裡寫圖片描述

解題思路

題目有問題,一個人可以控制iq相同的。使用資料結構計算出一個數和後面數構成的逆序對數,計算出每個點被操作的最早時間,從高到低加入,計算出每個點貢獻變成0的時間,統計答案即可。

code

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned int
#define fo(i,j,k) for(int i=j;i<=k;i  )
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int max(int x,int y){return (x>y)?x:y;}
int min(int x,int y){return (x<y)?x:y;}
int const mn=1e5 9,inf=1e9 7;
int n,m,a[mn],b[mn],c[mn],f[mn],t[mn],mi[mn],x[mn];
LL g[mn];
bool cmp(int x,int y){
    return (a[x]<a[y])||((a[x]==a[y])&&(x<y));
}
bool cm2(int x,int y){
    return (a[x]>a[y])||((a[x]==a[y])&&(c[x]<c[y]));
}
int qury(int x){
    int y=0;
    while(x){
        y =t[x];
        x-=x&(-x);
    }
    return y;
}
void oper(int x){
    while(x<=n){
        t[x]  ;
        x =x&(-x);
    }
}
int qur2(int x){
    int y=inf;
    while(x){
        y=min(y,mi[x]);
        x-=x&(-x);
    }
    return y;
}
void ope2(int x,int y){
    while(x<=n){
        mi[x]=min(mi[x],y);
        x =x&(-x);
    }
}
int main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,1,n)scanf("%d",&a[i]);
    fo(i,1,n)b[i]=i;
    sort(b 1,b n 1,cmp);
    fo(i,1,n){
        f[b[i]]=i-qury(b[i])-1;
        oper(b[i]);
    }
    fo(i,1,n)c[i]=mi[i]=m 1;
    fo(i,1,m)scanf("%d",&x[i]),c[x[i]]=min(c[x[i]],i);
    sort(b 1,b n 1,cm2);
    fo(i,1,n){
        ope2(b[i],c[b[i]]);
        int tmp=qur2(b[i])-1;
        g[tmp] =f[b[i]];
    }
    fd(i,m,0)g[i] =g[i 1];
    fo(i,0,m)printf("%lld\n",g[i]);
    return 0;
}