AC题目简解-数据结构 - Findxiaoxun - 博客园

AC题目简解-数据结构 - Findxiaoxun - 博客园

要两条路有交叉，(x1,y1)(x2,y2)那么需要满足：(x1-x2)*(y1-y2)<0判断出这是求逆序的问题 
树状数组求逆序，先通过自定义的比较器实现按照一种元素排序，然后再逐次查询和add来获取结果 


B - Ping pong POJ 3928 
分析裁判的位置，则可判断求逆序问题。对每个点的裁判，他能举办的比赛场数为左弱*右强+左强*右弱，通过正序和倒序两次插入和查询累加得最终结果 


C - Balanced Lineup POJ 3274 
用线段树A的== 


D - Mobile phones POJ 1195 
二维树状数组，理解了一维的，二维的也很好理解。一维是前面线上的和，二维的是前面矩形的和。算目标范围也很明确，就是减掉两个矩形的加上多减的一个正方形，维护跟一维的也基本一样 


E - MooFest POJ 1990 
首先，最重要的是理解好题意：1.两头牛只要通讯一次就行。每次的耗费是distance*max(v[i],v[j])2.按power还是按position排序。我选的是power，因为position没有重复值。排序这个想法跟Japan那道题是一样的。 
说下思路： 
按照power的升序排好后，依次加入树状数组,每加一次，就查一次，累计一次ans。这个是标准的数组数组的解法。 
但是，树状数组的索引值是牛的坐标的索引值，这就意味着，能力比当前低的牛可能会排到其后面，而且，它们的距离值是需要的。 
这就要求，既能记录到前面有多少头牛，又能记录他们的距离和，后面有多少头牛，和他们的距离和。 
而想到，加点的时候，有一个i来控制，也就是说，在i前面   有    a头牛的话，后面有i-a头，顺着这个想法，那也可以统计坐标和啊。前面加了i头牛，总共的坐标和distance可以累加出来，而在i的坐标前面有（这里的有和加是两回事）的牛的坐标和为sum(data[i].position-1).dist，那么坐标在第i个的后面，而且power比第i个的小的坐标和就是distance-sum(data[i].position-1).dist 
因为是按照power排的序，所以在i前面加的power都比第i个小，也就是说，如果之前加的和第i个通讯的话，取的power指肯定是第i个的 
公式: 
这里的sum(data[i].position).num表示坐标在data[i].position前面的牛的个数 
sum(data[i].position-1).dist    i的坐标前面有（这里的有和加是两回事）的牛的坐标和 


ans+=(sum(data[i]-1).num*data[i].position - sum(data[i].position-1).dist + (distance-sum(data[i].position-1).dist - (i-1-sum(data[i]-1).num)*data[i].position ))*data[i].power 
可以化简为 
int x1=sum(data[i]-1).num,x2=sum(data[i].position-1).dist; 
ans+=(data[i].position*(x1*2-i+1) - x2*2 + distance)*data[i].power; 

然后distance累加再把当前点add进树状数组就ok了

Read full article from AC题目简解-数据结构 - Findxiaoxun - 博客园