codeforces 830B 树状数组

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read(){int ret=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';return ret;}
vector<int> q[100005];
int sum[100005];
#define lowbit(x) x&(-x)
void add(int x,int p){while(x<=100000){sum[x]+=p;x+=lowbit(x);}}
int get(int x){int ans=0;while(x){ans+=sum[x];x-=lowbit(x);}return ans;}
int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
        q[read()].push_back(i),add(i,1);
    int cur=1;
    ll ans=1;
    for(int i=1;i<=100000;i++)
    {
        int pos=upper_bound(q[i].begin(),q[i].end(),cur-1)-q[i].begin();
        for(int j=pos;j<q[i].size();j++)
        {
           ans+=get(q[i][j])-get(cur);
           cur=q[i][j];
           add(cur,-1);
        }
        for(int j=0;j<pos;j++)
        {
            if(q[i][j]<cur)ans+=get(q[i][j])+(get(100000)-get(cur));
            else ans+=get(q[i][j])-get(cur);
            cur=q[i][j];
            add(cur,-1);
        }
    }
    cout<<ans<<endl;
}