\(\texttt{A.LuoTianyi and the Show}\)

如果没有第三种，是简单的。
否则，首先所有不同的第三种必定会坐上，通过观察样例可以发现，我们可以找个位置(或者边界)，左边全是第一类，右边全是第二类。
复杂度 \(O(n)\)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int n,m,c[N];
int l[N],r[N],sum[N];
void solve()
{
	scanf("%d %d",&n,&m);
	int A=0,B=0;
	for(int i=1;i<=m;i++)c[i]=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		if(x==-1)B++;
		else if(x==-2)A++;
		else c[x]++;
	}
	for(int i=1;i<=m;i++)sum[i]=sum[i-1]+(c[i]>0);
	int ans=0,res=0;
	for(int i=1;i<=m;i++)
	if(c[i])ans=max(ans,min(i-1-sum[i-1],B)+min(m-i-sum[m]+sum[i],A)+sum[m]);
	for(int i=m;i>=1;i--)
	{
		if(c[i])res++;
		else if(B)
		{
			B--;
			res++;
		}
	}
	ans=max(ans,res);
	res=0;
	for(int i=1;i<=m;i++)
	{
		if(c[i])res++;
		else if(A)
		{
			A--;
			res++;
		}
	}
	ans=max(ans,res);
	printf("%d\n",ans);
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
} 

\(\texttt{B.LuoTianyi and the Floating Islands (Easy/Hard Version)}\)

一个写起来非常简单的思路。
首先答案一定是一个联通块，那么点数 = 边数 + 1 。
那么我们求出合法的边数再加一就好了。
如果 \(k\) 是奇数，边数为 0.
否则，对于一条边，只有两边各有 \(\frac{k}{2}\) 时合法，组合数算算就好了。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
const int mod = 1e9+7;
int fac[N],ifac[N];
int Pow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
} 
void init(int n)
{
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
	ifac[n]=Pow(fac[n],mod-2);
	for(int i=n-1;i>=0;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
int binom(int n,int m)
{
	if(n<0||m<0||n<m)return 0;
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
struct edge
{
	int y,next;
}e[2*N];
int link[N],t=0;
void add(int x,int y)
{
	e[++t].y=y;
	e[t].next=link[x];
	link[x]=t;
}
int siz[N];
int n,k;
int ans=1;
void dfs(int x,int pre)
{
	siz[x]=1;
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(y==pre)continue;
		dfs(y,x);
		siz[x]+=siz[y];
		ans=(ans+1ll*binom(n-siz[y],k/2)*binom(siz[y],k/2)%mod*Pow(binom(n,k),mod-2)%mod)%mod;
	}
}
int main()
{
	cin>>n>>k;
	if(k%2==1)
	{
		cout<<1;
		return 0;
	}
	for(int i=2;i<=n;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		add(x,y);
		add(y,x);
	}
	init(n);
	dfs(1,0);
	cout<<ans;
	return 0;
}

\(\texttt{C.LuoTianyi and XOR-Tree}\)

设 \(f_{x,i}\) 为，\(x\) 的子树内，所有叶子到根上的点的异或和都是 \(i\)，最小的操作次数。

那么先不考虑 \(x\)， \(f_{x,i}=\sum_{y\in son_x}f_{y,i}\)
然后，因为是异或，所以我们可以花费 1 的代价变成任意的数，\(f_{x,i}=\min(f_{x,i},f_{y,i}+1)\)
对于叶节点 \(x\)，如果最初到根的异或和为 \(w_x\)，那么 \(f_{x,w_x}=0,f_{x,i\neq w_x}=1\) 。
我们用线段树合并维护，需要支持合并和取 \(\min\) 。

\(\texttt{D.LuoTianyi and the Function}\)

非常套路题。
询问是一个平面上的矩形，可以差分成四个右下矩形。
右下矩形等价于一个区间的所有子区间的\(g(l,r)\)和。
套路地从右到左扫描线，维护以当前点为左端点的区间的 \(g\)，那么对于 \(i\)，他只会影响它下一次出现位置之前的位置，让他们变成 \(i\)，即把 \([i,nxt_i-1]\) 变成 \(i\).
询问就是历史版本和。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+9;
struct Query
{
	int l,r,id,opt;
};
vector<Query> Q[N];
int n,q;
typedef long long LL;
LL ans[N];
int a[N],nxt[N],lst[N];
struct Info
{
	int cov;
	LL his;
	int pre;
	int len;
	LL tag;
	LL sum;
}tr[N*4];
void pushup(int k)
{
	tr[k].his=tr[k<<1].his+tr[k<<1|1].his;
	tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
}
Info Merge(Info A,Info B)
{
	Info C;
	LL v=A.cov;
	if(v==-1)v=0;
	C.his=A.his+1ll*(1ll*v*B.pre+B.tag)*A.len;
	if(A.cov==-1)C.his+=A.sum*B.pre;
	C.len=A.len;
	if(B.cov!=-1)C.cov=B.cov;
	else C.cov=A.cov;
	if(A.cov!=-1)C.pre=A.pre;
	else C.pre=A.pre+B.pre;
	C.tag=A.tag+1ll*v*B.pre+B.tag;
	if(B.cov==-1)C.sum=A.sum;
	else C.sum=1ll*B.cov*A.len;
	return C;
}
void pushdown(int k)
{
	if(tr[k].cov!=-1||tr[k].pre!=0||tr[k].tag!=0)
	{
		tr[k<<1]=Merge(tr[k<<1],tr[k]);
		tr[k<<1|1]=Merge(tr[k<<1|1],tr[k]);
		tr[k].cov=-1;
		tr[k].pre=0;
		tr[k].tag=0;
	}
}
void build(int k,int l,int r)
{
	tr[k]=(Info){-1,0,0,r-l+1,0,0};
	if(l==r)return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
void modify(int k,int l,int r,int L,int R,int v)
{
	if(L<=l&&r<=R)
	{
		tr[k]=Merge(tr[k],(Info){v,0,0,0,0,0});
		return;
	}
	pushdown(k);
	int mid=(l+r)>>1;
	if(L<=mid)modify(k<<1,l,mid,L,R,v);
	if(R>mid)modify(k<<1|1,mid+1,r,L,R,v);
	pushup(k);
}
LL ask(int k,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)return tr[k].his;
	pushdown(k);
	int mid=(l+r)>>1;
	LL res=0;
	if(L<=mid)res+=ask(k<<1,l,mid,L,R);
	if(R>mid)res+=ask(k<<1|1,mid+1,r,L,R);
	return res;
} 
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)lst[i]=n+1;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=n;i>=1;i--)
	{
		nxt[i]=lst[a[i]];
		lst[a[i]]=i;
	} 
	build(1,1,n);
	for(int i=1;i<=q;i++)
	{
		int l,r,x,y;
		scanf("%d %d %d %d",&l,&r,&x,&y);
		if(l<=y)Q[l].push_back((Query){l,y,i,1});
		if(l<=x-1)Q[l].push_back((Query){l,x-1,i,-1});
		if(r+1<=y)Q[r+1].push_back((Query){r+1,y,i,-1});
		if(r+1<=x-1)Q[r+1].push_back((Query){r+1,x-1,i,1});
	}
	for(int i=n;i>=1;i--)
	{
		int j=nxt[i];
		modify(1,1,n,i,j-1,i);
		tr[1]=Merge(tr[1],(Info){-1,0,1,0,0,0});
		for(auto U:Q[i])
		ans[U.id]+=ask(1,1,n,U.l,U.r)*U.opt; 
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}

\(\texttt{E.LuoTianyi and Cartridge}\)

枚举 \(v=\min(a,c)\),那么只有 \(a\geq v\)的点和 \(b\geq v\)的点可以选，我们称这些点为合法点。
对于 \(V\) 个合法点和 \(V-1\) 条合法边，如果某一条边只有一边有合法点，显然不合法，否则一定合法。

\(\texttt{proof:}\)
按任意顺序加边，每条边两边一定有一对不联通的点，否则说明所有点都已联通，但是边数显然不够。

把不合法的边以及某一边没有合法点的边缩起来，也就是说现在一个点代表了一堆点。
如果某个叶子上没有合法点，我们就删掉。

我们可以发现，叶子上的合法点一定会至少选一个，否则选上这个点和其父亲的边以及这个合法点，一定不劣。
且，我们选完这些叶子上的点之后，所有的边可以任意选了。
因此，设剩下的点数为 \(V\)，边数为 \(E\)，那么最终最多选 \(S=min(E,V-1)+1\)个点，且一定可以选这么多点。

那么最终选的点就是，每个叶子里权值最大的点(假设有 \(F\) 个)，然后剩下点里面再选 \(S_F\) 个权值最大的点，然后选 \(S-1\) 个权值最大的边。

从小到大依次删边，用权值线段树维护点和边，然后启发式合并维护每个点里的权值，以及有哪些出边。

复杂度 \(O(n\log n)\)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5+7;
struct SegMent
{
	int cnt[N*4];
	LL sum[N*4];
	void modify(int k,int l,int r,int x,int c)
	{
		cnt[k]+=c;
		sum[k]+=1ll*x*c;
		if(l==r)return;
		int mid=(l+r)>>1;
		if(x<=mid)modify(k<<1,l,mid,x,c);
		else modify(k<<1|1,mid+1,r,x,c);
	}
	LL ask(int k,int l,int r,int c)
	{
		if(l==r)return 1ll*c*l;
		int mid=(l+r)>>1;
		if(cnt[k<<1|1]>=c)return ask(k<<1|1,mid+1,r,c);
		return ask(k<<1,l,mid,c-cnt[k<<1|1])+sum[k<<1|1];
	 } 
}B,D;
int n;
const int W = 2e5;
LL ans=0;
int fa[N];
int Find(int x)
{
	if(x==fa[x])return x;
	return fa[x]=Find(fa[x]);
}
#define PII pair<int,int>
#define X(x) x.first
#define Y(x) x.second
#define mk(x,y) make_pair(x,y)
set<PII> G[N];
multiset<LL> S[N];
bool threw[N];
int a[N],b[N],c[N],d[N],up[N],vp[N];
void del(int o,int x,int y)
{
	G[x].erase(G[x].lower_bound(mk(o,0)));
	G[y].erase(G[y].lower_bound(mk(o,0)));
	threw[o]=1;
	D.modify(1,1,W,d[o],-1);
}
PII P[N];
PII E[N];
LL leaf=0;
void calc(int x,int c)
{
	if(G[x].size()!=1)return;
	LL v=(*--S[x].end());
	leaf+=v*c;
	B.modify(1,1,W,v,-c);
}
queue<int> q;
void DelE(int o)
{
	int x=Find(up[o]),y=Find(vp[o]);
	if(threw[o])return;
	calc(x,-1);calc(y,-1);del(o,x,y);
	if(S[x].size()<S[y].size())swap(S[x],S[y]);
	if(G[x].size()<G[y].size())swap(G[x],G[y]);
	for(auto u:S[y])S[x].insert(u);
	for(auto u:G[y])G[x].insert(u);
	fa[y]=x;calc(x,1);
}
void DelP(int o)
{
	int f=Find(o);
	calc(f,-1);
	S[f].erase(S[f].find(b[o]));
	B.modify(1,1,W,b[o],-1);
	if(S[f].empty()&&G[f].size()==1)
	{
		q.push(f);
		int c=0;
		while(!q.empty())
		{
			int x=q.front();
			q.pop();
			if(G[x].empty())continue;
			auto it=G[x].begin();
			int id=it->first,y=Find(it->second);
			del(id,x,y);
			if(G[y].size()==1)
			{
				if(S[y].empty())q.push(y);
				else calc(y,1);
			}
		}
	}
	else calc(f,1);
}
LL get(int p)
{
	int E=D.cnt[1],V=n-p+1;
	int m=min(E,V-1),lf=V-B.cnt[1];
	return leaf+D.ask(1,1,W,m)+B.ask(1,1,W,m+1-lf);
}
int main()
{
	cin>>n;
	int Mx=0;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		S[i].insert(b[i]);
		B.modify(1,1,W,b[i],1);
		P[i]=mk(a[i],i);
		Mx=max(Mx,a[i]);
		Mx=max(Mx,b[i]);
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d %d %d %d",&x,&y,&c[i],&d[i]);
		up[i]=x;
		vp[i]=y;
		G[x].insert(mk(i,y));
		G[y].insert(mk(i,x));
		D.modify(1,1,W,d[i],1);
		E[i]=mk(c[i],i);
		Mx=max(Mx,c[i]);
		Mx=max(Mx,d[i]);
	}
	for(int i=1;i<=n;i++)calc(i,1); 
	sort(P+1,P+n+1);sort(E+1,E+n);
	int p=1,e=1;
	LL val=get(p);
	for(int v=1;v<=Mx;v++)
	{
		int lp=p,le=e;
		while(e<n&&E[e].first<v) DelE(E[e++].second);
		while(p<=n&&P[p].first<v)DelP(P[p++].second);
		if(p>n)break;
		if(p>lp||e>le)val=get(p);
		ans=max(ans,1ll*val*v);
	}
	cout<<ans;
	return 0;
}