hdu1394线段树点修改，区间求和

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394

题意：给一个0-n-1的排列，这个排列中的逆序数为数对 (ai, aj) 满足 i < j and ai > aj的个数。依次把第一个数放到排列的末尾会得到另外n-1个排列，求这n个排列中的最小的逆序数。

思路：关键是要把第一个排列的逆序数求出来，后面的排列可以递推出来。假如第一个逆序数为s0,当把a0从首位移到末位时，新得到的s1应该是在s0的基础上加上比a0大的数的个数，减去比a0小的数的个数。由于这一串数是一个0-n-1的排列，所以比a0大的数的个数为 (n-1)-(a0+1)+1=n-a0-1，比a0小的数的个数为 (a0-1)-0+1=a0，所以s1=n-a0-a0-1.第一次做个题的时候一直想不明白要怎么建树，由于是满足 i < j and ai > aj的条件，所以其实就是对于每个数aj，求比它大的数的个数。建树的时候把每个节点都初始化为0，每当插入一个数，就在这个数对应的叶子节点上加1，同时更新包含这个点的线段所对应的非叶子节点（加1），一层层更新上去，区间求和。这样如果存在某个数，在相应查找的时候就会找到。由于是要找比aj大的数，所以查找范围就是aj-(n-1).如果还是想不明白的话，对着代码手动模拟一遍就清楚了。

这里有个线段树的讲解，虽然不是这道题，但是觉得对理解线段树挺有帮助的。http://hi.baidu.com/semluhiigubbqvq/item/be736a33a8864789f4e4ad18

#include <cstdio> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 5005; int sum[maxn<<2]; int a[maxn]; void PushUP(int rt)//更新每个节点的值，区间求和 {sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt) {sum[rt]=0;if(l==r) return;int m=(l+r)>>1;build(lson);build(rson); } int query(int L,int R,int l,int r,int rt) {if(L<=l && r<=R)return sum[rt];int m=(l+r)>>1;int s=0;if(L<=m) s+=query(L,R,lson);if(R>m) s+=query(L,R,rson);return s; } void update(int p,int l,int r,int rt) {if(l==r){sum[rt]++;return;}int m=(l+r)>>1;if(p<=m) update(p,lson);else update(p,rson);PushUP(rt);//每次更新了叶子节点后，内部节点也要更新 } int main() {int n;while(~scanf("%d",&n)){build(0,n-1,1);int sum=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);sum+=query(a[i],n-1,0,n-1,1);update(a[i],0,n-1,1);}int minm=sum;for(int i=0;i<n;i++){sum+=n-a[i]-a[i]-1;minm=min(minm,sum);}printf("%d\n",minm);}return 0; } View Code

 

 

 

转载于:https://www.cnblogs.com/54zyq/p/3268976.html

总结

以上是生活随笔为你收集整理的hdu1394线段树点修改，区间求和的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。