输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
3
3 2 19这是WUSTOJ上挂的2014年蓝桥杯本科B组预选赛的一题， 看着就是求逆序对，一开始没啥思路，后来想通了每个小朋友最后累加的愤怒值就是看他之前有多少个比他大的数加上之后有多少和比他小的数就做出来了，设该值为x的话，那么该小朋友累加的愤怒值就是x*（x+1）/2;因为1+2+3...+x嘛，因为这里是要求单点的逆序对数，归并排序不知道怎么求单点的，正好之前用树状数组和线段树写过求逆序对数的题，就用上了，然后这题因为数据1e7，开线段树不离散化的话会炸内存，但是树状数组就不会了，而且还省去了离散化，这题总体思路就是正着求一遍逆序对，反着求一遍逆序对
ps：
如果还不会树状数组，可以看之前的博客，比较基础的例题和讲解：点击打开链接
再上一题基础例题讲解：点击打开链接
然后学会树状数组后树状数组和线段树求逆序对思路都是一样的：
按照输入的数列一个个插入到树中，设插入的数为x，该数是插入的第i个数的话（从0开始），插入前求一下树上小于等于x的已经插入数的个数，求得就是单点的逆序对数为：i减去该数（原理就是插入数-正序对数等于逆序对数）
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<deque>
using namespace std;
int sum1[1000005];//用于正着求一遍逆序对的树状数组
int sum2[1000005];//反着求的树状数组
int p[1000005];//存数据
int b[1000005];//存第一遍的每个点的逆序对数
int lowbit(int x)
{return x&(-x);
}
void update(int x,int a[])//线段树的单点更新
{while(x<=1000001)//为什么填1000001和下面的操作有关{a[x]++;x+=lowbit(x);}
}
int query(int x,int a[])//询问
{int s=0;while(x>0)//因为这里如果x等于零的时候lowbit也为0，会无限循环，所以下面处理数据的时候全部加1，所以界限为1000001{s+=a[x];x-=lowbit(x);}return s;
}
int main()
{int i,j,k,n,t;long long s;while(scanf("%d",&n)!=EOF){s=0;memset(sum1,0,sizeof(sum1));memset(sum2,0,sizeof(sum2));for(i=0;i<n;i++){scanf("%d",&p[i]);p[i]+=1;//这里全部加上1防无限循环b[i]=i-query(p[i],sum1);//插入数-正序对数为逆序对数update(p[i],sum1);//更新}for(i=n-1;i>=0;i--)//反着再求一遍{t=query(1000001-p[i],sum2);s=s+((b[i]+t)*(1+b[i]+t)/2);//上面有推的公式update(p[i],sum2);}printf("%lld\n",s);}return 0;
}