题意：有一堆电影，按1-n顺序排，有m次操作，每次询问第ai个电影之前有多少个电影，然后将其抽出放在堆顶。
分析：线段树应用。
因为每次查询后要将电影移至堆顶，所以我们可以将线段树的区间开到maxn+n，[1,maxn]先置0，在[maxn+1,maxn+n]建树将值置为1，线段树每一段区间的值代表该区间的和。
每次查询后要将该位置的值更新为0，由于要将电影移至堆顶，用一个指针cnt初始化为maxn，记录当前电影可以移到的位置，
由于位置是变化的，所以要用一个数组indice[]来记录每个电影当前所在的位置，每次移动位置只要indice[x]=cnt--即可。
查询的时候只要查询[1,indice[x]-1]区间和就行了。
AC代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 #define lson l,m,rt<<1 6 #define rson m+1,r,rt<<1|1 7 const int maxn=100000+5; 8 int add[maxn<<3]; 9 int tree[maxn<<3]; 10 int indice[maxn]; 11 int n,num; 12 void pushup(int rt) 13 { 14 tree[rt]=tree[rt<<1]+tree[rt<<1|1]; 15 } 16 void update(int p,int x,int l,int r,int rt) 17 { 18 if(l==r) 19 { 20 tree[rt]=x; 21 return ; 22 } 23 int m=(l+r)>>1; 24 if(p<=m) 25 update(p,x,lson); 26 else 27 update(p,x,rson); 28 pushup(rt); 29 } 30 int query(int L,int R,int l,int r,int rt) 31 { 32 if(L<=l&&r<=R) 33 return tree[rt]; 34 int m=(l+r)>>1; 35 int ret=0; 36 if(L<=m) 37 ret+=query(L,R,lson); 38 if(R>m) 39 ret+=query(L,R,rson); 40 return ret; 41 } 42 void build(int l,int r,int rt) 43 { 44 if(l==r) 45 { 46 num++; 47 if(num>maxn) 48 tree[rt]=1; 49 return ; 50 } 51 int m=(l+r)>>1; 52 build(lson); 53 build(rson); 54 pushup(rt); 55 } 56 int main() 57 { 58 int t,m,i,x,index; 59 scanf("%d",&t); 60 while(t--) 61 { 62 memset(tree,0,sizeof(tree)); 63 scanf("%d%d",&n,&m); 64 num=0; 65 build(1,maxn+n,1); 66 for(int i=1;i<=n;i++) 67 indice[i]=maxn+i; 68 int cnt=maxn; 69 for(i=0;i<m;i++) 70 { 71 scanf("%d",&x); 72 printf("%d",query(1,indice[x]-1,1,maxn+n,1)); 73 if(i!=m-1) printf(" "); 74 update(indice[x],0,1,maxn+n,1); 75 indice[x]=cnt--; 76 update(indice[x],1,1,maxn+n,1); 77 } 78 printf(" "); 79 } 80 return 0; 81 }