自动搬运

查看原文

来自洛谷，原作者为

	daniel14311531 文化课菜逼

搬运于2025-08-24 21:51:54，当前版本为作者最后更新于2018-12-03 20:56:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

此题 1e5，分块逃不过。

尝试这样分块：

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

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

祝你们成功