为了让退出游戏的怪兽数量尽可能多，肯定是 $r$ 大的打 $r$ 小的，所以考虑用桶维护 $r$ 的出现次数，对于一个新的 $r$ 值，先让它打败 $r$ 比它小的，然后再加上它的数量。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,cnt[N],ans;
int main(){cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;cnt[x]++;}for(int i=1;i<=1e5;i++){ans-=min(ans,cnt[i]);ans+=cnt[i];}cout<<ans<<endl;return 0;
}

对于不同的加速度分类讨论，不难发现所有车超速的范围都是一个区间。

进而所有车能被测速仪测到的范围也是一个区间，这个可以通过二分预处理出来。

然后问题变为给我们若干个区间，选最少的点使得每个区间都至少覆盖到一个选中的点，这是个经典的贪心问题。

首先先按 $l$ 从小到大排序，$l$ 相等的按 $r$ 从大到小排序。对于 $[l_i,r_i],[l_j,r_j]$，若 $i$ 区间完全包含 $j$ 区间，则 $i$ 区间无用，然后我们就保证剩下的区间都按 $l,r$ 从小到大排序，接下来就很容易做了。

#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define double long double
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
const int N=1e5+10,INF=1e9;
int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;
}
int T,n,m,p[N],d[N],a[N],V,L,v[N],tot,res,del[N];
struct node{int l,r;}seg[N];
bool cmp(node a,node b){if(a.l!=b.l) return a.l<b.l;return a.r>b.r;
}
int main(){T=rd;while(T--){tot=res=0,n=rd,m=rd,L=rd,V=rd;FOR(i,1,n) d[i]=rd,v[i]=rd,a[i]=rd;FOR(i,1,m) p[i]=rd;sort(p+1,p+1+m);FOR(i,1,n){if(a[i]<=0&&v[i]<=V) continue;if(a[i]>0){int dis=V*V-v[i]*v[i];dis/=2*a[i],dis+=d[i];if(v[i]>V) dis=d[i]-1; int pos=0,l=1,r=m;while(l<=r){int mid=(l+r)>>1;if(p[mid]>dis) pos=mid,r=mid-1;else l=mid+1;}if(!pos) continue;seg[++tot]={pos,m};}else{int l=1,r=m,posl=0,posr=0;while(l<=r){int mid=(l+r)>>1;if(p[mid]>=d[i]) posl=mid,r=mid-1;else l=mid+1;}if(!posl) continue;l=posl,r=m;while(l<=r){int mid=(l+r)>>1;double tmp=sqrt(1.0*v[i]*v[i]+2.0*a[i]*(p[mid]-d[i]));if(tmp>V) l=mid+1,posr=mid;else r=mid-1;}if(posr<posl) continue;seg[++tot]={posl,posr};}}sort(seg+1,seg+1+tot,cmp),memset(del,0,sizeof(del));int mnr=INF;ROF(i,tot,1){if(mnr<=seg[i].r) del[i]=1;mnr=min(mnr,seg[i].r);}mnr=0;FOR(i,1,tot){if(del[i]) continue;if(mnr<seg[i].l){res++,mnr=seg[i].r;}}printf("%d %d\n",tot,m-res);}return 0;
}

一眼 dp 题。

设 $f_{i,0/1}$ 表示前 $i$ 个数，第 $i$ 个数染蓝 / 红色所能得到的最大价值，答案为 $\max (f_{n,0},f_{n,1})$。

考虑怎么转移，不难发现对于 $i$，它可以不产生贡献，直接从 $\max (f_{i-1,0},f_{i-1,1})$ 转移过来。

再考虑它要与之前的一个与它相等的位置配对，显然肯定要与它的前驱配对，这样才是最优的。而每个位置的前驱可以 $O(n)$ 预处理。

设 $i$ 的前驱为 $l$，$[l+1,i-1]$ 区间内的数一定会染同色。我们思考如何得到贡献，发现可以由三部分组成，首先是 $f_{l+1,co{l}_i\oplus 1}$，再就是 $[l+2,i-1]$ 区间全染同色可以产生的贡献，然后是 $a_i$。最后取一遍 $\max$ 即可。

注意特判 $l=i-1$ 的情况，此时转移为 $f_{i,co{l}_i}=f_{i-1,co{l}_i}+a_i$。

实际上 $f_{i,0/1}$ 是可以改为 $f_i$ 的，从转移式即可看出。

#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i<=k;i--)
const int N=2e5+10,M=1e6+10;
int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;
}
int n,pos[M],la[N],a[N],T;ll s[N],f[N][2];
int main(){T=rd;while(T--){memset(pos,0,sizeof(pos)),memset(la,0,sizeof(la)),memset(f,0,sizeof(f)),memset(s,0,sizeof(s));n=rd;FOR(i,1,n){a[i]=rd;la[i]=pos[a[i]],pos[a[i]]=i;}FOR(i,1,n) s[i]=s[i-1]+(a[i]==a[i-1])*a[i];FOR(i,1,n){int l=la[i];ll res1=0,res2=0;f[i][0]=f[i][1]=max(f[i-1][0],f[i-1][1]);if(l!=i-1&&l>0){res1=f[l+1][1]+a[i]+s[i-1]-s[l+1];res2=f[l+1][0]+a[i]+s[i-1]-s[l+1];}else if(l==i-1&&l>0) res1=f[i-1][0]+a[i],res2=f[i-1][1]+a[i];f[i][0]=max(f[i][0],res1),f[i][1]=max(f[i][1],res2);}printf("%lld\n",max(f[n][0],f[n][1]));}return 0;
}

将原问题转化为判断 $i$ 在 $c_j$ 的条件下能否成为擂主。

不难发现比赛过程会形成一颗完全二叉树，预处理出来 $f_x$ 表示在 $x$ 节点获胜的人是谁，这个可以 $O(n)$ 做到。然后暴力模拟每个 $i$ 向上跳的过程，根据题意分情况讨论一下，注意若有 $i>n$ 的新补充的选手，他可以随意输或赢。

时间复杂度 $O(Tnmlogn)$。

考虑优化，发现若前 $n^{\prime }$ 轮时，$i$ 能成为擂主，那么 $n^{\prime \prime }<n^{\prime }$ 时，$i$ 依然能成为擂主。每个 $i$ 都会对 $c$ 的一段区间做出贡献，设 $g_x$ 表示跳到 $x$ 节点的 $n^{\prime }$ 的最大值，这个可以和 $f$ 一起预处理出来。然后每次询问对于每个 $i$ 向上跳即可。

时间复杂度 $O(T(nlogn+m))$。

还是不够快，思考每次询问的线性做法。

发现进行操作的区间只有 $O(n)$ 个，所以从根节点开始，自顶向下不断走到左子树，对于每个左节点 dfs 一遍，会进行 ${\sum }_{i=1}^K{2}^i=O(n)$。

dfs 过程中，对于从 $x$ 到 $y$ 的边，倒着考虑之前 $y$ 到 $x$ 的操作过程，维护两个量 $val,mx$，$val$ 反映能否跳到这次枚举的左节点，$mx$ 反映额外的限制。

时间复杂度 $O(T(n+m))$。

这道题确实古怪，具体实现细节看代码。

#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;
}
const int N=4e5+10,M=20,INF=(1<<31)-1;
int n,m,T,k,a[N],aa[N],c[N],nn,X[N],p[N],t[N],f[N],g[N],op[N];ll ans[N];char s[M][N];
void dfs(int x,int d){p[d]++;if(d==k){t[x]=p[d];return;}//t[x]表示x叶子结点代表的编号op[x]=s[d][p[d]]-'0';//谁是擂主dfs(x<<1,d+1),dfs(x<<1|1,d+1);
}
void dfs1(int x,int d){//预处理f,g数组if(d==k){f[x]=t[x],g[x]=t[x]-1;return;}dfs1(x<<1,d+1),dfs1(x<<1|1,d+1);if(!op[x]){//转移比较简单if(a[f[x<<1]]>=k-d) f[x]=f[x<<1],g[x]=g[x<<1];else f[x]=f[x<<1|1],g[x]=g[x<<1|1];g[x]=max(g[x],g[x<<1]);}else{if(a[f[x<<1|1]]>=k-d) f[x]=f[x<<1|1],g[x]=g[x<<1|1];else f[x]=f[x<<1],g[x]=g[x<<1];g[x]=max(g[x],g[x<<1|1]);}
}
void update(int l,int r,int val){//差分if(l>r) return;r=min(r,nn);ans[l]+=val,ans[r+1]-=val;
}
void DFS(int x,int d,int l,int r,int val,int mx){if(l>val) return;if(d==k){int tmp=t[x];if(a[tmp]>=mx) update(max(l,tmp),min(r,val),tmp);update(l,min(tmp-1,val),tmp);return;}if(!op[x]){DFS(x<<1,d+1,l,r,val,max(mx,k-d));DFS(x<<1|1,d+1,l,r,a[f[x<<1]]>=k-d?min(val,g[x<<1]):val,mx);}else{DFS(x<<1,d+1,l,r,a[f[x<<1|1]]>=k-d?min(val,g[x<<1|1]):val,mx);DFS(x<<1|1,d+1,l,r,val,max(mx,k-d));}
}
int main(){n=rd,m=rd;FOR(i,1,n) aa[i]=rd;FOR(i,1,m) c[i]=rd;nn=1,k=0;while(nn<n) nn<<=1,k++;ROF(i,k-1,0) scanf("%s",s[i]+1);dfs(1,0);T=rd;while(T--){FOR(i,0,3) X[i]=rd;FOR(i,1,n) a[i]=aa[i]^X[i%4];FOR(i,n+1,nn) a[i]=INF;FOR(i,0,n) ans[i]=0;dfs1(1,0),update(1,1,1);int rt=1,d=0;//枚举左节点while((rt<<1)<=nn) DFS(rt,d,(1<<(k-d-1))+1,(1<<(k-d)),INF,0),rt<<=1,d++;ll res=0;FOR(i,1,n) ans[i]+=ans[i-1];FOR(i,1,m) res^=1ll*i*ans[c[i]];printf("%lld\n",res);}return 0;
}