链接: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;
}