HDU

题目链接

题意：

在路旁长了一些树，但是看起来不是很和谐，不和谐的因素有 $FAR$ 和 $SHORT$，不和谐的值 $disharmony= F * S$;

$FAR$ 定义为 $F =$ 两棵树之间 $x$ 坐标大小排名之差的绝对值

$SHORT$ 定义为 $S =$ 两个树之间高度最低的排名

求所有树的不和谐值的总和。

思路：

和$MooFest$的思路很类似，因为要求坐标大小排名之差的绝对值，所以我们要同时记录个数和值；

先将所有的树按照高度由高到低排序，那么我们每一次所用的S，就是当前树高度的排名；

  1 /*
  2 * @Author: windystreet
  3 * @Date:   2018-08-09 10:44:50
  4 * @Last Modified by:   windystreet
  5 * @Last Modified time: 2018-08-09 15:56:07
  6 */
  7 #include<bits/stdc++.h>
  8 
  9 using namespace std;
 10 
 11 #define X first
 12 #define Y second
 13 #define eps  1e-5
 14 #define gcd __gcd
 15 #define pb push_back
 16 #define PI acos(-1.0)
 17 #define lowbit(x) (x)&(-x)
 18 #define bug printf("!!!!!
");
 19 #define mem(x,y) memset(x,y,sizeof(x))
 20 
 21 typedef long long LL;
 22 typedef long double LD;
 23 typedef pair<int,int> pii;
 24 typedef unsigned long long uLL;
 25 
 26 const int maxn = 1e5+20;
 27 const int INF  = 1<<30;
 28 const int mod  = 1e9+7;
 29 
 30 struct node
 31 {
 32     int  x,h;
 33 }s[maxn];
 34 
 35 int xx[maxn],hh[maxn];
 36 
 37 LL tree[maxn][2]; // 0 num
 38 int n;            // 1 xsum
 39 bool cmp(node a, node b){
 40     return a.h>b.h||(a.h==b.h&&a.x>b.x);
 41 }
 42 
 43 void init(){
 44     for(int i=0;i<=n+10;i++){
 45         for(int j=0;j<2;j++){
 46             tree[i][j] = 0;
 47         }
 48     }
 49 }
 50 
 51 void add(int x,int v,int flag){
 52     for(int i=x;i<=n;i+=lowbit(i)){
 53         tree[i][flag] += v;
 54     }return;
 55 }
 56 
 57 LL query(int x,int flag){
 58     LL res = 0;
 59     for(int i=x;i;i-=lowbit(i)){
 60         res += tree[i][flag];
 61     }
 62     return res; 
 63 }
 64 
 65 void solve(){
 66     while(scanf("%d",&n)!=EOF){
 67         init();
 68         for(int i=1;i<=n;i++){
 69             scanf("%d%d",&s[i].x,&s[i].h);
 70             xx[i] = s[i].x; hh[i] = s[i].h;
 71         }
 72         sort(xx+1,xx+1+n);sort(hh+1,hh+1+n);sort(s+1,s+1+n,cmp);
 73         LL P,S,ans = 0;
 74         for(int i=1;i<=n;i++){
 75             int pos = lower_bound(xx+1,xx+1+n,s[i].x)-xx;        // 获取当前树的坐标排名
 76             int hi  = lower_bound(hh+1,hh+1+n,s[i].h)-hh;        // 获取当前树的高度排名
 77             P = pos*query(pos,0) - query(pos,1) + query(n,1)-query(pos,1)-(query(n,0)-query(pos,0))*pos;
 78             // 以上是计算之前已经存在的树与当前树的排名差的绝对值，分别是计算当前树位置之间的 和 之后的
 79             S = hi;                                                
 80             ans += P*S;                                          // 更新答案
 81             add(pos,1,0);add(pos,pos,1);                        
 82         }
 83         printf("%lld
", ans);
 84     }
 85     
 86     return;
 87 }
 88 
 89 int main()
 90 {
 91 //    freopen("in.txt","r",stdin);
 92 //    freopen("out.txt","w",stdout);
 93 //    ios::sync_with_stdio(false);
 94     int t = 1;
 95     //scanf("%d",&t);
 96     while(t--){
 97     //    printf("Case %d: ",cas++);
 98         solve();
 99     }
100     return 0;
101 }