真的是非常好的一道题，可以大幅增大各项能力，看懂了一定关了我的的代码自己写
一定一定一定一定一定一定要自己写，这个经验非常不错！！！！
非常详细的思路过程都在注释里面了
非常好理解，不理解请评论
#include<bits/stdc++.h>
using namespace std;
#define int long long
/*
题目看不懂，找了下
大意是给一个数组，若干询问，每一次把一个数字改为另一个数字，问当前数组最长上升子序列，询问之间是独立的。
树状数组求lis，非常好的一道综合能力提升的题（不论思维还是码力）
这道题可以让你对树状数组的理解大幅提升
注意树状数组的意义改变，代码也变了，要用来维护前缀max
假设比这个数都小的数中，lis长度为a
显然到这里就是a+1
然后大小维护好了，利用树状数组维护位置关系
所以每一次的f就是sum(v) (找值大小比他小的权值，这里权值就是最大lis)
但是由于前面有个=v的，不能算，所以应该是sum(v-1)
然后再add(a[i],f[i]),表明，在a[i]这个位置有一个f[i]的最长子序列了）
然后从1-n遍历就可以保证位置也是递增的（ 计算到某个点时，它后面的没有加上来，所以只有位置
在它前面的会影响他）
那么同理，我可以反着做一个最大下降序列（就是找这个数后面的）
现在我改变这个点的值
那么新的preup和新的nxtup会怎么变呢？
假设修改后的点为bi，原数组为a
对于preup就是找到1-i中一个数aj,要求在满足aj<bi的前提下找到最大的preup
nxtup就是i-n中aj,要求aj>bi的前提下找到最大的prenxt
我的程序中就用2xx来表示新数组吧
但是有个小问题，万一有多个询问在一个位置上，会导致不断被覆盖
为了不被覆盖，我就只能将2xx的值按询问顺序下标放
然后要找原来位置，就是这一次ask的pos了！
那最后的答案统计呢
我现在已知变前的nxtup,preup和变后的nxtup2,preup2
假设没变时lis为n；
若是变了以后>n那就是这个更大的答案
若是变了以后=n，那就不影响
若是变了以后<n，这个就要分两种情况了
如果变的这个在原来的lis的组成中，就是较小的答案
否则的话，不影响，那还是lis
怎么判断会不会影响？
处理出lis后，判断下nxtup+preup-1是否等于lis，等于就构成
但是像第二个样例，我的lis有多种组成方式，并不是充要的
所以要记录lis经过某一个点的次数，如果等于1的话，说明一定会遭
用cnt数组来完成
cnt[f[i]]记录路径数量 ,=1就G
如果wa在110个点（你算出来1998，1997这些的），记得数组开大点，我也不知道为什么
*/
int h[800005];
int cnt[800005];
int n,m;
struct node{
int pos;
int val;
int id;
}ask[800005];
int zg;
bool cmp(node x,node y){
if(x.pos!=y.pos)return x.pos<y.pos;
else return x.val<y.val;
}
int preup[800005];
int nxtup[800005];
int nxtup2[800005];
int preup2[800005];
int tree[800005];
int lowbit(int x){
return x&(-x);
}
void add1(int pos,int val){
for(int i=pos;i<=zg;i+=lowbit(i)){
tree[i]=max(tree[i],val);
}
}
int sum1(int pos){
int ret=0;
for(int i=pos;i>=1;i-=lowbit(i)){
ret=max(ret,tree[i]);
}
return ret;
}
void clear(){
memset(tree,0,sizeof(tree));
}
vector<int>num;
map<long long,int>mp;
int ans[800005];
void lsh(){
int st=0;
for(int i=0;i<num.size();i++){
if(mp[num[i]]==0){
mp[num[i]]=++st;
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> h[i];
num.push_back(h[i]);
}
for(int i=1;i<=m;i++){
cin >> ask[i].pos>> ask[i].val;//标号为a的高度，变为b,然后每个询问是独立的，互相不影响
ask[i].id=i;
num.push_back(ask[i].val);
//求每一次的最长上升子序列
}
sort(ask+1,ask+1+m,cmp);
sort(num.begin(),num.end());
lsh();
zg=mp.size();
int now=1;//枚举现在的qus
for(int i=1;i<=n;i++){//我想在这里就把2pre解决了
int v=mp[h[i]];
preup[i]=sum1(v-1)+1;
while(ask[now].pos==i){//现在在询问上,为了避免问两次同一个pos,占用了数组，我就只能放在q上了
preup2[now]=sum1(mp[ask[now].val]-1)+1;
now++;
}
add1(v,preup[i]);
}
now=m;//这里原来写的now=n
clear();
// cout<<zg<<" ";
int lis=-1;
for(int i=n;i>=1;i--){//权值反转反着做一遍最大上升，负负得正，最后顺序也是正着的最大上升子序列
int v=mp[h[i]];
nxtup[i]=sum1(zg-v)+1;
while(ask[now].pos==i){//同上
nxtup2[now]=sum1(zg-mp[(ask[now].val)])+1;
now--;
}
add1(zg-v+1,nxtup[i]);
}
for(int i=1;i<=n;i++){
lis=max(lis,preup[i]+nxtup[i]-1);
}
for(int i=1;i<=n;i++){
if(preup[i]+nxtup[i]-1==lis){
cnt[preup[i]]++;
}
}
for(int i=1;i<=m;i++){//注意2xx存的是i，但是xx存的是pos!!
int keypos=ask[i].pos;//关键位置
bool pan=0;
if(preup[keypos]+nxtup[keypos]-1==lis&&cnt[preup[keypos]]==1){
pan=1;
}
// printf("%d %d\n",nxtup2[i],preup2[i]);
if(nxtup2[i]+preup2[i]-1>lis){
ans[ask[i].id]=lis+1;
}
else if(nxtup2[i]+preup2[i]-1==lis){
ans[ask[i].id]=lis;
}
else{
if(pan==1){
ans[ask[i].id]=lis-1;
}
else{
ans[ask[i].id]=lis;
}
}
}
// printf("!!%d\n",lis);
for(int i=1;i<=m;i++){
cout<<ans[i]<<endl;
}
}