Uva(1513)(Movie collection)

链接：https://vjudge.net/problem/UVA-1513
思路：有几天没写了，今天来一个树状数组的。求一个盘子上面的盘子数目。首先我们要明白树状数组求的东西都要跟前缀有关，而盘子上面的数目正好就是前缀，恰好满足我们的条件，但是我们随即发现，抽出来之后还要将盘子放上面，我们是无法在树状数组的前端插入一个新值的，也不可能让整个数组移动，怎么办呢？我们想到只能在后端插值，那么此时前缀和的意义就变为了他下面盘子的数目，其实只需要用n减一下就可以转化为上面盘子的个数，将拿出位置的值设为0即可。需要把数组开大一点。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6;
int c[maxn];
int arr[maxn];
int n,t,m;

int lowbit(int x){
    return x&(-x);
}

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

int sum(int x){
    int res = 0;
    while(x){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

int main(){
    scanf("%d",&t);
    while(t--){
        memset(c,0,sizeof(c));  
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            arr[i] = n-i+1;
            add(i,1);
        }
            for(int j=1;j<=m;j++){
                int now;
                scanf("%d",&now);
                printf("%d%c",n-sum(arr[now]),j==m?'\n':' ');
                add(arr[now],-1);
                arr[now] = j+n;
                add(j+n,1);
            }
    }
    return 0;
}