链接:http://codeforces.com/problemset/problem/830/B

题意:给一个长度为n的数列(有重复数字),要重复进行下面的操作:如果第一个数是当前数列中最小的数那么就删除它,否则把它放到队尾 ,求这个数列能操作多少次

思路: 离散化后,把每个数字出现的位置i存进vector里后从小到大枚举 (因为一定优先删除小的数字)
假设上一个数字最后出现的位置是i,
如果当前数字第一次出现的位置j大于 i 那么删除当前位置所需要的代价就是 i+1~j 中的数字的个数
如果j<i,那么就把i之后的所有数字都删除(而i之前的数字留着下一回删)

查询数字的个数用树状数组维护一下就好
代码::

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
typedef long long LL;

struct node
{
    int num,id;
}a[100100];
int b[100100],n;
int sum(int x)
{
    int ans=0;
    while(x){ans=ans+b[x];x-=x&(-x);}
    return ans;
}
void upd(int x,int c)
{
    for(;x<=n;x+=x&(-x)) b[x]+=c;
}
vector<int>v[100010];
bool cmp(node x,node y)
{
    if(x.num==y.num) return x.id<y.id;
    return x.num<y.num;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].num);
        a[i].id=i;
        upd(i,1);
    }
    sort(a+1,a+1+n,cmp);
    int sz=1;
    v[sz].pb(a[1].id);
    for(int i=2;i<=n;i++){
        if(a[i].num!=a[i-1].num) sz++;
        v[sz].pb(a[i].id);
    }
    LL ans=0,LastMin=0;

    for(int i=1;i<=sz;i++){
        int pos=lower_bound(v[i].begin(),v[i].end(),LastMin)-v[i].begin();

        if(pos==0){
            pos=v[i][v[i].size()-1];
            ans=ans+sum(pos)-sum(LastMin);
            LastMin=pos;
            for(int j=v[i].size()-1;j>=0;j--) upd(v[i][j],-1),v[i].pop_back();
        }
        else {
            // pos=v[i][v[i].size()-1];
            ans=ans+sum(n)-sum(LastMin);
            LastMin=0;
            for(int j=v[i].size()-1;j>=pos;j--) upd(v[i][j],-1),v[i].pop_back();
                i--;
        }
    }
    printf("%lld\n",ans);
    return 0;
}