A 小W与伙伴招募

将方案按价格排序后，显然每次选择都是连续的一段，考虑用线段树维护宝石的数量和价格，支持区间清空和全局加，查询直接在线段树上二分即可。

#include<bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10;
int n,m,c[N],now;
__int128 num[N],sum[N];
struct MT{int a;__int128 b;}w[N];
inline bool cmp(MT a,MT b){if(a.a==b.a)return a.b>b.b;return a.a<b.a;}
struct TREE{
	__int128 num,sum;
	int tag,cl;
}t[N<<2];
inline void update(int p){
	t[p].num=t[ls].num+t[rs].num;
	t[p].sum=t[ls].sum+t[rs].sum;
}
inline void pushdown(int p,int l,int r){
	if(t[p].cl){
		t[ls].num=t[rs].num=t[ls].sum=t[rs].sum=t[ls].tag=t[rs].tag=0;
		t[ls].cl=t[rs].cl=1;
		t[p].cl=0;
	}
	if(t[p].tag){
		int mid=l+r>>1;
		t[ls].num+=t[p].tag*(num[mid]-num[l-1]);
		t[rs].num+=t[p].tag*(num[r]-num[mid]);
		t[ls].sum+=t[p].tag*(sum[mid]-sum[l-1]);
		t[rs].sum+=t[p].tag*(sum[r]-sum[mid]);
		t[ls].tag+=t[p].tag,t[rs].tag+=t[p].tag;
		t[p].tag=0;
	}
}
inline void change(int p,int l,int r,int x){
	if(x>0){
		t[p].num+=(num[r]-num[l-1]);
		t[p].sum+=(sum[r]-sum[l-1]);
		t[p].tag+=x;
	}else{
		t[p].num=t[p].sum=t[p].tag=0;t[p].cl=1;
	}
}
inline int query(int p,int l,int r,int k){
	if(l==r){
		t[p].num-=k,t[p].sum-=w[l].a*k;
		return w[l].a*k;
	}
	pushdown(p,l,r);
	int mid=l+r>>1,res=0;
	if(k<=t[ls].num){
		res=query(ls,l,mid,k);
		update(p);return res;
	}
	res=t[ls].sum+query(rs,mid+1,r,k-t[ls].num);		
	change(ls,l,mid,-1);
	update(p);return res;
}
signed main(){
	freopen("a.in","r",stdin);freopen("a.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
	n=read(),m=read();for(int i=1;i<=n;++i)c[i]=read();
	for(int i=1;i<=m;++i){
		w[i].a=read(),w[i].b=read();
		if(w[i].b==-1)w[i].b=1e12;
	}
	std::sort(w+1,w+m+1,cmp);
	for(int i=1;i<=m;++i){
		num[i]=num[i-1]+w[i].b;
		sum[i]=sum[i-1]+w[i].a*w[i].b;
		if(w[i].b==1e12){m=i;break;}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		change(1,1,m,1);
		ans+=query(1,1,m,c[i]);
	}
	std::cout<<ans<<'\n';
}

B 小W与制胡串谜题

sort (s+1, s+1+n, [](const string &a, const string &b){return (a+b) < (b+a);});

证明偏序关系考虑比较的过程是将 \(a\) 的无限循环与 \(b\) 比较，显然这个满足偏序关系。大力分讨也能证明。

C 小W与屠龙游戏

先考虑不选择子集的博弈。经典的 nim-k 博弈。

nim-k 游戏：有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 个，每人每次可以选择最多 \(k\) 堆，最少 \(1\) 堆石子，每堆石子拿任意个，不能操作者输。

证明：

• \(\text{N}\) 为先手必胜状态，\(\text{P}\) 为先手必败状态，当石子数为 \(0\) 时显然先手必败。
• \(\text{P}\) 的所有后继状态为 \(\text{N}\)：每次最多只能操作 \(k\) 堆，显然一次操作后 \(\sum\) 不可能再次为 \(0\)。
• \(\text{N}\) 必有后继状态为 \(\text{P}\)：从二进制的高位开始，选择所有的 \(1\)，如果不够 \(k\) 个，去下一位选择 \(1\)，这样可以使选的数后面全为 \(1\)，足够将 \(\sum\) 变为零，所以 \(\text{N}\) 必有后继状态 \(\text{P}\)。

考虑加上选择子集的操作。发现每一个只能保留 \(0,1,2\) 个，此时的必败条件就变成了 \(\sum_{i=1}^{d}x_ia_i=0\bmod(3)\)，发现必胜条件为选择的数线性无关，找出价值最大的一组基即可。
考虑使用线性基维护每次遇到一位，如果为空直接插入即可，否则比较已经插入的数 \(y\) 和当前数 \(x\) 的价值，如果当前价值更大，替换已经插入的数，用 \(x\) 消去 \(y\) 的当前位后继续向下比较 \(y\)，否则用 \(y\) 消去 \(x\) 后向下比较 \(x\)。
时间复杂度为 \(\mathcal{O}(n\log^2x)\) 过不了，用二进制维护三进制，时间复杂度为 \(\mathcal{O}(n\log x)\)。

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=5e5+10;
int n,lastans;
struct EMT{
	int p0,p1,p2,v;
	int operator[](int x){return p0>>x&1?0:p1>>x?1:2;}
	EMT operator*(int k){return k==1?EMT{p0,p1,p2,v}:EMT{p0,p2,p1,v};}
	EMT operator-(EMT b){return EMT{p0&b.p0|p1&b.p1|p2&b.p2,p0&b.p2|p1&b.p0|p2&b.p1,p0&b.p1|p1&b.p2|p2&b.p0,v};}
}p[105];
inline void insert(EMT x){
	for(int i=60;~i;--i){
		if(x[i]){
			if(!p[i][i]){p[i]=x,lastans+=x.v;return ;}
			if(x.v>p[i].v)lastans+=x.v-p[i].v,std::swap(p[i],x);
			x=x-p[i]*(x[i]/p[i][i]%3);
		}
	}
}
signed main(){
	freopen("a.in","r",stdin);freopen("a.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
	n=read();
	for(int i=1;i<=n;++i){
		int x=read()^lastans,y=read();
		EMT u={0,0,0,y};
		for(int i=0;i<=60;++i,x>>=1){
			if(x&1)u.p1|=1ll<<i;
			else u.p0|=1ll<<i;
		}
		insert(u);std::cout<<lastans<<'\n';
	}
}

感觉这场 T2 比较弱智，总体上质量不错。