SPOJ Another Longest Increasing Subsequence Problem
传送门:https://www.spoj.com/problems/LIS2/en/
题意:
给定 N个数对 \((x_i,y_i)\),求最长上升子序列的长度。上升序列定义为满足\((x_i,y_i)\)对i<j 有 \(x_i<x_j\) 且 \(y_i<y_j\)
题解:
一个三维最长链问题
第一维是存位置,第二维存x,第三维存y
注意查询是查询到p[i].z-1然后更新
细节方面和HDU4742是一样的
详情:https://www.cnblogs.com/buerdepepeqi/p/11193426.html
代码:
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********\n")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
struct node {
int x, y, z;
} p[maxn];
bool cmpx(node A, node B) {
return A.x < B.x;
}
bool cmpy(node A, node B) {
return A.y < B.y;
}
int lowbit(int x) {
return x & (-x);
}
int n;
int dp[maxn];
int Hash[maxn];
int bit[maxn];
void add(int pos, int val) {
while(pos < n + 2) {
bit[pos] = max(bit[pos], val);
pos += lowbit(pos);
}
}
int sum(int pos) {
int res = 0;
while(pos) {
res = max(res, bit[pos]);
pos -= lowbit(pos);
}
return res;
}
void init(int x) {
for(int i = x; i < n + 2; i += lowbit(i))
bit[i] = 0;
}
void solve(int l, int r) {
int mid = (l + r) >> 1;
sort(p + l, p + mid + 1, cmpy);
sort(p + mid + 1, p + r + 1, cmpy);
int j = l;
for(int i = mid + 1; i <= r; i++) {
while(j <= mid && p[j].y < p[i].y) {
add(p[j].z, dp[p[j].x]);
j++;
}
int tmp = sum(p[i].z - 1) + 1;
dp[p[i].x] = max(dp[p[i].x], tmp);
}
for(int i = l; i <= mid; i++) init(p[i].z);
sort(p + mid + 1, p + r + 1, cmpx);
}
void CDQ(int l, int r) {
if(l == r) {
return;
}
int mid = (l + r) >> 1;
CDQ(l, mid);
solve(l, r);
CDQ(mid + 1, r);
}
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d%d", &p[i].y, &p[i].z);
p[i].x = i;
dp[i] = 1;
Hash[i] = p[i].z;
}
sort(Hash + 1, Hash + n + 1);
int cnt = unique(Hash + 1, Hash + n + 1) - Hash - 1;
for(int i = 1; i <= n; i++) {
p[i].z = lower_bound(Hash + 1, Hash + cnt + 1, p[i].z) - Hash;
}
// debug1(n);
CDQ(1, n);
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = max(ans, dp[i]);
}
printf("%d\n", ans);
return 0;
}