(Zj) a300: NOIP2011 Day1.2.选择客栈

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

我的想法是說：

先觀察有一個很神奇的單調性：假設固定一個開始的客棧a , 如果a ~ b的選擇是okay的，那a~c (c>b) 也一定是okay的！！！(可以仔細想想為甚麼！)

藉由這個神奇的性質，我們可以開一棵線段樹維護最小值，然後binary search，就好了。

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

#define int long long

const int MAX_N = 2e5 + 6;
const int INF = 1e15+7;

vector<int> kind[MAX_N];

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

int v[MAX_N];
int kd[MAX_N]; //kind

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

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

main () {
 int n,k,p;
 while (scanf("%lld %lld %lld",&n,&k,&p) != EOF) {
  for (int x=1;n>=x;x++) {
   scanf("%lld %lld",&kd[x],&v[x]);
   kind[kd[x]].push_back(x);
  }
  Node* root=Build(1,n);
  long long ans=0;
  for (int i=0;k>i;i++) {
//   cout<<"i="<<i<<endl;
   if (kind[i].size()>1) {
    int len=kind[i].size();
    for (int j=0;len-1>j;j++) {
//     cout<<"j="<<j<<endl;
     int L=j,R=len-1;
     while (R-L!=1) {
//      cout<<"L ~ R : "<<L<<" ~ "<<R<<endl;
      int mid=(L+R)>>1;
      if (query(root,1,n,kind[i][j],kind[i][mid]) <= p) R=mid;
      else L=mid;
     }
//     cout<<"j="<<j<<" , L="<<L<<endl;
     if (query(root,1,n,kind[i][j],kind[i][R]) > p) break;
     else ans+=(len-R);
//     cout<<"ans = "<<ans<<endl;
    }
   }
//   cout<<"ans="<<ans<<endl;
  }
  printf("%lld\n",ans);
 }
}