E
考虑分开处理，我们枚举中间的 E，然后再枚举前面的 M 和后面的 X 分别是什么。
这样的话，我们会发现，对于相同的 \((A_i,A_j,A_k)\)，其贡献是相同的。我们可以记录前缀和后缀中，\(A_i\) 为某个值的 M 和 X 数量，然后计算个数，单独处理 MEX 即可。
ll n,pre[200005][3],suf[200005][3],a[200005];
string s;
inline int mex(int x,int y,int z){
rd(i,4)if(x!=i&&y!=i&&z!=i)return i;
return 3;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
rp(i,n)cin>>a[i];
cin>>s;s='$'+s;
rep(i,1,n){
rd(j,3)pre[i][j]=pre[i-1][j];
if(s[i]=='M')pre[i][a[i]]++;
}per(i,1,n){
rd(j,3)suf[i][j]=suf[i+1][j];
if(s[i]=='X')suf[i][a[i]]++;
}ll ans=0;
rep(i,2,n-1)if(s[i]=='E'){
rd(x,3)rd(y,3){
ans+=pre[i-1][x]*suf[i+1][y]*mex(a[i],x,y);
}
}cout<<ans<<endl;
return 0;
}//Crayan_r
F
考虑我们其实就是要最大化使用的折扣总和。先把所有的答案都加入，然后减去所使用的所有折扣即可。
考虑以下贪心策略：按照 \(P\) 从低到高，每次加入所有 \(L\) 满足要求的折扣，然后选择 \(D\) 最大的一个。
考虑证明：如果当前的不选最大的，后面不一定还能选最大的。当前的选了最大的，其他的后面也可以选。也就是交换选择顺序一定不会更优。所以先贪心选最大的即可。
ll n,m,p[200005],l[200005],d[200005],to[200005],ans=0;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
rp(i,n)cin>>p[i];
rp(i,n)ans+=p[i];
sort(p+1,p+1+n);
rp(i,m)cin>>l[i];
rp(i,m)cin>>d[i];
rp(i,m)to[i]=i;
sort(to+1,to+1+m,[](int x,int y){
return l[x]<l[y];
});
ll cur=0;
set<pll>se;
rp(i,n){
while(cur<m&&l[to[cur+1]]<=p[i]){
cur++;se.insert({-d[to[cur]],cur});
}
if(se.size()){
ll x=se.begin()->first;
se.erase(se.begin());
ans+=x;
}
}cout<<ans<<endl;
return 0;
}//Crayan_r
G
我们发现，加入操作是很好处理的，我们可以先在 TRIE 上找到当前数和前面插入的数的最小异或值，然后将其加入。
但是，带有删除操作就不好处理。我们考虑离线后线段树分治，这样就不需要删除，只需要撤销。而撤销因为可以回滚答案，所以只要在 TRIE 做修改而不必对答案做修改。
这样，线段树分治的每个子任务是 TRIE 上插入、删除、查询，复杂度 \(O(n\log n\log a)\)。
int trie[9000005][2],sum[9000005],cnt=1;
int q,c[300005],x[300005];
inline int ins(int x){
int res=0,cyr=1;
per(i,0,30){
int p=(x>>i&1);
if(sum[trie[cyr][p]])cyr=trie[cyr][p];
else cyr=trie[cyr][p^1],res|=(1<<i);
}cyr=1;sum[1]++;
per(i,0,30){
int p=(x>>i&1);
if(!trie[cyr][p])trie[cyr][p]=++cnt;
cyr=trie[cyr][p],sum[cyr]++;
}return res;
}
inline void ers(int x){
int cyr=1;sum[1]--;
per(i,0,30){
int p=(x>>i&1);
cyr=trie[cyr][p],sum[cyr]--;
}
}
struct node{
int l,r;vt<int>ope;
}sg[1200005];
inline void init(int i,int l,int r){
sg[i].l=l,sg[i].r=r,sg[i].ope.clear();
if(l==r)return;
init(i<<1,l,(l+r)>>1);
init(i<<1|1,((l+r)>>1)+1,r);
}
inline void add(int i,int l,int r,int x){
if(sg[i].l>r||sg[i].r<l)return;
if(sg[i].l>=l&&sg[i].r<=r){
sg[i].ope.pb(x);
return;
}add(i<<1,l,r,x);
add(i<<1|1,l,r,x);
}
inline void solve(int i,int mn){
for(auto x:sg[i].ope){
mn=min(mn,ins(x));
}if(sg[i].l==sg[i].r){
if(c[sg[i].l]==3)cout<<mn<<endl;
}else{
solve(i<<1,mn);
solve(i<<1|1,mn);
}for(auto x:sg[i].ope){
ers(x);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>q;
init(1,1,q);
map<int,vt<int> >mp;
rp(i,q){
cin>>c[i];
if(c[i]==1){
cin>>x[i];
mp[x[i]].pb(i);
}else if(c[i]==2){
cin>>x[i];
int l=mp[x[i]].back();
mp[x[i]].pop_back();
add(1,l,i-1,x[i]);
}
}for(auto i:mp){
for(auto j:i.second){
add(1,j,q,i.first);
}
}
solve(1,(1<<30));
return 0;
}//Crayan_r