(UVA) 11790 - Murcia's Skyline [max value of increasing sequence]

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

可以把題目簡化成這個樣子：

給你兩個長度n的序列(題目沒給n的大小QQ，看了我的作法後，我覺得n可以到1e5量級)，第一個序列叫 a, 第二個序列就b。

每當從a序列選擇一個元素ai時，可以獲得bi的價值。

那我就假設a序列叫 "重量" ， b序列叫 "價值"

現在，請你找到一條嚴格遞增 & 嚴格遞減 序列，使得這兩個的價值分別最大，最後按照比較輸出。

我的想法是這樣：開一個segment tree維護最小值，令segment tree的位置 i 的意義為：以重量i為尾巴的 遞增(遞減) 序列，最大的 "價值" 是多少。

對於每個新來的重量w，價值v，我先找 (1~w-1)的 max，加了v之後，存到線段樹 w的位置。

複雜度：O (n lg n)

(我也有在code離散化了一下)

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

const int MAX_N = 1e5+6;
int w[MAX_N];
int v[MAX_N];

struct Node {
 Node *lc,*rc;
 int val;
 Node() {
  lc=rc=NULL;
  val=0;
 }
 void pull() {
  val=max(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);
 return node;
}

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

vector<int> vec;

int main () {
// freopen("output.txt","w",stdout);
 int T;
 scanf("%d",&T);
 for (int qq=1;T>=qq;qq++) {
  printf("Case %d. ",qq);
  vec.clear();
  int n;
  scanf("%d",&n);
  for (int x=1;n>=x;x++) {
   scanf("%d",&w[x]);
   vec.push_back(w[x]);
  }
  for (int x=1;n>=x;x++) {
   scanf("%d",&v[x]);
  }
  sort(vec.begin(),vec.end());
  vec.resize(unique(vec.begin(),vec.end()) - vec.begin());
  for (int x=1;n>=x;x++) {
   w[x] = lower_bound(vec.begin(),vec.end(),w[x]) - vec.begin() + 1;
  }
  Node* root=Build(1,n);
  for (int x=1;n>=x;x++) {
   modify(root,1,n,w[x],query(root,1,n,1,w[x]-1)+v[x]);
  }
  int A=query(root,1,n,1,n);
  
  for(int x=1;n>=x;x++) w[x] = n - w[x] + 1;
  root=Build(1,n);
  
  for (int x=1;n>=x;x++) {
   modify(root,1,n,w[x],query(root,1,n,1,w[x]-1)+v[x]);
  }
  int B=query(root,1,n,1,n);
  
  if (A>=B) printf("Increasing (%d). Decreasing (%d).\n",A,B);
  else printf("Decreasing (%d). Increasing (%d).\n",B,A);
 }
}