0203题解

~ 2026-2-3 11:36:08

T1 梦幻麻将

source：瞎编的。

想不到吧，这是一个暴力题。

首先说怎么拿前1010个点，就是怎么判断和牌。

我们考虑枚举这一对是谁，剩下的就可以无脑贪心了，从小到大去枚举每一种牌，遇到xxx就无脑xxx，然后x,x+1,x+2。正确性显然：因为假设xxx都需要去匹配x,x+1,x+2，那相当于是三个xxx,x+1,x+1,x+1,x+2,x+2,x+2。

正解之一是这样的（此题显然正解一堆做法）：

我们考虑缺一门的情况下，一共就3232种可能凑成xxx或者x+1,x+2,x+3。一共需要44副，则方案数大约是C324=35960C_{32}^4=35960种。

我们暴力这些可能性，然后就可以O(27)O(27)的算答案了。

单组测试数据复杂度O(106)O(10^6)，不需要剪枝也能过。

#include<bits/stdc++.h>
#define ll long long 
#define double long double
#define maxn 10005
using namespace std;
int vis[28];
int used[28];
int ret;
int cmp(pair<int,int> x,pair<int,int> y) {return x.second>y.second;}
int fangan[10];
void dfs(int turn,int num,int l,int r,int pre)
{
	
	if (turn==6) {ret=min(ret,num); return;}
	if (num>=ret) return;
	if (ret==0) return;
	vector<pair<int,int>> choice;
	if (turn==5) //选将 
	{
		for (int i=1;i<=27;i++)
		if (!(l<=i && i<=r) && used[i]<=2)
		{
			ret=min(ret,num+2-min(vis[i],2));
		}
		return;
	}
	else //选xxx或者x(x+1)(x+2) 
	{
		for (int i=1;i<=27;i++)
		if (!(l<=i && i<=r))
		{
			if (used[i]<=1) choice.push_back({i,min(vis[i],3)});
			if (used[i]<=3 && used[i+1]<=3 && used[i+2]<=3)
			if (i+2<=27 && i+1!=10 && i+2!=10 && i+1!=19 && i+2!=19)
				choice.push_back({-i,min(vis[i],1)+min(vis[i+1],1)+min(vis[i+2],1)});
		}
		for (pair<int,int> tt:choice)
		{
			int id=tt.first,cost=tt.second;
			if (abs(pre)>abs(id)) continue;
			if (id>0) //xxx
			{
				vis[id]-=cost; used[id]+=3;
				fangan[turn]=id;
				dfs(turn+1,num+(3-cost),l,r,id);
				vis[id]+=cost; used[id]-=3;
			}
			else //xx+1x+2
			{
				id=-id;
				int f[3]={0};
				if (vis[id]) f[0]=1,vis[id]--;
				if (vis[id+1]) f[1]=1,vis[id+1]--;
				if (vis[id+2]) f[2]=1,vis[id+2]--;
				used[id]++; used[id+1]++; used[id+2]++;
				fangan[turn]=-id;
				dfs(turn+1,num+(3-cost),l,r,id);
				used[id]--; used[id+1]--; used[id+2]--;
				if (f[0]) vis[id]++;
				if (f[1]) vis[id+1]++;
				if (f[2]) vis[id+2]++;
			}
		}
	}
	return;
}

void work()
{
	memset(vis,0,sizeof(vis));
	ret=14; int x;
	for (int i=1;i<=14;i++) {cin>>x; vis[x]++;} 
	dfs(1,0,1,9,0);  //一共5轮 
	dfs(1,0,10,18,0);
	dfs(1,0,19,27,0);
	cout<<ret<<endl;
}

int main()
{
	int T,cas;
	cin>>T>>cas;
	while (T--) work();
}

T2 猜数游戏

source：瞎编的。

fi,jf_{i,j}表示还有ii的取值区间，此时还剩jj次就要猜的人输的概率是多少。

转移就非常简单了，我们枚举这个人猜的位置即可。

复杂度O(n2)O(n^2)。

#include<bits/stdc++.h>
#define ll long long 
#define double long double
#define maxn 10005
using namespace std;
double f[maxn][105];
int w[maxn];
int main()
{
	int T,n,k; cin>>T>>k; k--; n=10000;
	f[1][0]=1;
	f[2][0]=0.5; f[2][1]=0.5;
	for (int i=3;i<=n;i++)
	{
		//先算f[i][0]的
		f[i][0]=1.0;
		for (int l=0;l<=i-1-l;l++)
		{
			int r=i-1-l;
			double cost=1.0/i+l/(i+0.0)*(f[l][k])+r/(i+0.0)*(f[r][k]);
			if (cost<f[i][0]) f[i][0]=cost,w[i]=l;
		}
		for (int x=1;x<=k;x++)
		{
			int y=x-1;
			f[i][x]=w[i]/(i+0.0)*f[w[i]][y]+(i-1.0-w[i])/i*f[i-1-w[i]][y];
		}
	}
	while (T--)
	{
		cin>>n;
		for (int x=0;x<=k;x++)
			printf("%.6Lf ",1-f[n][x]);
		printf("\n");
	}
}

T3 松鼠游戏

source：好像有原题来着。

70分：

考虑一个简单套路做法：

对于松鼠洞，我们直接搞两棵线段树，一棵向父亲走00代价，一棵向儿子走00代价。然后对于两棵线段树上的对应叶子节点，从第二棵向第一棵连代价为00的边。对于一个松鼠洞，我们直接从第一棵线段树的uu向第二棵线段树的vv连边，代价是ww。

这样就通过2n2n个新节点以及n+m2n+m_2条新边搞定了松鼠洞。

对于松鼠地铁，我们把起点路径，终点路径用树链剖分的形式拆开成lognlogn段。给每条地铁建立一个虚点，然后从起点路径对应区间向虚点连边，从虚点向终点路径连边，这样只需要2logn2logn条边，就维护好了一条松鼠地铁，共2m1logn2m_1logn条新边。如果你没有想到虚点的问题，就只能是log2nlog^2n条边了，我觉得没人想不到吧，所以就没有这个范围的分数。

对于正常的树边可以看成是松鼠地铁来完成。

这样点的个数大约是3n+m13n+m_1，边的个数大约是m1logn+n+m2m_1logn+n+m_2，跑迪杰斯特拉，我不相信还能卡过去满数据！

100分

考虑转化一下Dijkstra的过程：我们每次往堆里面丢一个行为，一个行为，指的是：

（1）id dis，表示把节点idid的最短路与disdis取最小值。

（2）u v dis，表示把从uu到vv的路径上的最短路与disdis取最小值。

（3）u dis，表示把uu子树内每一个点的最短路与disdis取最小值。

那么，比如说我现在求出来55号点的最短路是114114，从这个点出发，有一条地铁，可以去55到11路径上任何一个点，代价是88，我就可以给堆里面丢一个5 1 114+8。

现在就只剩下如何用数据结构维护的问题了：

由于Dijkstra算法的性质，每个位置只要被更新，一定是更新成了最优解，那么：我们只需要用一种数据结构，来查询路径/子树内有没有赋值的点，并把他们更新成disdis即可。这显然线段树+树剖就足够了。

每当一个节点被更新了答案，我们就把它们涉及到的路线更新到堆里面去。

这里涉及一个小问题就是：一个松鼠洞或者一条松鼠地铁，显然只有第一次被拿出来是有用的。那么我们就在一开始把他们丢在线段树的每一个节点上，第一次被拿出来的时候再丢进堆里即可。

感觉这个题是非常综合的一个数据结构题，如果你之前有相当好的数据结构积累，那么上述内容已经足以看懂，如果你之前的数据结构水平不够的话，需要仔细研究代码。

复杂度分析

首先空间复杂度显然是nlognnlogn，只涉及到我们需要把每一条地铁，每一个洞拆分成lognlogn段插入在线段树对应的节点上。

时间复杂度上：我们的堆里一共只丢过所有的边，也就是最坏情况下只有n+m1+m2n+m_1+m_2条边被丢进来过。对于单点的更新，显然复杂度是单loglog的；对于子树的更新，我们用线段树去查询dfsdfs序内没有被改掉的节点即可，显然也是单loglog的；对于路径上的更新，我们需要树剖一下，这个过程只会涉及到若干个从uu到重链头的更新，以及一个非完整重链的更新，我们只需要记一个参数used[u]used[u]表示从uu到其重链头是否曾经更新过，即可保证复杂度均摊只剩下一次线段树上查找。

所以最终的时间复杂度是O(nlogn)O(nlogn)。

#include<bits/stdc++.h>
#define pb push_back
#define ls (now<<1)
#define rs ((now<<1)|1)
#define mid ((l+r)>>1)
#define maxn 500005
#define ll long long
using namespace std;
//树&树剖部分
int n,m1,m2;
int u[maxn],v[maxn],a[maxn],b[maxn],w[maxn],id[maxn];
vector<pair<int,int>> edge[maxn];
int siz[maxn],dep[maxn],FA[maxn],fa[maxn],IN[maxn],OUT[maxn],tot;

//线段树部分 
ll dis[maxn<<2]; //最短路 
basic_string<int> guan[maxn<<2]; //每个位置对应的管道ID

//求dep,siz,fa 
void dfs1(int x,int f)
{
	dep[x]=dep[f]+1; fa[x]=f; siz[x]=1;
	for (pair<int,int> tt:edge[x]) if (tt.first!=f) {dfs1(tt.first,x); siz[x]+=siz[tt.first];}
}
//剖
void dfs2(int x,int f) 
{
	IN[x]=++tot; FA[x]=f; id[tot]=x; //dfs序上第tot个点是x 
	int hs=-1;
	for (pair<int,int> tt:edge[x]) 
	if (tt.first!=fa[x] && (hs==-1 || siz[tt.first]>siz[hs]))
		hs=tt.first;
	if (hs!=-1) dfs2(hs,f);
	for (pair<int,int> tt:edge[x]) 
	if (tt.first!=fa[x] && tt.first!=hs)
		dfs2(tt.first,tt.first);
	OUT[x]=tot;
}

//给区间添加编号为id的边 
void addedge(int now,int l,int r,int L,int R,int id)
{
	if (L<=l && r<=R) {guan[now]+=id; return;} //你子树内都有这个了
	if (L<=mid) addedge(ls,l,mid,L,R,id);
	if (mid+1<=R) addedge(rs,mid+1,r,L,R,id);
	return; 
}

//x到y,id号边 
void ins1(int x,int y,int id)
{
	while (true)
	{
		if (dep[FA[x]]<dep[FA[y]] || (dep[FA[x]]==dep[FA[y]] && dep[x]<dep[y])) swap(x,y);
		//到同一条重链了 
		if (FA[x]==FA[y]) {addedge(1,1,n,IN[y],IN[x],id); return;}
		//否则，x先跳到重链头再说
		addedge(1,1,n,IN[FA[x]],IN[x],id);
		x=fa[FA[x]];
	}
	return;
}  

void init()
{
	cin>>n>>m1>>m2;
	int x,y,z;
	for (int i=1;i<n;i++) {cin>>x>>y>>z; edge[x].pb({y,z}); edge[y].pb({x,z});}
	dfs1(1,1);
	dfs2(1,1);
	for (int i=1;i<=m1;i++)
	{
		cin>>u[i]>>v[i]>>a[i]>>b[i]>>w[i];
		ins1(u[i],v[i],i); //u[i]到v[i],i号边 
	}
	for (int i=m1+1;i<=m1+m2;i++)
	{
		cin>>u[i]>>v[i]>>w[i];
		addedge(1,1,n,IN[u[i]],OUT[u[i]],i);
	}
}

//最短路的部分，不难写，好长，我* 
priority_queue<pair<ll,ll>> Q; //{dis,id} 管道的id 
int vis[maxn]; //记录每条管道是否用过 
void ADD2(int now,int l,int r,int pos,ll dis)
{
	if (l<=pos && pos<=r)
	{
		for (int id:guan[now]) if (!vis[id]) Q.push({-dis-w[id],id}),vis[id]=1;
		guan[now].clear();
	}
	if (l==r) return;
	if (pos<=mid) ADD2(ls,l,mid,pos,dis); else ADD2(rs,mid+1,r,pos,dis);
}

//添加所有x相关的边 
void ADD(int x,ll dis)
{
	//先加直接的边
	for (auto tt:edge[x]) 
	if (tt.first!=fa[x]) Q.push({-dis-tt.second,-tt.first}); 
	//再加相关的管道
	ADD2(1,1,n,IN[x],dis); 
} 

ll ans[maxn]; //记录答案 
//把区间没更新的更新成v 
void modify(int now,int l,int r,int L,int R,ll v)
{
	if (dis[now]>0) return;
	if (l==r) {dis[now]=v; ans[id[l]]=v; ADD(id[l],v); return;}
	if (L<=mid) modify(ls,l,mid,L,R,v);
	if (mid+1<=R) modify(rs,mid+1,r,L,R,v);
	dis[now]=min(dis[ls],dis[rs]);
	return;
}

int used[maxn];
//x到y路径，更新成dis 
void ins2(int x,int y,ll dis)
{
	while (true)
	{
		if (dep[FA[x]]<dep[FA[y]] || (dep[FA[x]]==dep[FA[y]] && dep[x]<dep[y])) swap(x,y);
		//到同一条重链了，更新这一段答案好了 
		if (FA[x]==FA[y]) 
		{
			if (!used[x]) modify(1,1,n,IN[y],IN[x],dis); 
			return;
		}
		//否则，x先跳到重链头再说
		if (!used[x]) modify(1,1,n,IN[FA[x]],IN[x],dis),used[x]=1;
		x=fa[FA[x]];
	}
	return;
}

void work()
{
	modify(1,1,n,IN[1],IN[1],1); //先把1的最短路更新成0+1啦
	while (!Q.empty() && dis[1]==0) //当dis[1]>0就说明更新完了 
	{
		pair<ll,ll> tt=Q.top(); Q.pop();
		ll dis=-tt.first,id=tt.second;
		if (id<0) //我爱单点 
		{
			id=-id;
			modify(1,1,n,IN[id],IN[id],dis);
		}
		else if (id<=m1) //更新a[id],b[id]这一段 
		{
			ins2(a[id],b[id],dis);
		}
		else //更新v[id]的子树，我也喜欢
			modify(1,1,n,IN[v[id]],OUT[v[id]],dis); 
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	init();
	work();
	for (int i=1;i<=n;i++) cout<<ans[i]-1<<" "; cout<<endl;
}

彩蛋

对于维护路径上没被更新的点，我们也可以使用树上的并查集来更新，如果一个点被更新了，就把它连给它父亲，这样重剖这一段的复杂度也就是单loglog了。至于子树的更新，本来用线段树就是单loglog的。

#include<bits/stdc++.h>
#define pb push_back
#define ls (now<<1)
#define rs ((now<<1)|1)
#define mid ((l+r)>>1)
#define maxn 500005
#define ll long long
using namespace std;
//树&树剖部分
int n,m1,m2;
int u[maxn],v[maxn],a[maxn],b[maxn],w[maxn],id[maxn];
vector<pair<int,int>> edge[maxn];
int siz[maxn],dep[maxn],FA[maxn],fa[maxn],IN[maxn],OUT[maxn],tot;

//线段树部分 
ll dis[maxn<<2]; //最短路 
basic_string<int> guan[maxn<<2]; //每个位置对应的管道ID

//求dep,siz,fa 
void dfs1(int x,int f)
{
	dep[x]=dep[f]+1; fa[x]=f; siz[x]=1;
	for (pair<int,int> tt:edge[x]) if (tt.first!=f) {dfs1(tt.first,x); siz[x]+=siz[tt.first];}
}
//剖
void dfs2(int x,int f) 
{
	IN[x]=++tot; FA[x]=f; id[tot]=x; //dfs序上第tot个点是x 
	int hs=-1;
	for (pair<int,int> tt:edge[x]) 
	if (tt.first!=fa[x] && (hs==-1 || siz[tt.first]>siz[hs]))
		hs=tt.first;
	if (hs!=-1) dfs2(hs,f);
	for (pair<int,int> tt:edge[x]) 
	if (tt.first!=fa[x] && tt.first!=hs)
		dfs2(tt.first,tt.first);
	OUT[x]=tot;
}

//给区间添加编号为id的边 
void addedge(int now,int l,int r,int L,int R,int id)
{
	if (L<=l && r<=R) {guan[now]+=id; return;} //你子树内都有这个了
	if (L<=mid) addedge(ls,l,mid,L,R,id);
	if (mid+1<=R) addedge(rs,mid+1,r,L,R,id);
	return; 
}

//x到y,id号边 
void ins1(int x,int y,int id)
{
	while (true)
	{
		if (dep[FA[x]]<dep[FA[y]] || (dep[FA[x]]==dep[FA[y]] && dep[x]<dep[y])) swap(x,y);
		//到同一条重链了 
		if (FA[x]==FA[y]) {addedge(1,1,n,IN[y],IN[x],id); return;}
		//否则，x先跳到重链头再说
		addedge(1,1,n,IN[FA[x]],IN[x],id);
		x=fa[FA[x]];
	}
	return;
}  

void init()
{
	cin>>n>>m1>>m2;
	int x,y,z;
	for (int i=1;i<n;i++) {cin>>x>>y>>z; edge[x].pb({y,z}); edge[y].pb({x,z});}
	dfs1(1,0);
	dfs2(1,1);
	for (int i=1;i<=m1;i++)
	{
		cin>>u[i]>>v[i]>>a[i]>>b[i]>>w[i];
		ins1(u[i],v[i],i); //u[i]到v[i],i号边 
	}
	for (int i=m1+1;i<=m1+m2;i++)
	{
		cin>>u[i]>>v[i]>>w[i];
		addedge(1,1,n,IN[u[i]],OUT[u[i]],i);
	}
}

//最短路的部分，不难写，好长，我* 
priority_queue<pair<ll,ll>> Q; //{dis,id} 管道的id 
int vis[maxn]; //记录每条管道是否用过 
void ADD2(int now,int l,int r,int pos,ll dis)
{
	if (l<=pos && pos<=r)
	{
		for (int id:guan[now]) if (!vis[id]) Q.push({-dis-w[id],id}),vis[id]=1;
		guan[now].clear();
	}
	if (l==r) return;
	if (pos<=mid) ADD2(ls,l,mid,pos,dis); else ADD2(rs,mid+1,r,pos,dis);
}

//添加所有x相关的边 
void ADD(int x,ll dis)
{
	//先加直接的边
	for (auto tt:edge[x]) 
	if (tt.first!=fa[x]) Q.push({-dis-tt.second,-tt.first}); 
	//再加相关的管道
	ADD2(1,1,n,IN[x],dis); 
} 

ll ans[maxn]; //记录答案 
//把区间没更新的更新成v 
void modify(int now,int l,int r,int L,int R,ll v)
{
	if (dis[now]>0) return;
	if (l==r) {dis[now]=v; ans[id[l]]=v; ADD(id[l],v); return;}
	if (L<=mid) modify(ls,l,mid,L,R,v);
	if (mid+1<=R) modify(rs,mid+1,r,L,R,v);
	dis[now]=min(dis[ls],dis[rs]);
	return;
}

int dsu[maxn];
int find(int x) {return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
int used[maxn];
int lca(int x,int y)
{
	while (true)
	{
		if (dep[FA[x]]<dep[FA[y]] || (dep[FA[x]]==dep[FA[y]] && dep[x]<dep[y])) swap(x,y);
		//到同一条重链了，更新这一段答案好了 
		if (FA[x]==FA[y]) 
		{
			return y;
		}
		//否则，x先跳到重链头再说
		x=fa[FA[x]];
	}
	return 0;
}
//x到y路径，更新成dis 
void ins2(int x,int y,int lca,ll dis)
{
	x=find(x); y=find(y);
	while (dep[x]>dep[lca])
	{
		modify(1,1,n,IN[x],IN[x],dis);
		dsu[x]=fa[x];
		x=find(x);
	}
	while (dep[y]>dep[lca])
	{
		modify(1,1,n,IN[y],IN[y],dis);
		dsu[y]=fa[y];
		y=find(y);
	}
	if (dep[x]==dep[lca]) modify(1,1,n,IN[x],IN[x],dis);
	return;
}

int check[maxn];
void work()
{
	for (int i=1;i<=n;i++) dsu[i]=i;
	modify(1,1,n,IN[1],IN[1],1); //先把1的最短路更新成0+1啦
	while (!Q.empty() && dis[1]==0) //当dis[1]>0就说明更新完了 
	{
		pair<ll,ll> tt=Q.top(); Q.pop();
		ll dis=-tt.first,id=tt.second;
		if (id<0) //我爱单点 
		{
			id=-id;
			ins2(id,id,id,dis);
		}
		else if (id<=m1) //更新a[id],b[id]这一段 
		{
			int l=lca(a[id],b[id]);
			ins2(a[id],b[id],l,dis);
		}
		else //更新v[id]的子树，我也喜欢
		{
			if (!check[v[id]])
				modify(1,1,n,IN[v[id]],OUT[v[id]],dis); 
			check[v[id]]=1;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	init();
	work();
	for (int i=1;i<=n;i++) cout<<ans[i]-1<<" "; cout<<endl;
}

T4 买宝石

source：瞎编的。

出这个题真折磨啊。

我们考虑按照价格从小到大来维护每一个商店。

对于一个商店ii，相当于是dfs序上[INi,OUTi][IN_i,OUT_i]这一段，在[ti,n][t_i,n]可以多花ki×wik_i\times w_i的钱了，我们用标记永久化的线段树套线段树可以维护这个信息。

那么我们就可以对所有的询问按照商店价格进行整体二分，对于每一个询问，找到一个最大的ww，使得我们把ww以内能买的都买了，w+1w+1以上一个宝石都没买，此时没有超过总价值。我们记这个为ans1idans1_{id}，同时维护此时一共花了多少钱。

接下来，我们按照时间tt从小到大，依次在[INi,OUTi][IN_i,OUT_i]插入kik_i这个价格到对应的set中。然后枚举所有T=tT=t的询问，去对应的set上查询比ans1idans1_{id}大的最小值，以及小于等于它的最大值。

那么，如果还有钱买一个更贵的宝石，答案就是比ans1idans1_{id}大的最小值；否则答案是小于等于它的最大值。

整个这个算法的时间复杂度瓶颈在于整体二分+线段树套线段树，所以复杂度是O((n+Q)log3(n+Q))O((n+Q)log^3(n+Q))的，但还是比暴力快的应该。

我写了大概11个小时，作为T4不过分。

#include<bits/stdc++.h>
#define ll long long 
#define ls lson[now]
#define rs rson[now]
#define mid ((l+r)>>1) 
#define maxn 100005
using namespace std;
int n,Q;
//id是按价格排序的 
basic_string<int> edge[maxn],id[maxn];
ll k[maxn],w[maxn],t[maxn];
int IN[maxn],OUT[maxn],num=0;
void dfs(int x,int f)
{
	IN[x]=++num;
	for (int y:edge[x]) if (y!=f) dfs(y,x);
	OUT[x]=num;
}
int root,rt[maxn<<8],lson[maxn<<8],rson[maxn<<8],tot;
ll sum[maxn<<8];
ll T[maxn],C[maxn],X[maxn];
int banben=0;

//子树内区间+v 
void ins2(int &now,int l,int r,int L,int R,ll v)
{
	if (!now) now=++tot;
	if (L<=l && r<=R) {sum[now]+=v; return;}
	if (L<=mid) ins2(ls,l,mid,L,R,v);
	if (mid+1<=R) ins2(rs,mid+1,r,L,R,v);
	return;
}
//给区间[L,R],[L2,R2]加v 
void ins(int &now,int l,int r,int L,int R,int L2,int R2,ll v)
{
	if (!now) now=++tot;
	if (L<=l && r<=R) {ins2(rt[now],1,n,L2,R2,v); return;}
	if (L<=mid) ins(ls,l,mid,L,R,L2,R2,v);
	if (mid+1<=R) ins(rs,mid+1,r,L,R,L2,R2,v);
	return;
}

ll query2(int now,int l,int r,int x)
{
	if (!now) return 0;
	ll ret=sum[now];
	if (l==r) return ret;
	if (x<=mid) ret+=query2(ls,l,mid,x); else ret+=query2(rs,mid+1,r,x);
	return ret;
}

//查询{x,y}的值 
ll query(int now,int l,int r,int x,int y)
{
	if (!now) return 0;
	ll ret=0;
	ret+=query2(rt[now],1,n,y); 
	if (l==r) return ret;
	if (x<=mid) ret+=query(ls,l,mid,x,y);
	else ret+=query(rs,mid+1,r,x,y);
	return ret;
}

void add(int price,ll v)
{
	for (int x:id[price]) //插入这一段 
	{
		//从t[x]到n，把东西拉满 
		ins(root,1,n,t[x],n,IN[x],OUT[x],v*k[x]*w[x]);
	}
	return;
}

//答案是多少，以及买了多少钱 
int ans[maxn]; ll buy[maxn];

//我现在需要知道每个点最多到哪里不会炸 
void solve(basic_string<int> Q,int l,int r)
{
	while (banben<mid) {banben++; add(banben,1);}
	while (banben>mid) {add(banben,-1); banben--;}
	basic_string<int> L,R;
	for (int id:Q)
	{
		//第一维是时间，第二维是位置 
		ll ret=query(root,1,n,T[id],IN[X[id]]);
		if (ret<=C[id])
		{
			ans[id]=max(ans[id],mid);
			if (ans[id]==mid) buy[id]=ret;
			R+=id;
		}
		else
		{
			L+=id;
		}
	}	
	if (l<=mid-1 && L.size()) solve(L,l,mid-1);
	if (mid+1<=r && R.size()) solve(R,mid+1,r);
	return; 
}
int zx[maxn],zd[maxn]; 
ll ret[maxn];
//这个是按时间给的 
basic_string<int> ID[maxn],ID2[maxn]; 
set<int> S[maxn<<2];
void modify(int now,int l,int r,int L,int R,int val)
{
	if (L<=l && r<=R) {S[now].insert(val); return;}
	if (L<=mid) modify(now*2,l,mid,L,R,val);
	if (mid+1<=R) modify(now*2+1,mid+1,r,L,R,val);
	return;
}

void cha(int now,int l,int r,int pos,int val,int id)
{
	if (!S[now].empty())
	{
		auto it=S[now].upper_bound(val);
		if (it!=S[now].end()) //查到比你大的了
			zx[id]=min(zx[id],*it);
		//还要查一个比你小的 
		if (it!=S[now].begin())
		{
			it--;
			zd[id]=max(zd[id],*it);
		}
	}
	if (l==r) return;
	if (pos<=mid) cha(now*2,l,mid,pos,val,id);
	else cha(now*2+1,mid+1,r,pos,val,id);
	return;
}

void work()
{
	for (int i=1;i<=n;i++)
	{
		for (int id:ID2[i]) //插入每一个价格 
			modify(1,1,n,IN[id],OUT[id],w[id]);
		for (int id:ID[i]) //对于每一个询问，查询价格以内最大值，价格以上最小值
		{
			zd[id]=0,zx[id]=n+1;
			cha(1,1,n,IN[X[id]],ans[id],id);
			//如果查到了更贵的，且能买得起 
			if (zx[id]!=n+1 && buy[id]+zx[id]<=C[id]) ret[id]=zx[id];
			else ret[id]=zd[id];
		} 
	}
//	for (int i=1;i<=Q;i++) cout<<ans[i]<<" "<<buy[i]<<endl;
	for (int i=1;i<=Q;i++) cout<<ret[i]<<" "; cout<<endl;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n;
	for (int i=1;i<=n;i++) 
	{
		cin>>k[i]>>w[i]>>t[i];
		id[w[i]]+=i; //价格为i 
		ID2[t[i]]+=i;
	}
	int u,v;
	for (int i=1;i<n;i++) {cin>>u>>v; edge[u]+=v; edge[v]+=u;}
	dfs(1,1);
	cin>>Q;
	for (int i=1;i<=Q;i++) {cin>>T[i]>>C[i]>>X[i];}
	for (int i=1;i<=Q;i++) ID[T[i]]+=i; 
	basic_string<int> qq;
	for (int i=1;i<=Q;i++) qq+=i;
	solve(qq,0,n);
	assert(tot<=(maxn<<7));
	//现在我知道到哪里是不炸的，
	//我还需要知道路径上它以内最小是多少，最大是多少。 
	work();
}

我们会审查剪贴板内容，并对发布不合适内容的同学进行相应的处理
  1. Judging Queue
  2. Service Status
  3. Legacy mode
  4. Theme
  2. 蜀ICP备2022005482号-4
  3. Worker 0, 13ms
  4. Powered by Hydro v5.0.0-beta.15 Community