a457: TOI2010 第五題：餐廳評鑑

http://zerojudge.tw/ShowProblem?problemid=a457

先按照第一個值(s)排序之後，尋找第二個值(r)的逆序數對個數(在不同第一個值之間)。

#include <iostream>
#include <stdio.h>
#include <utility>
#include <algorithm>
using namespace std;

const int MAX_N = 2e5 + 6;
typedef pair<int,int> pii;
vector<int> num;

struct Node {
 Node* lc;
 Node* rc;
 int val;
 Node() {
  lc=rc=NULL;
  val=0;
 }
 void pull() {
  val=lc->val + rc->val;
 }
};

Node* Build(int L,int R) {
 Node* node = new Node();
 if (L==R) {
  return node;
 }
 int mid=(L+R)>>1;
 node->lc=Build(L,mid);
 node->rc=Build(mid+1,R);
 node->pull();
 return node;
}

void modify(Node* node,int L,int R,int pos) {
 if (L==R) {
  node->val += 1;
  return;
 }
 int mid=(L+R)>>1;
 if (pos<=mid) modify(node->lc,L,mid,pos);
 else modify(node->rc,mid+1,R,pos);
 node->pull();
 return;
}

int query(Node* node,int L,int R,int l,int r) {
 if (L>r || l>R) return 0;
 else if (l<=L && R<=r) return node->val;
 int mid=(L+R)>>1;
 return query(node->lc,L,mid,l,r) + query(node->rc,mid+1,R,l,r);
}

pii s[MAX_N];

int main () {
 int k,m;
 while (scanf("%d %d",&k,&m) != EOF) {
  for (int x=0;k>x;x++) {
   int i;
   scanf("%d",&i);
   s[x].first=i;
  }
  for (int x=0;k>x;x++) {
   int i;
   scanf("%d",&i);
   s[x].second=i;
  }
  sort(s,s+k);
  for (int x=0;k>x;x++) {
   num.push_back(s[x].second);
  }
  sort(num.begin(),num.end());
  num.resize(unique(num.begin(),num.end()) - num.begin());
  for (int x=0;k>x;x++) {
   s[x].second = lower_bound(num.begin(),num.end(),s[x].second) - num.begin() + 1;
  }
  long long ans=0;
  int n=num.size();
  Node* root = Build(1,n);
  for (int x=0;k>x;x++) {
   vector<int> tmp;
   tmp.push_back(s[x].second);
   int val=s[x].first;
   while (k>x && s[x+1].first == val) {
    x++;
    tmp.push_back(s[x].second);
   }
   for (auto iter=tmp.begin();iter!=tmp.end();iter++) {
    int t=*iter;
    ans+=query(root,1,n,t+1,n);
   }
   for (auto iter=tmp.begin();iter!=tmp.end();iter++) {
    int t=*iter;
    modify(root,1,n,t);
   }
  }
  printf("%lld\n",ans);
 }
}