HDU多校第六场 1002 Nonsense Time —— LIS删点

本文主要是介绍HDU多校第六场 1002 Nonsense Time —— LIS删点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    长度为 $n$ 的排列 $p$，一开始全部冻结
    每次永久释放 $p_{k_i}$
    求每次释放之后的 $LIS$

解题思路：

    要查找 $x$ 是否在 $LIS$ 中，考虑用树状数组维护
    树状数组 $t[i]$ 记录的是每个点 $LIS$ 的位置，而不是值

核心：期望$LIS$，树状数组维护位置

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 5;
int T, n, a[maxn], k[maxn], ans[maxn];
int l[maxn], r[maxn], used[maxn];
int t[maxn], f[maxn], pre[maxn]; inline int lb(int x){return x & -x;
}inline void update(int x, int p){for(int i=x; i<=n; i+=lb(i))if(f[t[i]] < f[p]) t[i] = p;
}inline int query(int x){int ret = 0;for(int i=x; i; i-=lb(i))if(f[t[i]] > f[ret]) ret = t[i];return ret;
}inline void lis(){for(int i=0; i<=n+1; i++) t[i] = f[i] = used[i] = 0;for(int i=r[0]; i<=n+1; i=r[i]){int q = query(a[i]);f[i] = f[q] + 1;pre[i] = q;update(a[i], i);}for(int i=n+1; i; i=pre[i]) used[i] = 1;
}int main() {scanf("%d", &T);while(T--){scanf("%d", &n);a[n+1] = n + 1;for(int i=1; i<=n; i++) scanf("%d", a+i);for(int i=1; i<=n; i++) scanf("%d", k+i);for(int i=0; i<=n+1; i++) l[i] = i-1, r[i] = i+1;lis();for(int i=n; i; i--){ans[i] = f[n+1] - 1;l[r[k[i]]] = l[k[i]];r[l[k[i]]] = r[k[i]];if(used[k[i]]) lis();}for(int i=1; i<=n; i++) printf("%d%c", ans[i], i<n ? ' ' : '\n');}
}

这篇关于HDU多校第六场 1002 Nonsense Time —— LIS删点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---