令人抓狂的整体二分题。根本原因还是我太菜了。

在学校写了一个下午写得头晕，回家里重写了一遍，一个小时就写完了……不过还是太慢。

题目传送门：。

题意简述：

一棵 \(n\) 个结点的树，每个点有点权。

有 \(m\) 次操作，每个操作要么是更改单点点权，要么是查询树链上第 \(k\) 大点权。

题解：

树套树固然可以，但是整体二分也很好。

整体二分就是对于所有的询问一起二分答案，在二分区间范围内的查询和修改一并下传。

这题把整体二分基础题的操作搬到了链上，但是实现方法并没有太大不同。

初始点权看成增加点权，插入在所有操作的最前面即可。

更改点权可以看成删除点权再增加点权，变成两次修改即可。

这题整体二分要求第 \(k\) 大，考虑二分出的答案 \(mid\)，将大于 \(mid\) 的修改转成单点权值 \(\pm 1\)，

而对于树链查询第 \(k\) 大，则转化成链上权值之和是否等于 \(k\)。

写整体二分题永远要注意二分的条件，我的条件是，链上大于 \(mid\) 的点数小于 \(k\) 个则答案小于等于 \(mid\)，否则答案大于 \(mid\)。

单点修改，树链查询要是还用树剖就太naive了，套路转化：

考虑每个节点维护到根的路径上的信息，那么单点修改就变成子树修改，链查就变成四个单点查了（需要求LCA）。

而子树是一个区间，区间加法，单点查询；再使用树状数组差分技巧转化成单点差分，区间前缀和。

注意到还要求LCA，直接在DFS的时候用Tarjan处理就好了。

关于判断无解：当然可以直接处理掉……不过这样就必须求树链长度了。

我的方法是，往权值里面加一个-1，如果答案是-1，则真实答案应该是无解。

我的代码还离散化了权值，其实没用……

其他恶心的地方就是整体二分基本功了，太弱了调了好久……注意循环变量是指向真实操作的下标的指针还是真实操作的下标，如果你写结构体当我没说。

#include
    
     #include
     
      #include
      
       using namespace std;const int MN=80005;const int MM=110005;const int MQ=140005;int n,m,q,w[MN],d[MQ],c;int o[MQ],a[MQ],b[MQ],p[MQ],lc[MQ],ans[MQ];int eh[MN],qh[MN],nxt[MM*2],to[MM*2],tot;inline void ins(int*h,int x,int y){nxt[++tot]=h[x],to[tot]=y,h[x]=tot;}int ld[MN],rd[MN],faz[MN],dfc;int fa[MN];int ff(int x){return fa[x]?fa[x]=ff(fa[x]):x;}void dfs(int u,int f){    faz[u]=f,ld[u]=++dfc;    for(int i=eh[u];i;i=nxt[i])if(to[i]!=f)dfs(to[i],u),fa[to[i]]=u;    for(int i=qh[u];i;i=nxt[i])if(lc[to[i]])lc[to[i]]=ff(lc[to[i]]);else lc[to[i]]=u;    rd[u]=dfc;}int B[MN];inline void I(int i,int x){for(;i<=n;i+=i&-i)B[i]+=x;}inline int Q(int i){int a=0;for(;i;i-=i&-i)a+=B[i];return a;}int t[MQ];void s(int l,int r,int L,int R){    if(l>r)return;    if(L==R){for(int i=l;i<=r;++i)ans[p[i]]=L;return;}    int m=L+R>>1,p1=l-1,p2=r+1;    for(int j=l,i;j<=r;++j){        if(o[i=p[j]]>0){            int x=Q(ld[a[i]])+Q(ld[b[i]])-Q(ld[lc[i]])-Q(ld[faz[lc[i]]]);            if(x
       
        m){            I(ld[a[i]],o[i]?-1:1),I(rd[a[i]]+1,o[i]?1:-1);            t[--p2]=i;        }        else t[++p1]=i;    }    for(int i=l;i<=r;++i)if(o[p[i]]<=0&&b[p[i]]>m)I(ld[a[p[i]]],o[p[i]]?1:-1),I(rd[a[p[i]]]+1,o[p[i]]?-1:1);    reverse(t+p2,t+r+1),memcpy(p+l,t+l,r-l+1<<2);    s(l,p1,L,m),s(p2,r,m+1,R);}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;++i)scanf("%d",&w[i]),o[++q]=0,a[q]=i,b[q]=w[i],p[q]=q;    for(int i=1,x,y;i
        
         0)ins(qh,a[i],i),ins(qh,b[i],i);else d[++c]=b[i];    d[++c]=-1;sort(d+1,d+c+1);c=unique(d+1,d+c+1)-d-1;    for(int i=1;i<=q;++i)if(o[i]<=0)b[i]=lower_bound(d+1,d+c+1,b[i])-d;    dfs(1,0),s(1,q,1,c);    for(int i=1;i<=q;++i)if(o[i]>0)ans[i]==1?puts("invalid request!"):printf("%d\n",d[ans[i]]);    return 0;}// 20:08 - 21:03