Trong thuật toán quy hoạch động ta dễ nhận ra có phần tìm Max và điều đầu tiên ta cần nghĩ đến là dùng IT hoặc BIT để tìm, thế nhưng ở đây ta lại có 2 giá trị vị trí, vì thế mình đã nghĩ đến mấy loại IT 2d hoạch BIT 2d nhưng không thể dùng được do `n <= 10^5` như vậy nếu dùng 2D ta sẽ mất `n^2` bộ nhớ nên ta loại cách này
Thế nên ta cần tìm một cách tối ưu hóa hay loại bỏ công việc thừa và ta nhận thấy rằng nếu ta tìm những khối hộp kích thước a', b' mà `a' < a; b' b-1)` của cây IT. Sau khi lấy xong ta lại cập nhật `Update(b, max(1 -> b-1))` cho vị trí `a` rồi đến tiếp với vị trí `a mới` lớn hơn `a cũ` và kết quả cuối cùng ta sẽ lấy `max(1 -> 10^6)`
Tham khảo code của
Sơn Đẹp Zai
Setup Sơn's define
// _____ _ _ // / ____| | | (_) // | (___ ___ _ __ __| | ___ _ __ ______ _ _ // \___ \ / _ \| '_ \ / _` |/ _ \ '_ \ |_ / _` | | // ____) | (_) | | | | | (_| | __/ |_) | / / (_| | | // |_____/ \___/|_| |_| \__,_|\___| .__/ /___\__,_|_| // | | // |_|#include <bits/stdc++.h> #define nmax 100005 #define oo 10000000007 #define mod 1000000007 #define reset(x) memset(x, 0, sizeof x) #define PB(x) push_back(x) #define F first #define S second #define sonin cin #define sonout cout #define debug(x) cout << "Loli -> " << #x << " : " << x << "\n" #define debugAry(x, a, b, y) for(int y = a; y<=b; y++) cout << #x << "[" << y << "]" << " -> " << x[y] << "\n" #define filename "TOWERBOX" #define fileNX freopen(filename".inp", "r", stdin); freopen(filename".out", "w", stdout); #define fileN freopen(filename".inp", "r", stdin); #define fileX freopen(filename".out", "w", stdout); #define toiuuhoa ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define SZ(a) (int) a.size() #define FOU(x,a,b) for (lli x=a;x<=b;x++) #define FOD(x,a,b) for (lli x=a;x>=b;x--) #define FOA(a,b) for(auto &a:b) #define ALLvec(a) a.begin(),a.end() #define REU(x,a,b) for (lli x=a;x<b;x++) #define RED(x,a,b) for (lli x=a;x>b;x--) #define AutoCinAry(a,b,x) for(int a = 1; a<=b; a++) cin >> x[i]; #define dembit1(x) __builtin_popcount(x) #define bit(x,i) ((x>>(i-1))&1ll) #define on(x,i) (x|(1ll<<(i-1))) #define off(x,i) (x&~(1ll<<(i-1))) #define EL cout << "\n"; #define EX exit(0); #define Ary(x, i, j, a) x[(i - 1) * a + j] #define epsinon 1e-8 #define Son_onii_chan main #define times double stime = clock(); #define gettime cerr << "Time executed: " << (clock() - stime) / CLOCKS_PER_SEC * 1000 << "ms.\n"; using namespace std; typedef long long lli; typedef long double ldo; typedef double dou; typedef vector vi; typedef vector vvi; typedef pair<lli, lli> pii; typedef vector vpi; typedef deque dqll;
O(n^2)
lli n, f[nmax]; vpi arr;lli dp(lli index){ if(f[index]!=0) return f[index]; f[index] = 1; FOU(i, 0, n-1){ if(arr[index].F > arr[i].F && arr[index].S > arr[i].S) f[index] = max(f[index], 1 + dp(i)); } return f[index]; } int Son_onii_chan(){ //fileN toiuuhoa sonin >> n; FOU(i,1,n){ lli a, b; sonin >> a >> b; arr.push_back({a, b}); } lli res = 1; FOU(i,0,n-1) res = max(res, dp(i)); sonout << res; return 0; }
O(nlogn)
lli n, saki[nmax]; vvi ara; vpi arr;struct IT { lli n; vector it; IT(lli n) : n(n) { it = vector(4 * n, 0); } void update(lli i, lli l, lli r, lli u, lli detal) { if (l == r) { it[i] = max(detal, it[i]); return; } lli mid = (l + r) / 2, li = i * 2; if (u >= l && u <= mid) { update(li, l, mid, u, detal); } if (u >= mid + 1 && u <= r) { update(li + 1, mid + 1, r, u, detal); } it[i] = max(it[li], it[li + 1]); } lli query(lli i, lli l, lli r, lli u, lli v) { if (l > v || r < u) return 0; if (l >= u && r <= v) return it[i]; lli mid = (l + r) / 2, li = i * 2; return max(query(li, l, mid, u, v), query(li + 1, mid + 1, r, u, v)); } };
bool cmp(pii ax, pii bx){ return ax.F < bx.F; } bool cmp2(pii ax, pii bx){ return ax.S < bx.S; } lli roihoa[2][1000005]; lli kkc = 1, kkcc = 1; void thahoa(lli i){ if(roihoa[1][arr[i-1].S] == 0){ roihoa[1][arr[i-1].S] = kkcc; arr[i-1].S = kkcc; kkcc++; } else arr[i-1].S = roihoa[1][arr[i-1].S]; } int Son_onii_chan(){ //fileN toiuuhoa //Input sonin >> n; FOU(i,1,n){ lli a, b; sonin >> a >> b; arr.push_back({a, b}); } //Rời rạc hóa (Không cần thiết) sort(arr.begin(), arr.end(), cmp2); FOU(i,1,n) thahoa(i); //Sắp xếp thao tác (Quan trọng) sort(arr.begin(), arr.end(), cmp); FOU(i,1,n){ if(roihoa[0][arr[i-1].F] == 0){ if(ara.size() > 0) sort(ara[kkc - 2].begin(), ara[kkc - 2].end()); ara.push_back(vi(0)); ara[kkc - 1].push_back(arr[i-1].S); roihoa[0][arr[i-1].F] = kkc; kkc++; } else { ara[kkc - 2].push_back(arr[i-1].S); } } //Xử lý tìm min, max bằng cây IT IT gg(kkcc); FOU(i,0,ara[0].size()-1) gg.update(1,1,kkcc,ara[0][i],1); FOU(i,1,ara.size()-1){ FOU(j,0,ara[i].size()-1) saki[j] = gg.query(1,1,kkcc,1,ara[i][j]-1) + 1; FOU(j,0,ara[i].size()-1) gg.update(1,1,kkcc,ara[i][j],saki[j]); } lli res = gg.query(1,1,kkcc,1,kkcc); sonout << res; return 0; }