UVALive 2191电影收藏,伪-(动态)树状数组

Posted by Cww97 on 2016-03-07

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50820898
题目点这

题意:
有n个电影光盘堆成一个栈的样子,每次抽出其中一个,看完放在最上面,问每次抽出时这个光盘上面有多少光盘。

分析
看了份题解的中文部分,说的不是很清楚,但有个大概方向
然后一边洗澡一边思考,,,想通了

树状数组的范围是n,每抽一次电影光盘,n++,
原来的节点值是1,变成0。。第n+1个节点值变成1
也就是说,树状数组的有效范围是变化的
注意是有效范围,这个有效很重要
也就是说,后面的范围即使一开始用不到,也要初始化
初始化的时候,要初始化到maxn(20W左右)
PS:t数组记录每个光盘的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=233333,nn=200000;
int n,c[N],m,t[N];

void add(int k,int x){
while(k<=nn){
c[k]+=x;
k+=k&-k;
}
}

int sum(int k){
int s=0;
while (k){
s+=c[k];
k-=k&-k;
}
return s;
}

int main(){
//freopen("fuck.in","r",stdin);
int T;scanf("%d",&T);
while (T--){
scanf("%d%d",&n,&m);
memset(c,0,sizeof(c));
for (int i=1;i<nn;i++){
t[i]=n-i+1;
}
for (int i=1;i<=n;i++){
add(i,1);
}

while (m--){
int x;scanf("%d",&x);
printf("%d",sum(n)-sum(t[x]));
if (m)printf(" ");
add(t[x],-1);
t[x]=++n;
add(n,1);
}
puts("");
}
return 0;
}

很久没有一发过了(这两天数据结构题有毒)。。。
嘿嘿嘿,开心