悲报：今年好像没有统一题解了。

H Magic Transport

首先一个显然的结论：给定若干带体积的物品，有限容积选择的物品数最大化，显然应当按照体积递增选择若干件，证明考虑交换法和反证法。

我们维护的东西就变成了：给定一个可重集，支持查询上面那个东西和插入元素，上面那个东西转化成查询总和不超过某值的体积前若干个元素数量总和。

查询容易用线段树上二分/平衡树上二分处理，这里我考场直接用 FHQ-Treap，注意到上面那个东西所依赖的信息是容易合并的，查询直接分裂子树之后查询根结点信息即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+11;
mt19937 gen;
struct nd
{
	int ch[2],sz;ll r,val,sv;
}cts[N];int cnt;
int nnd(ll val)
{
	++cnt;
	cts[cnt]={0,0,1,gen(),val,val};
	return cnt;
}
void up(int x)
{
	cts[x].sz=1,cts[x].sv=cts[x].val;
	if(cts[x].ch[0]) cts[x].sz+=cts[cts[x].ch[0]].sz,cts[x].sv+=cts[cts[x].ch[0]].sv;
	if(cts[x].ch[1]) cts[x].sz+=cts[cts[x].ch[1]].sz,cts[x].sv+=cts[cts[x].ch[1]].sv;
}
int merge(int x,int y)
{
	if(!x||!y) return x?x:y;
	if(cts[x].r<cts[y].r)
	{
		cts[x].ch[1]=merge(cts[x].ch[1],y);up(x);return x;
	}
	else
	{
		cts[y].ch[0]=merge(x,cts[y].ch[0]);up(y);return y;
	}
}
using ip=pair<int,int>;
ip split_v(int x,ll k)
{
	if(!x) return {0,0};ll lsv=cts[cts[x].ch[0]].sv,nv=cts[x].val;
	if(lsv+nv<=k)
	{
		ip u=split_v(cts[x].ch[1],k-lsv-nv);
		cts[x].ch[1]=u.first,up(x);u.first=x;return u;
	}
	else
	{
		ip u=split_v(cts[x].ch[0],k);
		cts[x].ch[0]=u.second,up(x);u.second=x;return u;
	}
}
ip split(int x,ll k)
{
	if(!x) return {0,0};
	if(cts[x].val<=k)
	{
		ip u=split(cts[x].ch[1],k);
		cts[x].ch[1]=u.first,up(x);u.first=x;return u;
	}
	else
	{
		ip u=split(cts[x].ch[0],k);
		cts[x].ch[0]=u.second,up(x);u.second=x;return u;
	}
}
void insert(int &x,ll val)
{
	int nxd=nnd(val);
	ip u1=split(x,val-1);
	x=merge(merge(u1.first,nxd),u1.second);
}
void clear()
{
	for(int i=1;i<=cnt;++i) cts[i]={0,0,0,0,0,0};
	cnt=0;
}
int n;ll m;
int a[N];int rt;
int qans(int xx)
{
	if(!xx) return 0;
	return cts[xx].sz;
}
void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i)
	{
		ll pans=i-1;
		ll pm=m-a[i];
		ip u1=split_v(rt,pm);
		pans-=qans(u1.first);
		rt=merge(u1.first,u1.second);
		cout<<pans<<' ';
		insert(rt,a[i]);
	}
	clear();rt=0;cout<<endl;
}
int main()
{
	int t;cin>>t;
	while(t--) solve();
	return 0; 
}

B Ternary Tree

先考虑把给出的 BFS 序标号转成 DFS 序，这样方便处理子树删除操作。

由于本题给出的是完全三叉树，且为儿子标号可递推的堆式存储，因此我们考虑直接使用计算结点排名的方式计算 DFN 序：

首先，所有子树都是完全三叉树，根据给出的公式，高度为 的三叉树的结点数为 ，可以直接计算；计算结点的深度时可以根据标号对 取余的余数分类算出是左、中或右儿子，转为中儿子标号后除以 来爬父亲同时累加深度。因此，求一次深度后，可以在求排名的过程中动态维护当前结点深度来计算子树大小（如果每次暴力爬父亲重算， 的时间复杂度会 TLE）。这样，我们很容易求出一个结点的子树对应的 DFN 序区间。

之后，由于树的结点数最大可达 数量级，显然不能直接维护每个结点。考虑使用颜色段均摊维护DFN序列，即使用std::set维护若干DFN序的不交区间，由于一次操作最多新增 个区间，而删除操作的操作数最大为所有曾经存在过的区间数之和，因此总操作数为 级别，均摊单次操作时间复杂度 。

时间复杂度 ，感觉细节有点多。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
struct node
{
	ll l,r;
	node():l(0),r(0) {}
	node(ll pos):l(pos),r(pos) {}
	node(ll l,ll r):l(l),r(r) {}
	bool operator <(const node& a) const
	{
		return r<a.r;
	}
};
set<node> odt;
using sit=set<node>::iterator;
ll operate(ll l,ll r)
{
	assert(l<=r);
	if(!odt.size()) return 0;
	sit tr=odt.lower_bound(r),tl=odt.lower_bound(l);
	if(tl==tr)
	{
		if(tr==odt.end()) return 0;
		else if(tr->l>r) return 0;
		ll pl=tl->l,pr=tr->r;
		if(l<=pl&&pr<=r)
		{
			ll ans=pr-pl+1;
			odt.erase(tl);
			return ans;
		}
		ll ans=min(pr,r)-max(l,pl)+1;
		odt.erase(tl);
		if(pl<=l-1) odt.insert(node(pl,l-1));
		if(r+1<=pr) odt.insert(node(r+1,pr));
		return ans;
	}
	else if(tr==odt.end())
	{
		--tr;if(tl==tr)
		{
			if(tr==odt.end()) return 0;
			else if(tr->l>r) return 0;
			ll pl=tl->l,pr=tr->r;
			if(l<=pl&&pr<=r)
			{
				ll ans=pr-pl+1;
				odt.erase(tl);
				return ans;
			}
			ll ans=min(pr,r)-max(l,pl)+1;
			odt.erase(tl);
			if(pl<=l-1) odt.insert(node(pl,l-1));
			if(r+1<=pr) odt.insert(node(r+1,pr));
			return ans;
		}
	}
	else if(tr->l>r)
	{
		assert(tr!=odt.begin());
		--tr;
	}
	if(tr->r>r)
	{
		assert(tr!=odt.end());
		ll wl=tr->l,wr=tr->r;
		odt.erase(tr);
		odt.insert(node(wl,r));
		tr=odt.insert(node(r+1,wr)).first;
	}
	if(tl->l<l)
	{
		ll wl=tl->l,wr=tl->r;
		odt.erase(tl);
		odt.insert(node(wl,l-1));
		tl=odt.insert(node(l,wr)).first;
	}
	tr=odt.lower_bound(node(r));
	if(tr!=odt.end()&&tr->r<=r) ++tr;
	ll ans=0;
	for(auto xxx=tl;xxx!=tr;++xxx)
	{
		ans+=xxx->r-xxx->l+1;
	}
	odt.erase(tl,tr);
	return ans;
}
ll n,q;
map<ll,ll> hig;
ll get_depth(ll x)
{
	ll ans=0;
	while(x)
	{
		if(x%3==2) ++x;
		else if(x%3==1) --x;
		x/=3;++ans;
	}
	return ans;
}
ll trp[30];
ll dfn_ord(ll x)
{
	ll ans=0;ll dep=get_depth(x);
	while(x)
	{
		++ans;
		if(x==1) break; 
		if(x%3ll==2ll)
		{
			ll px=x+1ll;x=px/3ll;--dep;
		}
		else if(x%3ll==0)
		{
			ll pth=n-dep+1ll;
			ans+=(trp[pth]-1ll)/2ll;
			x/=3ll;--dep;
		}
		else if(x%3ll==1)
		{
			x-=1ll;
			ll pth=n-dep+1;
			ans+=(trp[pth]-1);
			x/=3ll;--dep;
		}
	}
	return ans;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin>>n>>q;
	trp[0]=1;
	for(int i=1;i<=27;++i) trp[i]=trp[i-1]*3ll,hig[trp[i]]=i;
	odt.insert(node(1ll,(trp[n]-1ll)/2ll));ll ans=(trp[n]-1ll)/2ll;
	for(int i=1;i<=q;++i)
	{
		ll u;cin>>u;ll siz=(trp[1ll*n-get_depth(u)+1ll]-1ll)/2ll;
		u=dfn_ord(u);
		ans-=operate(u,u+siz-1ll);
		cout<<ans<<endl;
	}
	return 0;
}