7.20T1

排序（sort）

【问题描述】

有 n 个人依次站在小 A 面前。小 A 会依次对这 n 个人进行 m 次操作。

每次操作选择一个位置 k，将这 n 个人中的所有身高小于等于当前 k 位置的

人的身高的人从队伍里拎出，然后按照升高从矮到高的顺序从左到右依次插入到

这些人原本的位置当中。

小 A 对这 n 个人身高构成的序列的逆序对很感兴趣。现在小 A 想要知道每一

次操作后这个序列的逆序对数。

【输入格式】

第一行 2 个整数 n 和 m，表示人数和操作数。

接下来一行 n 个整数 ai，表示初始状态从左到右每个人的身高。

接下来 m 行每行 1 个数，表示这次操作的 k。

【输出格式】

输出共 m+1 行，第 1 行表示未操作时的逆序对数量。

除第一行外第 i 行表示第 i-1 次操作后序列的逆序对数。

【样例输入】

6 2

160 163 164 161 167 160

【样例输出】

【样例解释】

第一次拎出 160、163、161、160

操作完后序列为 160 160 164 161 167 163

第二次拎出 160、160、164、161、163

操作完后的序列为 160 160 160 161 167 163

【数据范围】

对于 30%的数据，n,m≤500

对于 60%的数据，n,m≤1000

对于 100%的数据,n,m≤300000，1≤k≤n，,1≤ai≤10^9

sol：花式送分，大概就是当前大小之前的都不用管了，因为不影响答案了

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef long long ll;

inline ll read()

{

    ll s=; bool f=; char ch=' ';

    while(!isdigit(ch)) {f|=(ch=='-'); ch=getchar();}

    while(isdigit(ch)) {s=(s<<)+(s<<)+(ch^); ch=getchar();}

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<) {putchar('-'); x=-x;}

    if(x<) {putchar(x+''); return;}

    write(x/); putchar((x%)+'');

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const ll N=;

ll n,m;

struct Node

{

    ll id,num,val;

}a[N];

inline bool cmpnum(Node a,Node b){return a.num<b.num;}

inline bool cmpid(Node a,Node b){return a.id<b.id;}

struct BIT

{

    ll S[N<<];

    #define lowbit(x) ((x)&(-x))

    inline void Ins(int x,int v)

    {

        while(x<=n)

        {

            S[x]+=v; x+=lowbit(x);

        }

    }

    inline int Que(int x)

    {

        ll ans=;

        while(x>)

        {

            ans+=S[x]; x-=lowbit(x);

        }

        return ans;

    }

}T,BT;

signed main()

{

    freopen("sort.in","r",stdin);

    freopen("sort.out","w",stdout);

    ll i,cv=,ans=,now=,oo;

    R(n); R(m);

    for(i=;i<=n;i++) R(a[a[i].id=i].num);

    sort(a+,a+n+,cmpnum);

    a[].val=++cv;

    for(i=;i<=n;i++)

    {

        if(a[i].num==a[i-].num) a[i].val=cv; else a[i].val=++cv;

    }

    sort(a+,a+n+,cmpid);

    for(i=n;i>=;i--)

    {

        ans+=(oo=T.Que(a[i].val-));

        BT.Ins(a[i].val,oo);

        T.Ins(a[i].val,);

    }

    Wl(ans);

    for(i=;i<=m;i++)

    {

        ll pos; R(pos);

        if(now<a[pos].val)

        {

            ans-=(BT.Que(a[pos].val)-BT.Que(now)); now=a[pos].val;

        }

        Wl(ans);

    }

    return ;

}

/*

input

6 2

160 163 164 161 167 160

2

3

output

6

3

1

*/

巴特西

7.20T1

最新文章

热门文章