题面
题目链接
https://www.luogu.com.cn/problem/P4309
题目大意
给定一个序列，初始为空。
现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。
每插入一个数字，我们都想知道此时最长上升子序列长度是多少？
解题思路
因为每次插入的数是按顺序从小到大的，所以我们可以从后往前计算
我们先用 vector 自带的 insert 函数得到所有数都插入完后的序列，然后从 n 到 1 依次计算
当计算完第 i 次操作的 Lis 后只要把 i 这个数的贡献去掉即可返回第 i - 1 次操作
然后就没有然后了。。。
以上步骤用 线段树 or 树状数组 维护都可
感觉挺水的一道题，不理解为什么会是紫题
AC_Coder 线段树
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; struct Tree { int l, r, lazy, maxn; } tree[N << 2]; void push_up(int rt) { tree[rt].maxn = max(tree[rt << 1].maxn, tree[rt << 1 | 1].maxn); } void push_down(int rt, int length) { if(tree[rt].lazy) { tree[rt << 1].lazy += tree[rt].lazy; tree[rt << 1 | 1].lazy += tree[rt].lazy; tree[rt << 1].maxn += tree[rt].lazy; tree[rt << 1 | 1].maxn += tree[rt].lazy; tree[rt].lazy = 0; } } void build(int l, int r, int rt, int *aa) { tree[rt].lazy = 0; tree[rt].l = l; tree[rt].r = r; if(l == r) { tree[rt].maxn = aa[l]; return; } int mid = (l + r) >> 1; build(l, mid, rt << 1, aa); build(mid + 1, r, rt << 1 | 1, aa); push_up(rt); } void update_range(int L, int R, int key, int rt) { if(tree[rt].r < L || tree[rt].l > R) return; if(L <= tree[rt].l && R >= tree[rt].r) { tree[rt].maxn += key; tree[rt].lazy += key; return; } push_down(rt, tree[rt].r - tree[rt].l + 1); int mid = (tree[rt].r + tree[rt].l) >> 1; if(L <= mid) update_range(L, R, key, rt << 1); if(R > mid) update_range(L, R, key, rt << 1 | 1); push_up(rt); } int query_max(int L, int R, int rt) { if(L <= tree[rt].l && R >= tree[rt].r) return tree[rt].maxn; push_down(rt, tree[rt].r - tree[rt].l + 1); int mid = (tree[rt].r + tree[rt].l) >> 1; int ans = -(0x3f3f3f); if(L <= mid) ans = max(ans, query_max(L, R, rt << 1)); if(R > mid) ans = max(ans, query_max(L, R, rt << 1 | 1)); return ans; } vector<int> vec, ans; int a[N], aa[N], n; signed main() { ios::sync_with_stdio(false); cin >> n; for(int i = 1; i <= n; i++) { int pos; cin >> pos; vec.insert(vec.begin() + pos, i); } for(int i = 1; i <= n; i++) a[i] = vec[i - 1]; build(1, n, 1, aa); for(int i = 1; i <= n; i++) { int val = a[i]; int ma = max(0, query_max(1, a[i] - 1, 1)); update_range(a[i], a[i], ma + 1, 1); } for(int i = n; i; i--) { int res = query_max(1, n, 1); ans.push_back(res); update_range(i, i, -0x3f3f3f, 1); } reverse(ans.begin(), ans.end()); for(auto i : ans) cout << i << ' '; return 0; }
AC_Coder 树状数组
#include<bits/stdc++.h> using namespace std; const int N = 3e5 + 10; int n , tree[N] , a[N]; vector<int>vec , ans; int lowbit(int x) { return x & (-x); } void Add(int pos , int val) { while(pos <= N) { tree[pos] = max(tree[pos] , val) ; pos += lowbit(pos); } } int Get_max(int pos) { int res = 0 ; while(pos) { res = max(res , tree[pos]); pos -= lowbit(pos); } return res ; } signed main() { ios::sync_with_stdio(false); cin >> n; for(int i = 1 ; i <= n ; i ++) { int pos ; cin >> pos; vec.insert(vec.begin() + pos , i); } for(int i = 1 ; i <= n ; i ++) a[i] = vec[i - 1]; for(int i = 1 ; i <= n ; i ++) { int ma = Get_max(a[i]); Add(a[i] , ma + 1); } for(int i = n ; i ; i --) { int res = Get_max(i); ans.push_back(res); Add(i , -(0x3f3f3f3f)); } reverse(ans.begin() , ans.end()); for(auto i : ans) cout << i << ' ' ; return 0; }