题目链接：http://codeforces.com/contest/650/problem/D
大意是给一个数组，若干询问，每一次把一个数字改为另一个数字，问当前数组最长上升子序列，询问之间是独立的。
注意到：假设初始数组的LIS长度为len。如果某一个位置的数字属于所有LIS，那么即便这个位置的数字被更改，答案至少是len-1，也有可能会因为变化维持len不变（未必是因为变化介于原来LIS前一个数字和后一个数字之间）。如果某一个位置的数字不是属于所有的LIS（属于某一种或者不属于任何LIS），那么答案至少是len，但也有可能因为变化新答案为len+1。至此，处理出所有位置的数字是否属于所有LIS的情况后，所有询问有了保底的答案。对于这两种情况，可能会产生不保底的情况，则需要对每一个询问查询，左边小于新数字的最大dp值，与右边大于新数字的最大dp值，两者相加再加上1与保底答案取最大值。具体操作，可以按照询问的位置对询问排序，离线处理。
具体写法有两种，一种是树状数组对原有数组数字与询问新数字全部离散化处理，以及基于LIS O(nlog(n))二分解法的写法。判断一个数字是否属于某一个LIS，条件是f[i]+g[i]==len-1? 其中f[i]和g[i]分别是以a[i]为结尾从1到i的LIS长度以及以a[i]为开端从i到n的LIS长度。判断一个数字是否属于所有LIS，则扫描所有属于某一种LIS的数字，统计它们的f值或者g值出现次数，如果某一个f值只出现了1次，则说明拥有这个f值的数字被所有LIS经过。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <map>
#include <set> using namespace std; const int N=1e6+;
int a[N],b[N];
struct Query {
int p,v;
int id;
int ans;
int l,r;
bool operator < (const Query &o) const {
return p<o.p;
}
}query[N]; int t[N];
inline int lowbit(int x) {
return x&(-x);
}
void upd(int x,int v) {
for (;x<N;x+=lowbit(x))
t[x]=max(t[x],v);
}
int ask(int x) {
int ret=;
for (;x;x-=lowbit(x))
ret=max(ret,t[x]);
return ret;
}
int lis(int n,int *f){
memset(t,,sizeof t);
int ret=;
for (int i=;i<n;i++) {
int d=ask(a[i]-);
upd(a[i],d+);
f[i]=d+;
ret=max(ret,d+);
}
return ret;
}
bool flag[N];int cnt[N];
int ret[N];
int f[N],g[N];
int main(){
int n,m;
scanf("%d %d",&n,&m);
for (int i=;i<n;i++) {
scanf("%d",a+i);
b[i]=a[i];
}
int tot=n;
for (int i=;i<m;i++) {
int x,y;
scanf("%d %d",&x,&y);
query[i].p=x-;
query[i].v=y;
query[i].id=i;
b[tot++]=y;
}
sort(b,b+tot);
int k=unique(b,b+tot)-b;
for (int i=;i<n;i++) {
a[i]=lower_bound(b,b+k,a[i])-b+;
}
for (int i=;i<m;i++) {
query[i].v=lower_bound(b,b+k,query[i].v)-b+;
}
int len=lis(n,f);
for (int i=;i<n;i++) {
a[i]=N-a[i];
}
reverse(a,a+n);
lis(n,g);
reverse(g,g+n); reverse(a,a+n);
for (int i=;i<n;i++) {
a[i]=N-a[i];
} memset(cnt,,sizeof cnt);
for (int i=;i<n;i++) {
if (f[i]+g[i]-==len) {
cnt[f[i]]++;
}
}
for (int i=;i<n;i++) {
if (f[i]+g[i]-==len&&cnt[f[i]]==) {
flag[i]=true;
}
} sort(query,query+m);
for (int i=;i<m;i++) {
int p=query[i].p;
if (flag[p])
query[i].ans=len-;
else
query[i].ans=len;
}
int st=;
memset(t,,sizeof t);
for (int i=;i<m;i++) {
int p=query[i].p;
for (;st<p;st++) {
int d=ask(a[st]-);
upd(a[st],d+);
}
int d=ask(query[i].v-);
query[i].l=d;
}
memset(t,,sizeof t);
for (int i=;i<n;i++) {
a[i]=N-a[i];
}
st=n-;
for (int i=m-;i>=;i--) {
int p=query[i].p;
query[i].v=N-query[i].v;
for (;st>p;st--) {
int d=ask(a[st]-);
upd(a[st],d+);
}
int d=ask(query[i].v-);
query[i].r=d;
query[i].ans=max(query[i].ans,query[i].l+query[i].r+);
ret[query[i].id]=query[i].ans;
}
for (int i=;i<m;i++) {
printf("%d\n",ret[i]);
}
return ;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <map>
#include <set> using namespace std; const int N=1e6+;
const int INF=0x3f3f3f3f;
int a[N];
struct Query {
int p,v;
int id;
int ans;
int l,r;
bool operator < (const Query &o) const {
return p<o.p;
}
}query[N];
int dp[N];
int f[N],g[N];
int cnt[N];
int lis(int n,int *f){
fill(dp,dp+n,INF);
for (int i=;i<n;i++) {
int pos=lower_bound(dp,dp+n,a[i])-dp;
dp[pos]=a[i];
f[i]=pos+;
}
return lower_bound(dp,dp+n,INF)-dp;
}
bool flag[N];
int ret[N];
int main(){
int n,m;
scanf("%d %d",&n,&m);
for (int i=;i<n;i++) {
scanf("%d",a+i);
}
for (int i=;i<m;i++) {
int x,y;
scanf("%d %d",&x,&y);
query[i].p=x-;
query[i].v=y;
query[i].id=i;
} int len=lis(n,f);
for (int i=;i<n;i++) {
a[i]=-a[i];
}
reverse(a,a+n); lis(n,g);
reverse(g,g+n); for (int i=;i<n;i++) {
a[i]=-a[i];
}
reverse(a,a+n); memset(cnt,,sizeof cnt);
for (int i=;i<n;i++) {
if (f[i]+g[i]-==len) {
cnt[f[i]]++;
}
}
for (int i=;i<n;i++) {
if (f[i]+g[i]-==len&&cnt[f[i]]==) {
flag[i]=true;
}
} sort(query,query+m);
for (int i=;i<m;i++) {
int p=query[i].p;
if (flag[p])
query[i].ans=len-;
else
query[i].ans=len;
} int st=;
fill(dp,dp+n,INF);
for (int i=;i<m;i++) {
int p=query[i].p;
for (;st<p;st++) {
int pos=lower_bound(dp,dp+n,a[st])-dp;
dp[pos]=a[st];
}
int pos=lower_bound(dp,dp+n,query[i].v)-dp;
query[i].l=pos;
} for (int i=;i<n;i++) {
a[i]=-a[i];
}
st=n-;
fill(dp,dp+n,INF);
for (int i=m-;i>=;i--) {
int p=query[i].p;
for (;st>p;st--) {
int pos=lower_bound(dp,dp+n,a[st])-dp;
dp[pos]=a[st];
}
int pos=lower_bound(dp,dp+n,-query[i].v)-dp;
query[i].r=pos;
query[i].ans=max(query[i].ans,query[i].l+query[i].r+);
ret[query[i].id]=query[i].ans;
}
for (int i=;i<m;i++) {
printf("%d\n",ret[i]);
}
return ;
}