题意分析

带修改树链第\(k\)大

首先我们使用树链剖分将树上问题转化为区间问题

然后对于当前修改我们直接修改即可

对于链上第\(k\)大我们先求一个总点数

转化为链上第\(k\)小

然后我们将\(x\)到\(y\)之间所有的重链都提出来

那么在\(dfs\)序上就是一堆连续区间

而且最多\(log\)个

类比于区间问题维护一个区间

我们顶多维护\(log\)个区间

然后同时跳即可详细见代码即可

CODE:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define ll long long#define inf 0x7fffffff#define N 80008#define IL inline#define M 1008611#define D double#define ull unsigned long long#define R registerusing namespace std;template
                   
                    IL void read(T &_){ T __=0,___=1;char ____=getchar(); while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();} while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();} _=___ ? __:-__;}/*-------------OI使我快乐-------------*/int n,m,tot,cnt,all;struct Node{ int fro,tox,cnta,cntb; int cdy[30],wzy[30];}e[N];struct Qury{ int k,a,b;}ex[N];int num[N],res[N<<1];int to[N<<1],nex[N<<1],head[N];int dep[N],fa[N],ssiz[N],son[N];int top[N],dfn[N],wt[N];int root[N],lson[M*40],rson[M*40],siz[M*40];IL void add(int x,int y){to[++tot]=y;nex[tot]=head[x];head[x]=tot;}IL int get_hash(int x){return lower_bound(res+1,res+cnt+1,x)-res;}IL void insert(int &now,int le,int ri,int pos,int d){ if(!now) now=++tot;siz[now]+=d; if(le==ri) return; int mid=(le+ri)>>1; if(pos<=mid) insert(lson[now],le,mid,pos,d); else insert(rson[now],mid+1,ri,pos,d);}IL void Add(int x,int pos,int d){ for(R int i=x;i<=n;i+=i&-i) insert(root[i],1,cnt,pos,d);}IL void get_ready(){ for(R int i=1;i<=all;++i) { e[i].cnta=0;e[i].cntb=0; for(R int j=e[i].fro-1;j>0;j-=j&-j) e[i].cdy[++e[i].cnta]=root[j]; for(R int j=e[i].tox;j>0;j-=j&-j) e[i].wzy[++e[i].cntb]=root[j]; }}IL void dfs1(int now,int fat){ dep[now]=dep[fat]+1;fa[now]=fat;ssiz[now]=1; int maxsiz=-1; for(R int i=head[now];i;i=nex[i]) { int v=to[i]; if(v==fat) continue; dfs1(v,now); ssiz[now]+=ssiz[v]; if(ssiz[v]>maxsiz) maxsiz=siz[v],son[now]=v; }}IL void dfs2(int now,int topf){ top[now]=topf;dfn[now]=++all;wt[all]=now; if(!son[now]) return;dfs2(son[now],topf); for(R int i=head[now];i;i=nex[i]) { int v=to[i]; if(v==fa[now]||v==son[now]) continue; dfs2(v,v); }}IL int LCA(int nowx,int nowy){ while(top[nowx]!=top[nowy]) { if(dep[top[nowx]]
                    
                     dep[nowy]) swap(nowx,nowy); return nowx;}IL void QuryRange(int nowx,int nowy){//我们提出所有的dfs序的连续区间 while(top[nowx]!=top[nowy]) { if(dep[top[nowx]]
                     
                      dep[nowy]) swap(nowx,nowy); ++all;e[all].fro=dfn[nowx];e[all].tox=dfn[nowy]; return;}IL int getsiz(int x,int y){ int lca=LCA(x,y); return dep[x]+dep[y]-dep[lca]-dep[fa[lca]];}IL int getsum(){//类似于动态主席树 int res=0; for(R int i=1;i<=all;++i) { for(R int j=1;j<=e[i].cnta;++j) res-=siz[lson[e[i].cdy[j]]]; for(R int j=1;j<=e[i].cntb;++j) res+=siz[lson[e[i].wzy[j]]]; } return res;}IL void pushcdy(){ for(R int i=1;i<=all;++i) { for(R int j=1;j<=e[i].cnta;++j) e[i].cdy[j]=lson[e[i].cdy[j]]; for(R int j=1;j<=e[i].cntb;++j) e[i].wzy[j]=lson[e[i].wzy[j]]; }}IL void pushwzy(){ for(R int i=1;i<=all;++i) { for(R int j=1;j<=e[i].cnta;++j) e[i].cdy[j]=rson[e[i].cdy[j]]; for(R int j=1;j<=e[i].cntb;++j) e[i].wzy[j]=rson[e[i].wzy[j]]; }}IL int getrnk(int le,int ri,int k){ while(le
                      
                       >1; int tmp=getsum(); if(k<=tmp) ri=mid,pushcdy(); else k-=tmp,le=mid+1,pushwzy(); } return le;}int main(){// freopen("222.in","r",stdin);// freopen("222.out","w",stdout); read(n);read(m); for(R int i=1;i<=n;++i) read(num[i]),res[++cnt]=num[i]; for(R int i=1,x,y;i