UVA 1513 Movie collection （树状数组+反向存储）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：给你n盘歌碟按照（1....n）从上到下放，接着m个询问，每一次拿出x碟，输出x上方有多少碟并将此碟放到开头

直接想其实就是一线段的区间更新，单点求值，但是根据题意我们可以这样想

首先我们倒着存 n--1，接着每次询问时把放碟子放到最后，这样我们要开一个映射数组映射每个碟子在哪个位置

其中我们需要使用树状数组维护每个绝对位置是否有碟子（有些碟子已经放到了后面了），再使用区间求和就好了

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;//开成两倍，因为要向后添加

int mp[Max],bit[Max],tot,tol;//映射位置 被映射的树状数组 总大小

int lowbit(int x)

{

    return x&(-x);

}

void Add(int x,int y)

{

    while(x<=tol)

    {

        bit[x]+=y;

        x+=lowbit(x);

    }

    return ;

}

int Sum(int x)

{

    int sum=;

    while(x)

    {

        sum+=bit[x];

        x-=lowbit(x);

    }

    return sum;

}

void Init(int n,int m)

{

    memset(bit,,sizeof(bit));

    tot=n;

    tol=n+m;

    for(int i=; i<=n; ++i)//倒序存储

    {

        mp[i]=n-i+;

        Add(mp[i],);

    }

    return;

}

int Solve(int n,int m)

{

    ll ans=;

    int pos=mp[m];

    //printf("\npos=%d\n",pos);

    ans=n-Sum(pos);//求后面的

    tot++;

    Add(pos,-);//更新

    Add(tot,);

    mp[m]=tot;//映射到开头

    return ans;

}

int main()

{

    int t,n,m,num;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d %d",&n,&m);

        Init(n,m);

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

        {

            scanf("%d",&num);

            printf("%d%c",Solve(n,num),i==m-?'\n':' ');

        }

    }

    return ;

}