1513 - Movie collection
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4259
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3913
Mr. K. I. has a very big movie collection. He has organized his collection in a big stack. Whenever he wants to watch one of the movies, he locates the movie in this stack and removes it carefully, ensuring that the stack doesn't fall over. After he finishes watching the movie, he places it at the top of the stack.
Since the stack of movies is so big, he needs to keep track of the position of each movie. It is sufficient to know for each movie how many movies are placed above it, since, with this information, its position in the stack can be calculated. Each movie is identified by a number printed on the movie box.
Your task is to implement a program which will keep track of the position of each movie. In particular, each time Mr. K. I. removes a movie box from the stack, your program should print the number of movies that were placed above it before it was removed.
Input
On the first line a positive integer: the number of test cases, at most 100. After that per test case:
- one line with two integers n and m (1 n, m
UVa 1513 / UVALive 5902 Movie collection (樹狀數組) 100000): the number of movies in the stack and the number of locate requests.UVa 1513 / UVALive 5902 Movie collection (樹狀數組) - one line with m integers a1,..., am (1 ai
UVa 1513 / UVALive 5902 Movie collection (樹狀數組) n) representing the identification numbers of movies that Mr. K. I. wants to watch.UVa 1513 / UVALive 5902 Movie collection (樹狀數組)
For simplicity, assume the initial stack contains the movies with identification numbers 1, 2,..., n in increasing order, where the movie box with label 1 is the top-most box.
Output
Per test case:
- one line with m integers, where the i-th integer gives the number of movie boxes above the box with label ai, immediately before this box is removed from the stack.
Note that after each locate request ai, the movie box with label ai is placed at the top of the stack.
Sample Input
2
3 3
3 1 1
5 3
4 4 5
Sample Output
2 1 0
3 0 4
思路:使用樹狀數組+位置數組可破。
完整代碼:
/*UVa: 0.175s*/
/*UVALive: 0.139s*/
#include<cstdio>
#include<cstring>
const int maxn=200010;
int c[maxn], p[100010], toppos;///使用數組p來儲存位置
inline void update(int pos, int num) //1或-1(對0的加1,對1的減1)
{
while (pos <= maxn)//全局更新!
{
c[pos] += num;
pos += -pos & pos;
}
}
inline int sum(int pos)
{
int count = 0;
while (pos)
{
count += c[pos];
pos -= -pos & pos;
}
return count;
}
int main(void)
{
int t, n, m, a;
scanf("%d", &t);
while (t--)
{
memset(c, 0, sizeof(c));
memset(p, 0, sizeof(p));
scanf("%d%d", &n, &m);
toppos = n;
for (int i = 1; i <= n; ++i)
{
p[i] = n - i + 1;
update(i, 1);
}
//
bool first = true;
while (m--)
{
scanf("%d", &a);
if (first)
{
printf("%d", n - sum(p[a]));
first = false;
}
else
printf(" %d", n - sum(p[a]));
update(p[a], -1);
p[a] = ++toppos;
update(toppos, 1);
}
puts("");
}
return 0;
}