Loj 6046 爷

Posted on | Views:

分块 + 定期重构.

把树的 dfs 序找出来,问题就变成了区间加,区间询问第 $k$ 小.

如果直接分块 + 询问二分 + 块内二分,复杂度是根号带两只 $\log$ ,跑不过去.

唯一还能利用的性质就是 $len\le 10$ .

如果一个块内最大值和最小值相差很小,就可以记录个数的前缀和,少掉一只 $\log$ .

于是可以给块大小和元素极差分别设一个阈值,当其中一者超过阈值时,就立即新开一个块.

块有分裂的操作,为了方便,可以用一个链表把所有块串起来,方便遍历.

还有一个优化,当我们对边角部分暴力修改时,原来的一块可能会因为极差超过阈值而裂成几个小块.

而这些小块是可能与前后的块进行合并的.

如果每次都检查能否合并,效果并不会很好,我们可以定期将整个数列的分块重构一下.

阈值和重构的周期可能需要照抄别人的参数手动调一下参.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10,D=3000,S=400,T=1000,inf=1e9;
// max-min<=D,siz<=S,ReBuild after T operations.
int n,m,len,ecnt=0,head[MAXN],to[MAXN],nx[MAXN],eval[MAXN];
void addedge(int u,int v,int w)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	eval[ecnt]=w;
	head[u]=ecnt;
}
int in[MAXN],out[MAXN],idx=0,a[MAXN];
void dfs(int u,int dist)
{
	in[u]=++idx,a[idx]=dist;
	for(int i=head[u]; i; i=nx[i])
		dfs(to[i],dist+eval[i]);
	out[u]=idx;
}
int bel[MAXN],cnt=0;
int lp[MAXN],rp[MAXN],nxt[MAXN],tag[MAXN],mx[MAXN],mi[MAXN];
vector<int> sum[MAXN];
void pushdown(int x)
{
	if(tag[x])
	{
		for(int i=lp[x]; i<=rp[x]; ++i)
			a[i]+=tag[x];
		tag[x]=0;
	}
}
void ReBuild()
{
	for(int i=1; i<=cnt; ++i)
		pushdown(i);
	cnt=0;
	int pos=1;
	mx[cnt+1]=mi[cnt+1]=a[1];
	for(int i=2; i<=n+1; ++i)
	{
		if(i>n || i-pos+1>S || mx[cnt+1]-a[i]>D || a[i]-mi[cnt+1]>D)
		{
			++cnt;
			lp[cnt]=pos,rp[cnt]=i-1,nxt[cnt]=cnt+1,tag[cnt]=0;
			sum[cnt].clear();
			sum[cnt].resize(mx[cnt]-mi[cnt]+1);
			for(int j=lp[cnt]; j<=rp[cnt]; ++j)
				++sum[cnt][a[j]-mi[cnt]],bel[j]=cnt;
			for(int j=1; j<=mx[cnt]-mi[cnt]; ++j)
				sum[cnt][j]+=sum[cnt][j-1];
			mx[cnt+1]=mi[cnt+1]=a[i],pos=i;
		}
		else
		{
			mx[cnt+1]=max(mx[cnt+1],a[i]);
			mi[cnt+1]=min(mi[cnt+1],a[i]);
		}
	}
}
void bf(int L,int R,int c)
{
	pushdown(bel[L]);
	for(int i=L; i<=R; ++i)
		a[i]+=c;
	int tmp=nxt[bel[L]],pos=lp[bel[L]],cur=bel[L];
	int st=lp[bel[L]],ed=rp[bel[L]];
	mx[cur]=mi[cur]=a[st];
	for(int i=st+1; i<=ed+1; ++i)
	{
		if(i>ed || i-pos+1>S || mx[cur]-a[i]>D || a[i]-mi[cur]>D)
		{
			lp[cur]=pos,rp[cur]=i-1,tag[cur]=0;
			if(i<=ed)
				nxt[cur]=++cnt;
			else
				nxt[cur]=tmp;
			sum[cur].clear();
			sum[cur].resize(mx[cur]-mi[cur]+1);
			for(int j=lp[cur]; j<=rp[cur]; ++j)
				++sum[cur][a[j]-mi[cur]],bel[j]=cur;
			for(int j=1; j<=mx[cur]-mi[cur]; ++j)
				sum[cur][j]+=sum[cur][j-1];
			if(i<=ed)
			{
				cur=cnt;
				mx[cur]=mi[cur]=a[i];
				pos=i;
			}
		}
		else
		{
			mx[cur]=max(mx[cur],a[i]);
			mi[cur]=min(mi[cur],a[i]);
		}
	}
}
void upd(int L,int R,int c)
{
	if(bel[L]==bel[R])
		bf(L,R,c);
	else
	{
		int st=rp[bel[L]]+1;
		bf(L,rp[bel[L]],c);
		for(int i=bel[st]; i!=bel[R]; i=nxt[i])
			tag[i]+=c,mi[i]+=c,mx[i]+=c;
		bf(lp[bel[R]],R,c);
	}
}
int calc(int L,int R,int c)
{
	pushdown(bel[L]);
	int res=0;
	for(int i=L; i<=R; ++i)
		res+=(a[i]<=c);
	return res;
}
int query(int L,int R,int c) // num of a[i]<=c in [L,R]
{
	int ans=0;
	if(bel[L]==bel[R])
		ans=calc(L,R,c);
	else
	{
		ans+=calc(L,rp[bel[L]],c);
		for(int i=nxt[bel[L]]; i!=bel[R]; i=nxt[i])
			if(c>=mi[i])
			{
				if(c<mx[i])
					ans+=sum[i][c-mi[i]];
				else
					ans+=sum[i][mx[i]-mi[i]];
			}
		ans+=calc(lp[bel[R]],R,c);
	}
	return ans;
}
int solve(int L,int R,int k)
{
	if(R-L+1<k)
		return -1;
	int res=0,l=0,r=(n-1+m)*len;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(query(L,R,mid)>=k)
			res=mid,r=mid-1;
		else
			l=mid+1;
	}
	return res;
}
int main()
{
	n=read(),m=read(),len=read();
	for(int i=2; i<=n; ++i)
	{
		int f=read(),w=read();
		addedge(f,i,w);
	}
	dfs(1,0);
	ReBuild();
	for(int i=1; i<=m; ++i)
	{
		int op=read(),x=read(),k=read();
		if(op==1)
			printf("%d\n",solve(in[x],out[x],k));
		else
			upd(in[x],out[x],k);
		if(i%T==0)
			ReBuild();
	}
	return 0;
}