Fork me on GitHub

[LA-5902] Movie Collection Fenwick树

发表于 | 分类于
字数统计: 413字 | 阅读时长 ≈ 2分钟

题面

传送门:LA-5902

题目大意:有个物品从上到下放置,并且标号,有次查询,每次查询标号为的物品现在的位置（,即该物品上面有多少个物品）,同时将该物品取出放到第号位置。

样例

1
2
3
4
5
6
7
8
9
Sample Input
2
3 3
3 1 1
5 3
4 4 5
Sample Output
2 1 0
3 0 4

思路

还是不难想到的,将1~n件物品重新编号,1~n标为n~1,每次拿出一件物品x,再将其重新编号,如果是第一次拿出就标为n+1…..依次递增,然后将之前的编号删掉,插入新的编号即可，用一个树状数组维护

代码

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
49
50
51
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2*1e5+10;
#define lowbit(x) (x&-x)
int T,n,m;
int pos[maxn],c[maxn];
inline void read(int &x)
{
	x=0;char ch=getchar();int f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
int sum(int x)
{
	int ret = 0;
	while(x){ret+=c[x];x-=lowbit(x);}
	return ret;
}
void add(int x,int d)
{
	while(x<=maxn)
	{
		c[x]+=d;
		x+=lowbit(x);
	}
}
int main(int argc, char *argv[])
{
	read(T);
	while(T--)
	{
		read(n),read(m);
		for (int i = 1; i <= n; i++)
		pos[i] = n + 1 - i;
		for (int i = 1; i < maxn; i++)
		c[i] = lowbit(i);
		int t = n;
		for (int i = 0; i < m; i++)
		{
			int id;
			read(id);
			if (i != 0) printf(" ");
			printf("%d",n-sum(pos[id]));
			add(pos[id],-1);
			pos[id] = ++t;
		}
		printf("\n");
	}
	return 0;
}

一看Rank榜是第一.

窃喜

Markdown