传送门
大意：给出一个序列，求修改一个数过后的最长上升子序列。
思路：可以用主席树在线搞，也可以用树状数组离线搞，明显后者好写得多。我们首先读取所有的询问，然后就把询问绑在给出的位置，然后我们正向做一遍LIS，反向做一遍LDS，然后就可以解决这个问题了。
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXN 400005
using namespace std;
inline void GET(int &n) {
char c; n = 0;
do c = getchar(); while('0' > c || c > '9');
do n=n*10+c-'0',c=getchar();while('0' <= c && c <= '9');
}
vector<int> q[MAXN];
int lm[MAXN << 1], rm[MAXN << 1], B[MAXN << 1], a[MAXN];
int n, m, N, ask[MAXN], ans[MAXN], f[MAXN], g[MAXN], cnt[MAXN], qid[MAXN];
inline void gmax(int &a, int b) { if(a < b) a = b; }
inline void A2l(int x, int v) {
for(; x <= N; x += x&-x) gmax(lm[x], v);
}
inline void A2r(int x, int v) {
for(; x > 0; x -= x&-x) gmax(rm[x], v);
}
inline int Qml(int x, int v = 0) {
for(; x > 0; x -= x&-x) gmax(v, lm[x]); return v;
}
inline int Qmr(int x, int v = 0) {
for(; x <= N; x += x&-x) gmax(v, rm[x]); return v;
}
inline int BS(int p) {
int l = 1, r = N, mid, ans = 0;
while(l <= r) {
mid = (l + r) >> 1;
if(B[mid] >= p) { ans = mid; r=mid-1; }
else l = mid+1;
}
return ans;
}
int main() {
GET(n); GET(m); int id;
for(int i = 1; i <= n; ++ i) {
GET(a[i]); B[++ N] = a[i];
}
for(int i = 1; i <= m; ++ i) {
GET(qid[i]); GET(ask[i]);
q[qid[i]].push_back(i);
B[++ N] = ask[i];
ans[i] = 1;
}
sort(B + 1, B + N + 1);
N = unique(B + 1, B + N + 1) - B-1;
for(int i = 1; i <= n; ++ i)
a[i] = BS(a[i]);
for(int i = 1; i <= m; ++ i)
ask[i] = BS(ask[i]);
int lgst = 0;
for(int i = 1; i <= n; ++ i) {
for(auto j : q[i]) ans[j] += Qml(ask[j]-1);
f[i] = Qml(a[i]-1) + 1;
A2l(a[i], f[i]); lgst = max(lgst, f[i]);
}
for(int i = n; i > 0; -- i) {
for(auto j : q[i]) ans[j] += Qmr(ask[j]+1);
g[i] = Qmr(a[i]+1) + 1; A2r(a[i], g[i]);
}
for(int i = 1; i <= n; ++ i) if(f[i] + g[i] == lgst + 1) ++ cnt[ f[i] ];
for(int i = 1; i <= m; ++ i)
if(f[qid[i]] + g[qid[i]] == lgst + 1 && 1 == cnt[ f[qid[i]] ]) printf("%d\n", max(ans[i], lgst-1));
else printf("%d\n", max(ans[i], lgst));
return 0;
}