题面

给出长度为 $n$ 的序列，$q$ 次修改，求每次修改首项固定的最长上升子序列长度，$n,q\le 10^5$

解题思路

线段树（合并较难）

分析

感觉有点像线段树，但是线段树维护的话，合并的时候貌似不能 $O(1)$，然后就放弃了

结果，正解合并就是 $\log$ 的……深深地明白自己的弱小

这样子的话，就是可以给我们要维护的区间找一找相同点或者不同点，比如我们发现一开始的区间，如果有建筑，那么这个建筑是肯定要选的，换句话说，可以认为就是某个区间的左端点必须选，因为肯定是看得到第一幢建筑的，那么由于这个特殊性质处理起来比较麻烦，我们考虑能不能让所有区间都带上这个性质，思考之后可以发现，这样是可以的，而且经过这样的处理，就不用去管第一个点必须选的特殊性了

再考虑哪些信息有用，区间中的最大值 $fa[k]$ 是需要的，因为该区间中的合法序列肯定以该值结尾，当然还要一个 $f[k]$ 记录当前区间的最长序列的长度

考虑如何合并答案，$fa[k]$ 的合并较简单，$O(1)$ 转移即可（如果有不会的……，问题在于如何对 $f[k]$ 进行合并

先枚举几种情况，

  • $fa[ls]\ge fa[rs]$，左区间的最大值比右区间的大，右区间无贡献，故 f[k]=f[ls]
  • $fa[ls]<a[m+1]$，左区间的最大值小于右区间的左端点，右区间都有贡献，故 f[k]=f[ls]+f[rs]
  • $a[m+1]\le fa[ls]< fa[rs]$，也就是两区间的序列有交叉的部分，此时要计算贡献，只能用 $\log n$ 式递归查询

处理上述最后一种情况，即查询右区间中范围在 $fa[ls]$~$fa[rs]$ 的部分

最大限制不用管，肯定能满足，就考虑最小限制 $fa[ls]$，记为 $val$，考虑如何递归计算

  • 若一个区间的最大值 $fa[k]\le val$ ，那么这个区间没有贡献 return 0
  • 若一个区间的左端点 $a[l]>val$，那么整个区间都有贡献 return f[k]
  • 若只有一个点，即递归边界，则 return a[l]>val
  • 上述情况都不满足，但若左区间的最大值 $fa[k]>val$，说明有一部分贡献在左区间，递归左区间，加上右区间 return Query(ls,l,m)+f[k]-f[ls|1] (右区间很妙)
  • 否则就说明贡献在右区间，递归右区间即可 return Query(ls|1,m+1,r)

如此一来，就可以在 $O(q\log^2n)$ 复杂度内求解

warning

1、$Updata$ 的递归边界一定要判

2、右区间可以由 f[k]-f[ls] 得，真的很妙

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 100003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,T,pos,f[N<<2];
double a[N],fa[N<<2],val;
inline int Query(rint k,rint l,rint r) {
    if(fa[k]<=val) return 0;//最大值小于val
    if(a[l]>val) return f[k];//val小于左端点
    if(l==r) return 0;//递归边界
    rint m=(l+r)>>1,ls=k<<1;
    if(val<fa[ls]) return Query(ls,l,m)+f[k]-f[ls];//val在左区间有贡献
    return Query(ls|1,m+1,r);//在左区间无贡献
}
inline void Modify(rint k,rint l,rint r) {
    if(l==r) {fa[k]=a[l],f[k]=(a[l]!=0);return;}
    rint m=(l+r)>>1,ls=k<<1,rs=ls|1;
    (pos<=m)?Modify(ls,l,m):Modify(rs,m+1,r);
    if(fa[ls]>=fa[rs]) fa[k]=fa[ls],f[k]=f[ls];//只有左区间有贡献
    else { fa[k]=fa[rs];
        if(fa[ls]<a[m+1]) f[k]=f[ls]+f[rs];//左右区间贡献不重叠
        else val=fa[ls],f[k]=f[ls]+Query(rs,m+1,r);//要递归求的部分
    }
}
int main() {
    n=read(),T=read();
    while(T--) {
        pos=read(),a[pos]=(double)read()/pos;
        Modify(1,1,n),printf("%d\n",f[1]);
    }
    return 0;
}

devil.