SPOJ Another Longest Increasing Subsequence Problem 三维最长链

迈不过友情╰ 2021-12-04 06:59 152阅读 0赞

# SPOJ Another Longest Increasing Subsequence Problem #

传送门：[https://www.spoj.com/problems/LIS2/en/][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][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; }

转载于:https://www.cnblogs.com/buerdepepeqi/p/11194811.html

[https_www.spoj.com_problems_LIS2_en]: https://www.spoj.com/problems/LIS2/en/
[https_www.cnblogs.com_buerdepepeqi_p_11193426.html]: https://www.cnblogs.com/buerdepepeqi/p/11193426.html