Description

对家庭菜园有兴趣的JOI君每年在自家的田地中种植一种叫做IOI草的植物。JOI君的田地沿东西方向被划分为N个区域，由西到东标号为1~N。IOI草一共有N株，每个区域种植着一株。在第i个区域种植的IOI草，在春天的时候高度会生长至hi，此后便不再生长。

为了观察春天的样子而出行的JOI君注意到了IOI草的配置与预定的不太一样。IOI草是一种非常依靠阳光的植物，如果某个区域的IOI草的东侧和西侧都有比它高的IOI草存在，那么这株IOI草就会在夏天之前枯萎。换句话说，为了不让任何一株IOI草枯萎，需要满足以下条件：

对于任意2<=i<=N-1，以下两个条件至少满足一个：

1. 对于任意1<=j<=i-1，hj<=hi

2. 对于任意i+1<=j<=N，hk<=hi

IOI草是非常昂贵的，为了不让IOI草枯萎，JOI君需要调换IOI草的顺序。IOI草非常非常的高大且纤细的植物，因此JOI君每次只能交换相邻两株IOI草。也就是说，JOI君每次需要选择一个整数i(1<=i<=N-1)，然后交换第i株IOI草和第i+1株IOI草。随着夏天临近，IOI草枯萎的可能性越来越大，因此JOI君想知道让所有IOI草都不会枯萎的最少操作次数。

现在给出田地的区域数，以及每株IOI草的高度，请你求出让所有IOI草的不会枯萎的最少操作次数。

Input

第一行一个正整数N，代表田地被分为了N个区域。

接下来N行，第i行(1<=i<=N)一个整数hi，表示第i株植物在春天时的高度

Output

输出一行一个整数，表示最少需要的操作次数

 

Solution

贪心+树状数组

采用重新编号。

对于原来的数组，重新编号为1 2 3 4 5 6

假如交换之后，这些编号交换成了1 3 4 2 6 5

变成这个最终序列操作次数就是最终序列逆序对对数。

对于这个样例就是3

（证明：考虑反过来，一个序列变成升序的，就是逆序对数量，所以，从升序变成这个序列，也是逆序对对数）

现在就要考虑怎么构造。

使得最终的序列合法，并且逆序对数最少。

 

类似于各种排序问题

 

按h 从大到小sort

之前放好的h们成了一个块。

后面的h小的，为了保证合法，只能往之前的块的左边或者右边放。

贪心放置，每次选择已经块的左边或者右边，使得新的逆序对最小。

（证明：放完之后，和之前块形成一个新的块。块内的放置方法不会对后面的逆序对产生带来影响。

所以自然已经放置的块里逆序对最少是成立的。）

至于这个决策，用两个树状数组处理，一个查询比i小的，一个查询比i大的。

 

 

相同的权值，先一起查询，然后一起放置。因为相同权值之间不会因为下标逆序对产生代价。

 

代码：

#include
      
       using namespace std;typedef long long ll;const int N=3e5+5;ll ans;int n;int st[N];struct tr{    int f[N];    void add(int x,int c){        for(;x<=n;x+=x&(-x)) f[x]+=c;    }    int query(int x){        int ret=0;        for(;x;x-=x&(-x)) ret+=f[x];        return ret;    }}Max,Min;struct node{    int h,id;    bool friend operator<(node a,node b){        return a.h>b.h;    }}a[N];int sta[N],top;int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&st[i]);        a[i].id=i,a[i].h=st[i];    }    sort(a+1,a+n+1);    //cout<<" bug "<
      

 总结：

突破口：重新编号，转化为最终序列的编号序列的逆序对数。还有对h排序，为了不造成影响，并且放置方便（只能往左右放）。

然后就是贪心关键点：先放置大的形成了一块，块内的放置方法不会对后面的逆序对产生带来影响。

可以注意到，对于排序的问题，通常可以把编号什么的条件排个序决策，

好处是，我们可以自然而然地获得了一些性质，而避免了状压。