本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-02 19:31:32

怎么没人写字典树？我来补一篇。

发现要使字符串序列字符串序列最小，则对于两个相邻的字符串 $s_i$，$s_j$，$s_{i,k}\le s_{j,k}$，不难发现用字典树倒序插入是好维护的，只需在字典树上每遍历到一个节点，判断是否本节点下一层已存在比当前字符字典序更小的字符即可。

发现难以处理字符串长度不一的情况，这时我们只需标记字符串结尾为一个独立节点，使其小于所有字符，每次额外判断即可。

复杂度 $O(n\times26)$，$n$ 为字符串总长度。

#include<bits\/stdc++.h>
#define endl '\n'
using namespace std;
const int N=5e5+10;
int t[N][30];
int cnt;
string ans[N];
void ins(string s,int xx){
	int u=0;
	int w=-1;
	for(int i=0;i<s.size()-1;i++){
		int x=s[i]-'a'+1;
		bool mx=0;
		for(int j=x-1;j>=0;j--){
			if(t[u][j]){
				mx=1;break; 
			}
		}
		if(mx){
			break;
		}
		if(!t[u][x]){
			t[u][x]=++cnt;
		}
		u=t[u][x];
		w=i;
	}
	t[u][0]=++cnt;
	ans[xx]='#';
	for(int i=0;i<=w;i++){
		ans[xx]+=s[i];
	}
} 
string S[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		for(int i=0;i<s.size();i++){
			s[i]=s[i+1];
		}
		S[i]=s;
	}
	for(int i=n;i>=1;i--){
		ins(S[i],i);
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-16 10:10:01

本篇题解提供一种学数据结构学傻了的数据结构模拟贪心策略解法。又臭又长，不如图论解法与证法。

首先手玩几个样例，发现要使得两个同色球能在操作后放在一个桶中，操作前这两个球必须均位于不同的桶的顶端。

当有两个同色球位于不同桶顶端时，存在以下几种操作：

1\. 两个球，均在桶的上方位置，此时需要有一个空桶才能使得两个球放到同一个桶当中，操作次数为 2。

2\. 两个球，一个在桶的上方位置，一个在桶的下方位置，此时把在一号位置的球放在位于二号位置的球的桶中，操作次数为 1。

3\. 两个球，均在桶的下方位置，此时可以把两个球放到同一个桶当中，然后得到一个空桶，操作次数为 1。

然后考虑并分讨一下是否存在空桶的情况：

• 当存在空桶的时候，优先进行 1 操作。本种情况下，因为存在空桶，所以必定所有桶内都存着两个球，无法进行 2 操作与 3 操作，但是我们可以通过实现 1 操作来创造可以进行 2 操作与 3 操作的情况，使得操作可以继续进行。
• 当不存在空桶的时候，2 操作与 3 操作有只一种能够进行，直接进行即可。本种情况下，如果能进行 2 操作，则说明两个只有一个球的桶中的球的颜色是不同的，无法进行 3 操作，如果能进行 2 操作，则说明两个只有一个球的桶中的球的颜色是相同的，无法进行 2 操作。因此我们从其中取一种可进行的操作进行即可。

但是会存在球都被错开的情况，此时三种操作均无法进行，且一种颜色的球只会在顶端出现一次，如：桶一从上到下存颜色为 $1$，为 $2$ 的球，桶二从上到下存颜色为 $2$，为 $1$ 的球，此时只有存在空桶才能继续操作下去，可以把一个位于桶的上方的球放到空桶当中，然后进行上方的操作，如果还是无法进行，则说明无解，因为我们这种操作本质上是使得两个球满足在 2 操作的情况，如果操作完之后仍不能操作，则无解。

考虑证明：

对于给出初始状态当中下方的一个球，当且仅当上方没有球，并且有另一个在顶端的球时，能进行匹配，对于这种状态，我们可以用 1 操作来创作出一种两个球均在桶的上方的局面，在进行过若干次 2 操作后，由一个 3 操作来结尾，因为每个球只出现两次，所以每种颜色的球只会产生两个桶的对应关系，即本次与下次操作的桶，当我们最后剩余两个同色球在不同桶时，我们会进行一次 3 操作，使得形成一个新的有若干球匹配完成的状态。

排除掉已经匹配完成的球，就到了一个新的初始状态，我们可以继续使用 1 操作来创造出进行 2 操作与 3 操作的局面，直至所有球被匹配完成为止。

而当其产生所有球被错开的情况，相当于我们进行一次把上方的球取出的时候，我们可以借助一个空桶移开一个元素，使得其到达可进行 2 操作的情况，并一直进行 2 操作直至所有球被匹配完成为止，也会形成一个新的有若干球匹配完成的状态。

考虑无解的情况，此时产生了多个 1 操作或对应到了一连串 2 操作上，又或是无法进行 1 操作，而同色球在不同桶中而不是一对一错开的情况，因为第一步的操作（包含两种情况）需要空桶的支持，这两种情况下只有一个空桶无法满足需求，所以无解。

因此每次选择只与进行 1 操作来进行匹配并已 3 操作作为结尾或是选择错开的情况进行匹配有关，并且每次进行完会形成新的子状态，并形成独立问题，因此策略正确。

发现需要维护一种数据结构来维护球有多少在最顶端，支持查询全局最大值，单点修改，并且需要维护不同情况下的策略，这里我采用了线段树。

整体复杂度 $O(n\log n)$。

代码实现丑，较上方描述略为复杂，慎看。

代码

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-18 16:57:01

两种团队的上车方式不同，所以分开处理。

又因为每个团队只会上车一次，所以我们可以暴力地修改每个团队的上车情况，并每次从当前编号最小的团队开始上车。

设置当前车剩下的名额为 $b$，对于下一个团队，如果能拆开，则直接让其上车，需要维护这类团队的编号的最小值，可以使用对顶堆维护。如果不能拆开，则要找到下一个能上车的团队，需要找到这类团队的下一个编号最小的价值小于等于 $b$ 的位置，这个可以用线段树二分，或者平衡树维护。

复杂度 $O(q \log q)$

#include<bits\/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10;
const int INF=1e18;
struct node{
	int l,r,mn;
};
node tr[N*4];
#define ls u<<1
#define rs u<<1|1
inline void up(int u){
	tr[u].mn=min(tr[ls].mn,tr[rs].mn);
}
inline void build(int u,int l,int r){
	tr[u].l=l;tr[u].r=r;
	if(l==r){
		tr[u].mn=INF;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	up(u);
}
inline void cg(int u,int x,int k){
	if(tr[u].l==x&&tr[u].r==x){
		tr[u].mn=k;
		return;
	}
	int mid=(tr[u].l+tr[u].r)>>1;
	if(x<=mid){
		cg(ls,x,k);
	}
	else{
		cg(rs,x,k);
	}
	up(u);
}
inline int find(int u,int x){
	if(tr[u].l==tr[u].r){
		return tr[u].mn<=x?tr[u].l:-1;
	}
	int ans=-1;
	if(tr[ls].mn<=x){
		ans=find(ls,x);
	}
	else if(tr[rs].mn<=x){
		ans=find(rs,x);
	}
	return ans;
}
struct Node{
	int id;
	bool operator<(const Node &x) const{
		return x.id<id;
	}
};
int ww[N];
priority_queue<Node> q,fq;
inline void qcl(){
	while(q.size()&&fq.size()&&q.top().id==fq.top().id){
		q.pop();fq.pop();
	}
}
int lx[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int qq;
	cin>>qq;
	int cnt=0;
	build(1,1,200000);
	for(int i=1;i<=qq;i++){
		int op;cin>>op;
		if(op==1){
			++cnt;
			cin>>ww[cnt]>>lx[cnt];
			if(lx[cnt]==0){
				cg(1,cnt,ww[cnt]);
			}
			else{
				q.push({cnt});
			}
		}
		if(op==2){
			int x;cin>>x;
			if(lx[x]==0){
				cg(1,x,INF);
			}
			else{
				ww[x]=0;
				fq.push({x});
				qcl();
			}
		}
		if(op==3){
			int b;cin>>b;
			vector<int> ansid,ansvl;
			while(b){
				qcl();
				int fdw=find(1,b);
				if(!q.size()&&fdw==-1){
					break;
				}
				else if(!q.size()&&fdw!=-1){
					int id=fdw;
					ansid.push_back(id);
					ansvl.push_back(ww[id]);
					cg(1,id,INF);b-=ww[id];
				}
				else if(q.size()&&fdw==-1){
					int id=q.top().id;
					if(ww[id]<=b){
						ansid.push_back(id);
						ansvl.push_back(ww[id]);
						q.pop();b-=ww[id];
					}
					else{
						ansid.push_back(id);
						ansvl.push_back(b);
						ww[id]-=b;b=0;
					}
				}
				else{
					if(q.top().id>fdw){
						int id=fdw;
						ansid.push_back(id);
						ansvl.push_back(ww[id]);
						cg(1,id,INF);b-=ww[id];	
					}
					else{
						int id=q.top().id;
						if(ww[id]<=b){
							ansid.push_back(id);
							ansvl.push_back(ww[id]);
							q.pop();b-=ww[id];
						}
						else{
							ansid.push_back(id);
							ansvl.push_back(b);
							ww[id]-=b;b=0;
						}
					}
				}
			}
			cout<<ansid.size()<<endl;
			for(int j=0;j<ansid.size();j++){
				cout<<ansid[j]<<" "<<ansvl[j]<<endl;
			}
		}
	}
	
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-19 08:40:27

平衡树实在是太好用了。

对于每个询问，需要遍历整棵树，但是这显然超时，于是考虑把这些询问离线一起处理。

我们把这些询问看做一个集合，每次到一个新的节点，集合的整体大小就会加或者减当前节点 $u$ 的权值 $w[u]$，此时对于 $u$ 的一个子节点 $v$，只有值在 $[l_v,r_v]$ 之间的集合元素可以到达 $v$，剩下的集合元素我们从集合中删去，留在当前节点，当结束完对 $v$ 的遍历后再重新加入集合。统计答案可以通过对集合内的元素打标记解决。

这个容易使用平衡树维护，对于整体大小的加减，我们可以额外维护一个变量表示集合内元素整体增加或减少了多少，整体复杂度 $O(q\log q)$。

#include<bits\/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+10;
struct node{
	int ls,rs,sz,rd,x;
	int id,as,aslz;
}; 
node tr[N];
struct Node{
	int v,l,r;
};
vector<Node> g[N];
int w[N];
int rt,cnt;
inline int nt(int x,int id){
	tr[++cnt]={0,0,1,rand(),x,id,0,0};
	return cnt;
}
inline void up(int u){
	tr[u].sz=tr[tr[u].ls].sz+tr[tr[u].rs].sz+1;;
}
inline void down(int u){
	if(tr[u].aslz){
		if(tr[u].ls){
			tr[tr[u].ls].aslz+=tr[u].aslz;
			tr[tr[u].ls].as+=tr[u].aslz;
		}
		if(tr[u].rs){
			tr[tr[u].rs].aslz+=tr[u].aslz;
			tr[tr[u].rs].as+=tr[u].aslz;
		}
	}
	tr[u].aslz=0;
}
inline void spt(int u,int &x,int &y,int k){
	if(!u){
		x=y=0;
		return;
	}
	down(u);
	if(tr[u].x<=k){
		x=u;
		spt(tr[u].rs,tr[u].rs,y,k);
	}
	else{
		y=u;
		spt(tr[u].ls,x,tr[u].ls,k);
	}
	up(u);
}
inline int mg(int u,int v){
	if(!u||!v){
		return u+v;
	}
	down(u),down(v);
	if(tr[u].rd<tr[v].rd){
		tr[u].rs=mg(tr[u].rs,v);
		up(u);
		return u;
	}
	else{
		tr[v].ls=mg(u,tr[v].ls);
		up(v);
		return v;
	}
}
inline void ins(int x,int id){
	int l,r;
	spt(rt,l,r,x-1);
	rt=mg(l,mg(nt(x,id),r));
}
inline void dfs(int u,int nt,int prs){
	prs+=w[u];
	tr[nt].as++;
	tr[nt].aslz++;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].v;
		int l=g[u][i].l;
		int r=g[u][i].r;
		int L,md,R;
		spt(nt,L,md,l-1-prs);
		spt(md,md,R,r-prs);
		dfs(v,md,prs);
		nt=mg(L,mg(md,R));
	}
}
int ans[N];
inline void dfst(int u){
	down(u);
	if(tr[u].ls){
		dfst(tr[u].ls);
	}
	ans[tr[u].id]=tr[u].as;
	if(tr[u].rs){
		dfst(tr[u].rs);
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n,q;cin>>n>>q;
	for(int i=2;i<=n;i++){
		int p,l,r;cin>>p>>l>>r;
		g[p].push_back({i,l,r});
	}
	for(int i=1;i<=n;i++){
		char x;cin>>x;
		if(x=='+'){
			cin>>w[i];
		}
		else{
			cin>>w[i],w[i]=-w[i];
		}
	}
	for(int i=1;i<=q;i++){
		int x;cin>>x;ins(x,i);
	}
	dfs(1,rt,0);
	dfst(rt);
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}