(UVA) 11368 - Nested Dolls

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2353&mosmsg=Submission+received+with+ID+17773282

題意：給你m(1<=m<=20000)個物品，每個物品有a值和b值。若一個東西裡面可以裝另外一個東西的條件為：a1>a2 且 b1>b2。問說通通推疊完後，最少有多少堆。

一開始，我還不知道這題要怎麼做。

於是乎，我就想說，先把數值按照a從小到大排序，如果a值相同，再用b值由大到小排序。

那接下來，我們維護一棵數值線段樹，裡面記錄這個b值出現過幾次，並且順便維護區間max跟size。之後對於一個新進的b，因為我們已經按照a排序了，b也按照大小排序了，所以b可以很安心的接在恰好比b小的數字中最大的後面。如果沒有一個這樣的值，就另開一個新的點。

最後輸出size值即可

時間複雜度：O(n lg n)

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

typedef pair<int,int> pii;
const int MAX_N = 1e5+6;

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

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);
 return node;
}

void modify(Node* node,int L,int R,int pos,int val) {
 if (L==R) {
  node->val += val;
  if (node->val ==0) node->mx=0;
  else if (node->val >=1) node->mx=pos;
  return;
 }
 int mid=(L+R)>>1;
 if (pos<=mid) modify(node->lc,L,mid,pos,val);
 else modify(node->rc,mid+1,R,pos,val);
 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->mx;
 int mid=(L+R)>>1;
 return max(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}

pii v[MAX_N];

int main () {
 int T;
 scanf("%d",&T);
 while (T--) {
  int n;
  scanf("%d",&n);
  for (int x=0;n>x;x++) {
   int i,j;
   scanf("%d %d",&i,&j);
   v[x] = make_pair(i,-j);
  }
  sort(v,v+n);
  Node* root=Build(1,MAX_N);
  for (int x=0;n>x;x++) {
   int t=query(root,1,MAX_N,1,-v[x].second-1);
   if (t==0) modify(root,1,MAX_N,-v[x].second,1);
   else {
    modify(root,1,MAX_N,t,-1);
    modify(root,1,MAX_N,-v[x].second,1);
   }
  }
  printf("%d\n",root->val);
 }
}