UVALive - 5902 Movie collection

题意：1～n按从上到下排列，m次询问，每次问x之前的有多少个数字，并且将x放到队首

思路：树状数组，首先将1~n下标向后移m位，每次询问后都将一个数字移到队首，每次

都更新了节点的大小，并且问到了前缀和，所以用树状数组

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 201010;

int pos[MAXN],c[MAXN];
int n,m;

void Update(int x,int d){
    while (x <= n+m+1)
        c[x] += d,x += x&-x;
}

int sum(int x){
    int ret = 0;
    while (x > 0)
        ret += c[x],x -= x&-x;
    return ret;
}

int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%d%d",&n,&m);
        memset(pos,0,sizeof(pos));
        memset(c,0,sizeof(c));
        for (int i = 1; i <= n; i++){
            pos[i] = i+m;
            Update(pos[i],1);
        }
        for (int i = 1; i <= m; i++){
            int x;
            scanf("%d",&x);
            int ans = sum(pos[x]-1);
            Update(pos[x],-1);
            Update(m-i+1,1);
            pos[x] = m-i+1;
            if (i != m)
                printf("%d ",ans);
            else printf("%d\n",ans);
        }
    }
    return 0;
}

UVALive - 5902 Movie collection

原文：http://blog.csdn.net/u011345136/article/details/19767869