BZOJ 4867 分块+神tm卡常

时间：2024-12-05 16:07:44

思路：

注意到len<=10

按照权值max-min<=sqrt(n)*len 分块
记一下前缀和  每修改sqrt(n)次以后重新分块
修改的时候整块打标记  两边重构
（这题常数卡得要死   找同学要来fread才过）

查询的时候 就 二分答案 O(sqrt(n))判断

二分的上界要实时根据maxdeep变化才能过

//By SiriusRen

#include<bits/stdc++.h>

using namespace std;

const int N=;

int n,m,op,xx,yy,len,limval,Block,deep[N],cnt,dfn[N],lst[N],maxdep;

int first[N],next[N],v[N],w[N],tot,a[N],pos[N],maxx[N],minn[N],L[N],R[N],tag[N];

unsigned short sum[][];

inline int nextChr() {

    static const int siz=<<;

    static char buf[siz],*chr=buf+siz;

    if(chr==buf+siz)fread(chr=buf,,siz,stdin);

    return int(*chr++);

}

inline int read(){

    register int r=,c=nextChr();

    for(;c<;c=nextChr());

    for(;c>;c=nextChr())r=(r<<)+(r<<)+c-;

    return r;

}

inline void add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}

void dfs(int x){

    dfn[x]=++cnt,a[cnt]=deep[x];

    for(int i=first[x];~i;i=next[i])

        deep[v[i]]=deep[x]+w[i],dfs(v[i]);

    lst[x]=cnt;

}

void rebuild(int x){

    for(int i=;i<=limval;i++)sum[x][i]=;maxx[x]=;

    for(int i=L[x];i<=R[x];i++)sum[x][a[i]]++,maxx[x]=max(maxx[x],a[i]);

    for(int i=;i<=maxx[x];i++)sum[x][i]+=sum[x][i-];

}

void build(){

    int bs=;limval=n*len/Block;maxdep=;

    for(int i=;i<=n;i++)a[i]=a[i]+tag[pos[i]],maxdep=max(maxdep,a[i]);

    for(int i=;i<=n;){

        bs++,L[bs]=R[bs]=i,maxx[bs]=minn[bs]=a[i];

        while(i<=n&&max(maxx[bs],a[i])-min(minn[bs],a[i])<=limval&&R[bs]-L[bs]<=Block)

            R[bs]=i,pos[i]=bs,maxx[bs]=max(maxx[bs],a[i]),minn[bs]=min(minn[bs],a[i]),i++;

    }

    for(int i=;i<=bs;i++){

        maxx[i]-=(tag[i]=minn[i]);

        for(int j=L[i];j<=R[i];j++)a[j]-=tag[i];

        rebuild(i);

    }

}

void change(int l,int r,int wei){

    if(pos[l]==pos[r]){for(int i=l;i<=r;i++)a[i]+=wei;rebuild(pos[l]);}

    else{

        for(int i=l;i<=R[pos[l]];i++)a[i]+=wei;rebuild(pos[l]);

        for(int i=L[pos[r]];i<=r;i++)a[i]+=wei;rebuild(pos[r]);

        for(int i=pos[l]+;i<=pos[r]-;i++)tag[i]+=wei;

    }

}

int kth(int l,int r,int wei){

    int ans=;

    if(pos[l]==pos[r]){for(int i=l;i<=r;i++)ans+=(tag[pos[l]]+a[i]<=wei);}

    else{

        for(int i=l;i<=R[pos[l]];i++)ans+=(tag[pos[l]]+a[i]<=wei);

        for(int i=L[pos[r]];i<=r;i++)ans+=(tag[pos[r]]+a[i]<=wei);

        for(int i=pos[l]+;i<=pos[r]-;i++)if(wei>=tag[i])

            ans+=sum[i][min(maxx[i],wei-tag[i])];

    }return ans;

}

int bsrch(int l,int r,int k){

    if(r-l+<k)return -;

    int lft=,rit=maxdep,ans=-;

    while(lft<=rit){

        int mid=(lft+rit)>>;

        if(kth(l,r,mid-)+<=k)lft=mid+,ans=mid;

        else rit=mid-;

    }return ans;

}

int main(){

    memset(first,-,sizeof(first));

    n=read(),m=read(),len=read(),Block=min(n,(int)sqrt(n));

    for(int i=;i<=n;i++)xx=read(),yy=read(),add(xx,i,yy);

    dfs(),build();

    while(m--){

        if(cnt>Block)cnt=,build();

        op=read(),xx=read(),yy=read();

        if(op==)printf("%d\n",bsrch(dfn[xx],lst[xx],yy));

        else limval+=yy,maxdep+=yy,change(dfn[xx],lst[xx],yy),cnt++;

    }

}

相关文章