【分块】少女与战车

· · 题解

此题 1e5，分块逃不过。

尝试这样分块：

块内元素数目不超过sqrt(n)个，且块内元素最大值与最小值之差不超过2000。记录块内每个元素比块内元素最小值大多少，记在一个数组里，跑一边前缀和，这样便可以O(1)的时间内查询块内小于k的元素的个数。

查询很简单，不必赘述。考虑修改，整块修改放懒惰标记，其余的可以这样：每次加一个不超过10的值，那么只进行1000次修改块内元素最大值与最小值之差不会超过20000，依然能用数组存下。那么每进行1000次操作就重新分块，时间复杂度约O(nsqrt(n)log(n))，可以跑过。

代码： 

#include<bits/stdc++.h>
#define Min(x,y)    ((x)<(y)?   (x):(y))
#define Max(x,y)    ((x)>(y)?   (x):(y))
using namespace std;
const int blo=300,s=2000;
const int INF=0x3f3f3f3f;
const int SIZEBLO=2010,N=100010;
int n,m,len,tot;
int cnt=0,hed[N],to[N],nxt[N],val[N];
int dfn[N],idx=0,dep[N],low[N];
int bl[N],L[SIZEBLO],R[SIZEBLO],lz[SIZEBLO],bL[SIZEBLO],bR[SIZEBLO],sum[SIZEBLO][20010];
int sta[N],Dis[N],mark[N],top=0;

inline int read() {
    register int tmp=0;register bool flag=0;register char c=getchar();
    while(c<'0'||c>'9') { if(c=='-')    flag=1;c=getchar(); }
    while(c>='0'&&c<='9')   tmp=(tmp<<1)+(tmp<<3)+(c^48),c=getchar();
    return flag?    -tmp:tmp;
}
inline void add(int x,int y,int z) { to[++cnt]=y,val[cnt]=z,nxt[cnt]=hed[x],hed[x]=cnt; }
void dfs(int u,int dis) {
    dfn[u]=++idx,dep[idx]=dis; for(int i=hed[u];i;i=nxt[i]) dfs(to[i],dis+val[i]);
    low[u]=idx;
}
void Dfs(int u,int dis) {
    sta[++top]=u,Dis[top]=dis;
    while(top) {
        int v1=sta[top],v2=Dis[top],v3=mark[top];
        if(v3) { low[v1]=idx,--top;continue; }
        dfn[v1]=++idx,dep[idx]=v2,mark[top]=1;
        for(int i=hed[v1];i;i=nxt[i])   sta[++top]=to[i],Dis[top]=v2+val[i],mark[top]=0;
    }
}
inline void reset(int x) {
    if(!lz[x])  return ; for(int i=L[x];i<=R[x];i++)    dep[i]+=lz[x]; lz[x]=0;
}
inline void update(int x) {
    bL[x]=INF,bR[x]=-INF;
    for(int i=L[x];i<=R[x];i++) bL[x]=Min(bL[x],dep[i]),bR[x]=Max(bR[x],dep[i]);
    for(int i=0;i<=bR[x]-bL[x];i++) sum[x][i]=0;
    for(int i=L[x];i<=R[x];i++) ++sum[x][dep[i]-bL[x]];
    for(int i=1;i<=bR[x]-bL[x];i++) sum[x][i]+=sum[x][i-1];
}
void build() {
    for(int i=1;i<=bl[n];i++)   reset(i);
    int lx=INF,rx=-INF,u=1;L[1]=1;
    for(int i=1;i<=n;i++) {
        lx=Min(lx,dep[i]),rx=Max(rx,dep[i]);
        if(rx-lx>s||i-L[u]>=blo)    lx=rx=dep[i],R[u]=i-1,L[++u]=i;
        bl[i]=u;
    }
    R[u]=n; for(int i=1;i<=bl[n];i++)   update(i);
}
inline int Getval(int x,int w) {
    if(w<bL[x]) return 0; if(w>=bR[x])  return sum[x][bR[x]-bL[x]];
    return sum[x][w-bL[x]];
}
inline int query(int l,int r,int w) {
    int Count=0;
    if(bl[l]+1>=bl[r]) {
        for(int i=l;i<=r;i++)   if(dep[i]<=w)   ++Count;
        return Count;
    }
    for(int i=l;i<=R[bl[l]];i++)    if(dep[i]<=w)   ++Count;
    for(int i=L[bl[r]];i<=r;i++)    if(dep[i]<=w)   ++Count;
    for(int i=bl[l]+1;i<bl[r];i++)  Count+=Getval(i,w);
    return Count;
}
inline int Kth(int l,int r,int k) {
    if(r-l+1<k) return -1;
    reset(bl[l]),reset(bl[r]);
    int ll=INF,rr=-INF,midd,tans=0;
    for(int i=bl[l];i<=bl[r];i++)   ll=Min(ll,bL[i]),rr=Max(rr,bR[i]);
    if(ll==rr)  return ll;
    while(ll<=rr) {
        midd=(ll+rr)>>1;
        if(query(l,r,midd)>=k)  tans=midd,rr=midd-1;
        else    ll=midd+1;
    }
    return tans;
}
inline void change(int l,int r,int w) {
    reset(bl[l]),reset(bl[r]);
    if(bl[l]+1>=bl[r]) {
        for(int i=l;i<=r;i++)   dep[i]+=w; update(bl[l]),update(bl[r]);
        return ;
    }
    for(int i=l;i<=R[bl[l]];i++)    dep[i]+=w; update(bl[l]);
    for(int i=L[bl[r]];i<=r;i++)    dep[i]+=w; update(bl[r]);
    for(int i=bl[l]+1;i<bl[r];i++)  lz[i]+=w,bL[i]+=w,bR[i]+=w;
}
int main() {
    n=read(),m=read(),len=read();
    for(int i=2,x,y;i<=n;i++)   x=read(),y=read(),add(x,i,y);
    Dfs(1,0),build();
    for(int i=1,opt,x,y;i<=m;i++) {
        opt=read(),x=read(),y=read();
        if(opt==1)  printf("%d\n",Kth(dfn[x],low[x],y));
        else    ++tot,change(dfn[x],low[x],y);
        if(i%1000==0)   tot=0,build();
    }
    return 0;
}

祝你们成功