本文共 2014 字，大约阅读时间需要 6 分钟。
分析：
注意所有m此操作中，只会发生一个，于是考虑dp。dp[i]=dp[j]+1，j<i，a[j]<=L[i]，R[j]<=a[i]。L[i]为位置i处，所有可能发生的改变中的最小值，R[i]为最大值。
这是三维偏序问题，于是CDQ+树状数组。
代码：
#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;inline int read() { int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;}const int N = 200005;int dp[N];struct Node { int id, x, l, r; } A[N], B[N];bool cmp1(Node A, Node B) { return A.l < B.l; }bool cmp2(Node A, Node B) { return A.x < B.x; }bool cmp3(Node A, Node B) { return A.id < B.id; }struct Bit{ int mx[N], n; void update(int p,int v) { for (; p <= n; p += (p & (-p))) mx[p] = max(mx[p], v); } int query(int p) { int ans = 0; for (; p; p -= (p & (-p))) ans = max(ans, mx[p]); return ans; } void clear(int p) { for (; mx[p] && p <= n; p += (p & (-p))) mx[p] = 0; }}bit;void cdq(int l,int r) { if (l >= r) return ; int mid = (l + r) >> 1; cdq(l, mid); sort(A + mid + 1, A + r + 1, cmp1); int i = l, j = mid + 1; while (i <= mid && j <= r) { if (A[i].x <= A[j].l) { bit.update(A[i].r, dp[A[i].id]); i ++; } else { dp[A[j].id] = max(dp[A[j].id], bit.query(A[j].x) + 1); j ++; } } while (j <= r) { dp[A[j].id] = max(dp[A[j].id], bit.query(A[j].x) + 1); j ++; } for (int k = l; k < i; ++k) bit.clear(A[k].r); sort(A + mid + 1, A + r + 1, cmp3); cdq(mid + 1, r); sort(A + l, A + r + 1, cmp2);}int main() { int n = read(), m = read(); bit.n = n; for (int i = 1; i <= n; ++i) A[i].id = i, A[i].x = A[i].l = A[i].r = read(); for (int i = 1; i <= m; ++i) { int x = read(), y = read(); A[x].l = min(A[x].l, y), A[x].r = max(A[x].r, y); } for (int i = 1; i <= n; ++i) dp[i] = 1; cdq(1, n); int ans = 0; for (int i = 1; i <= n; ++i) ans = max(ans, dp[i]); cout << ans; return 0;}
转载于:https://www.cnblogs.com/mjtcn/p/10529341.html