题目
题面
Cards Sorting
Vasily has a deck of cards consisting of n cards.There is an integer on each of the cards, this integer is between 1 and 100 000, inclusive .It is possible that some cards have the same integers on them.
Vasily decided to sort the cards .To do this, he repeatedly takes the top card from the deck, and if the number on it equals the minimum number written on the cards in the deck, then he places the card away.Otherwise, he puts it under the deckand takes the next card from the top, and so on.The process ends as soon as there are no cards in the deck.You can assume that Vasily always knows the minimum number written on some card in the remaining deck, but doesn’t know where this card (or these cards) is.
You are to determine the total number of times Vasily takes the top card from the deck.
Input
The first line contains single integer n (1 ≤ n ≤ 100 000) — the number of cards in the deck.
The second line contains a sequence of n integers a1, a2, …, an (1 ≤ ai ≤ 100 000), where ai is the number written on the i - th from top card in the deck.
Output
Print the total number of times Vasily takes the top card from the deck.
Examples
Input
4
6 3 1 2
Output
7
Input
1
1000
Output
1
Input
7
3 3 3 3 3 3 3
Output
7
大意
瓦西里有一副由n张牌组成的牌组。每张牌上都有一个整数，介于1到100 000之间（包括1和100000），有些牌上可能有相同的整数。
瓦西里决定对卡片进行排序，为此他反复从卡组中取出最上面的卡，如果卡上的数字等于卡组中卡片上所写的最小值，则他将卡取走。否则 他会将此卡放到卡组底部，然后从顶部取出下一张卡，依此类推。一旦卡座中没有卡，该过程就会结束。您可以假设Vasily始终知道剩余卡座中某张卡上写入的最小值，但是 不知道这张卡（或这些卡）在哪里。
您将确定Vasily从卡片组拿走顶卡的总次数。
思路
开始看错题目了，还天真的以为没有重复的数。这个题的主要还是要用树状数组计算前缀和，
因为每次都是吧最小值去掉，所以对于输入的数据进行排序就可以了。
代码
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
vector<int> ve[100010];/*建立一个vector数组，记录每一个数在数组中的位置*/
int c[100010], n, a[100010], pr[100010];
/*用树状数组计算前缀和（一个位置前有多少个数*/
int lowbit(int x)
{
return x & (-x);
}
void add(int x,int y)
{
for (int i = x; i <= n; i += lowbit(i))
c[i] += y;
}
int find(int x)
{
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i))
ans += c[i];
return ans;
}
int main()
{
//freopen("F:/y.txt", "r", stdin);
while (~scanf("%d", &n))
{
memset(c, 0, sizeof(c));
memset(pr, 0, sizeof(pr));
int t = 0;
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
if (pr[x] == 0)
{
pr[x] = 1;
a[t++] = x;
}
ve[x].push_back(i);
add(i, 1);
}
/*因为存入vector时是安i的顺序存的，所以在vector[]内部的元素是有序的*/
sort(a, a + t);/*查看每次操作后的最小值*/
long long ans = 0, p = 0;
for (int i = 0; i < t; i++)//每次要保证最小的卡片全部被取走
{
int s = ve[a[i]].size();
if (p < ve[a[i]][0])/*记录p之前的数*/
{
vector<int>::iterator it = ve[a[i]].begin();
int x = ve[a[i]][s - 1];
ans += find(x) - find(p);
p = x;
for (it; it != ve[a[i]].end(); it++)
{
add(*it, -1);/* *it前面的数的数量减一*/
}
}
else/*记录p之后的数*/
{
int temp = 0;
vector<int>::iterator it = ve[a[i]].begin();
int x = 0;
for (it; it != ve[a[i]].end(); it++)
{
if (*it < p)
{
x = *it;
}
else
{
break;
}
}
ans += find(n) - find(p) + find(x);
p = x;
it = ve[a[i]].begin();
for (it; it != ve[a[i]].end(); it++)
{
add(*it, -1);/**it前面的数的数量减一*/
}
}
}
printf("%lld\n", ans);
}
return 0;
}
