0428 C组模拟赛 题解
因为黑树说最好不要放出来我就把搬运删掉了。
T1 题解
这道题我赛时部分分炸掉了，所以我不会部分分。
首先我们发现 $f(n)$ 非常难处理，我们考虑对每个不同的 $f(n)$ 分别计算。
容易发现，$f(n)=x$ 的 $n$ 中，任意一个数都可以表示为 $p\cdot 2^x+c\cdot x$，其中 $p$ 是一个奇数，所以 $f=x$ 的第 $m$ 个数即可表示为 $(2m-1)\cdot 2^x+c\cdot x$，化简一下就是 $m\cdot 2^{x+1}-2^x+c\cdot x$，容易发现这是个关于 $m$ 的一次函数（由于是离散的所以其实也是个等差数列）的形式，我们可以二分第 $k$ 大的 $a$，对于每个 $f$，求出有几个 $a$ 大于它。得到答案后用等差数列求和解决，复杂度 $O(\log^2V)$，其中 $V$ 为值域。
code
code
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(register ll i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register ll i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline ll read(){
ll x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const ll inf=0x3f3f3f3f;
ll t,l,r,k,c,rkr[35],rkl[35];
ll rk(ll x,ll i){
return (x+(1<<i))>>(i+1);
}
ll rkf(ll x,ll i){
return rk(x-c*i,i);
}
ll getf(ll x,ll i){
return (x<<(i+1))-(1<<i)+c*i;
}
ll get(ll x,ll i){
return getf(rk(x,i),i);
}
bool chk(ll x){
ll cnt=0;
forup(i,0,30){
if(rkl[i]==0&&rkr[i]==0) break;
if(rkl[i]==rkr[i]) continue;
if(rkf(x,i)<=rkr[i]&&rkf(x,i)>rkl[i]){
cnt+=rkr[i]-rkf(x,i);
if(get(x-c*i,i)==x) cnt++;
}else if(rkf(x,i)<=rkl[i]){
cnt+=rkr[i]-rkl[i];
}else{
continue;
}
if(cnt<0) return false;
}
return cnt>=k;
}
ll calc(ll x){
ll res=0,cnt=0;
forup(i,0,30){
if(rkl[i]==0&&rkr[i]==0) break;
if(rkl[i]==rkr[i]) continue;
ll cc;
if(rkf(x,i)<=rkr[i]&&rkf(x,i)>rkl[i]){
cc=rkr[i]-rkf(x,i);
res+=(getf(rkf(x,i)+1,i)+getf(rkr[i],i))*cc/2;
}else if(rkf(x,i)<=rkl[i]){
cc=rkr[i]-rkl[i];
res+=(getf(rkl[i]+1,i)+getf(rkr[i],i))*cc/2;
}else{
continue;
}
cnt+=cc;
}
if(cnt<k) res+=x*(k-cnt);
return res;
}
signed main(){
t=read();
while(t--){
l=read();r=read();k=read();c=read();
mem(rkr,0);mem(rkl,0);
forup(i,0,30){
rkr[i]=rk(r,i);
rkl[i]=rk(l-1,i);
if(rkr[i]<=0) break;
}
ll L=0,R=1e18,M;
while(L<R){
M=(L+R+1)>>1;
if(chk(M)) L=M;
else R=M-1;
}
printf("%lld\n",calc(L));
}
}
T2 题解
因为我赛时就切出来了所以我不知道部分分怎么写。
由于三种手势是等价的所以只讲 $R$ 的情况。
首先假设不处理问号，即每个人的手势都是已知的。
容易想到，两个相邻的 $R$ 之间要么没有元素，要么有至少一个 $S$，否则就要用中间的一个 $P$ 打败其中一个 $R$ 然后用旁边的另一个区间中的 $S$ 打败这里面的 $P$。
这是一个贪心的思路，通俗点讲，我们要尽量使删除的 $R$ 最少，所以我们要让 $?$ 变成 $R$ 或 $S$。
考虑从前向后 dp，$dp_{i,0/1}$ 表示考虑前 $i$ 位，前面还有没有未处理的 $P$ 需要在后面处理，所能剩下的最多的 $R$。但是这个做法转移有点复杂，我讲完这个做法贴一下官方题解。
- 假如 $s_i=R$，$dp_{i,1}=dp_{i-1,1},dp_{i,0}=dp_{i-1,0}+1$。
这很好理解，如果前面有未处理的 $P$，那么在被处理前他将会杀穿，所以中间的 $R$ 都不会造成贡献。
- 假如 $s_i=P$，我们设 $ns$ 为 $1\le j < i$ 中，$s_j=S$ 的最大的 $j$（这可以在扫到它的时候存下来），$nq$ 表示最大的 $s_j=?$，假如这两个均存在（如果不存在特判即可），转移方程如下：
$$dp_{i,1}=\max{dp_{i-1,0},dp_{i-1,1}}$$ $$dp_{i,0}=\max{dp_{ns,0},dp_{nq-1,0},dp_{nq-1,1}}$$
首先，第二维为 $1$ 的很好理解，因为无论前面有没有 $P$ 到这里总归有一个，取较大的。为 $0$ 的比较复杂，为了不留后患，需要从前面找一个能处理它的，我刚才说过，这是个贪心的过程，显然我们找最靠后的 $?$ 或 $S$ 来处理会比较好，由于 $?$ 有可能在转移时提供了贡献，所以要从 $nq-1$ 转移。
- 假如 $s_i=S$，那 $dp_{i,0}=\max{dp_{i-1,0},dp_{i-1,1}},dp_{i,1}=-\infty$。
显然，由于 $S$ 是有能力处理 $P$ 的，所以这里可以直接取最大值，但是由于前面的 $P$ 必定被处理了（由于要构造最优解），所以 $dp_{i,1}$ 就不存在了。
- 假如 $s_i=?$，$dp_{i,0}=\max{dp_{i-1,0}+1,dp_{i-1,1}},dp_{i,1}=-\infty$。
大体思路和 $S$ 的一样就不多赘述，需要注意如果前面没有需要处理的 $P$，那么 $?$ 是可以做出贡献的，加个一。
另外容易发现每次 $dp_{i}$ 都是从 $dp_{i-1}$ 或者 $ns,nq$ 转移过来的，所以我们可以把 $i$ 这一维压掉，卷空间和长度最优解。
code
code
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(register int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register int i=(s);i>=(e);i--)
using namespace std;
const int N=1e6+5,inf=0x3f3f3f3f;
int n,a[N],nw[2];
char s[N];
signed main(){
scanf(" %s",s+1);n=strlen(s+1);
forup(i,1,n) a[i]=(s[i]=='R'?1:s[i]=='P'?2:s[i]=='S'?3:0);
forup(i,1,3){
int bt=i-1;
if(!bt) bt=3;
nw[0]=0;nw[1]=-inf;
int nb=-inf,nq=-inf;
forup(j,1,n){
if(a[j]==i){
++nw[0];
}else if(a[j]==0){
nq=max(nw[0],nw[1]);
nw[0]=max(nw[0]+1,nw[1]);
nw[1]=-inf;
}else if(a[j]==bt){
nw[0]=max(nw[0],nw[1]);
nw[1]=-inf;
nb=nw[0];
}else{
nw[1]=max(nw[1],nw[0]);
nw[0]=(nq<0&&nb<0?-inf:max(nb,nq));
}
}
printf("%d\n",max(nw[0],0));
}
}
附件：官方题解。
T3 题解
首先不考虑删除操作，这道题应该怎么做。
容易发现，每个数最后一次修改为 $0$ 之前的所有操作都不会有贡献，所以每个数对最大值的贡献就是它最后一次修改为 $0$ 后，所有操作 $2$ 的最大值。换言之，即为操作队列的后缀最大值。但是有些数从头到尾都没有被赋为 $0$ 过，为了解决这个问题，我们可以再开头加 $2n$ 个操作代替数组的初始化。
接下来考虑如何维护删除。发现维护删除非常麻烦，但是我们可以先加入所有没被删除过的操作，然后按删除的倒序加入操作，每加入一个统计答案，这就比较好处理。
考虑只加操作一的情况，容易发现每次增加操作一其实就是把当前位置的贡献改为另一个位置的后缀最大值，这启发我们用某种方法维护后缀最大值来处理操作 $2$。
容易想到在操作序列上维护一颗线段树，维护区间（操作 $2$ 的）后缀最大值最大值，区间操作一的数量（最后产生贡献的那个），区间操作一位置上的后缀最大值之和。（黑体是为了帮助断句）
对于操作二，假如当前要增加的操作为 2 v，由于后缀最大值显然是单调不增的，所以我们只要在线段树上二分找到最后一个大于 $v$ 的位置，然后将这一整段的后缀最大值修改为 $v$ 即可注意维护其他变量，具体看代码。
操作一十分简单，假如比原来位置靠前就不动，靠后就先减去原来的再加上新的就行了。
复杂度就是线段树模板的复杂度，完全能过，需要注意空间要开三倍（因为最开始要加 $2n$ 个操作）。
code
code
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(register ll i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register ll i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline ll read(){
ll x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
using pii=pair<ll,ll>;
const ll N=1e6+5;//注意开三倍
ll n,m,mm,q,vis[N],d[N],ans[N],gz[N];
pii a[N];
struct Node{
ll s,x;
}op[N];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
private:
ll querymax[N<<2],mark[N<<2],querysum[N<<2],querycnt[N<<2];
void PushUp(ll id){//上传的时候直接递归合并即可
querymax[id]=max(querymax[id<<1],querymax[id<<1|1]);
querysum[id]=querysum[id<<1]+querysum[id<<1|1];
querycnt[id]=querycnt[id<<1]+querycnt[id<<1|1];
}
void PushDown(ll id){
//由于整个区间都被修改了，
//所以querysum[id<<1|1]=querymax[id<<1|1]*querycnt[id<<1|1];
mark[id<<1]=mark[id<<1|1]=mark[id];
querymax[id<<1]=querymax[id<<1|1]=mark[id];
querysum[id<<1]=querymax[id<<1]*querycnt[id<<1];
querysum[id<<1|1]=querymax[id<<1|1]*querycnt[id<<1|1];
mark[id]=0;
}
public:
void Update(ll L,ll R,ll X,ll l=1,ll r=m,ll id=1){
//区间修改为某个值
if(L<=l&&r<=R){
querymax[id]=X;
querysum[id]=querymax[id]*querycnt[id];
mark[id]=X;
return;
}
if(l<r&&mark[id]!=0) PushDown(id);
if(L<=mid) Update(L,R,X,lson);
if(mid< R) Update(L,R,X,rson);
PushUp(id);
}
void Add(ll P,ll X,ll l=1,ll r=m,ll id=1){
//单点加操作 1
if(l==r){
querycnt[id]=X;
querysum[id]=querymax[id]*querycnt[id];
return;
}
if(l<r&&mark[id]!=0) PushDown(id);
if(P<=mid) Add(P,X,lson);
else Add(P,X,rson);
PushUp(id);
}
ll Search(ll X,ll l=1,ll r=m,ll id=1){
//二分找左边界
if(l==r) return l;
if(l<r&&mark[id]!=0) PushDown(id);
if(querymax[id<<1|1]>X) return Search(X,rson);
else if(querymax[id<<1]>X) return Search(X,lson);
else return 0;
}
ll AskSum(){//整个数组的和
return querysum[1];
}
}mt;
bool cmp(pii a,pii b){
return a.first>b.first;
}
signed main(){
n=read();mm=read();q=read();
forup(i,1,n){
a[i].first=read();a[i].second=i;
}
sort(a+1,a+n+1,cmp);
forup(i,1,n){//最开始加 2n 个操作代替数组初始化
op[++m]=Node{1,a[i].second};
op[++m]=Node{2,a[i].first};
}
forup(i,1,mm){
op[++m].s=read();op[m].x=read();
}
forup(i,1,q){
d[i]=read()+n*2;
vis[d[i]]=1;
}
forup(i,1,m){
if(!vis[i]){
if(op[i].s==1){//先删再加
if(gz[op[i].x]!=0) mt.Add(gz[op[i].x],0);
gz[op[i].x]=max(gz[op[i].x],i);
mt.Add(gz[op[i].x],1);
}else{
ll res=mt.Search(op[i].x);//先查再修
if(res<i){
mt.Update(res+1,i,op[i].x);
}
}
}
}
fordown(i,q,1){
//注意答案是删除后的，转换过来就是添加前的，先统计再操作
ans[i]=mt.AskSum();
if(op[d[i]].s==1){
mt.Add(gz[op[d[i]].x],0);
gz[op[d[i]].x]=max(gz[op[d[i]].x],d[i]);
mt.Add(gz[op[d[i]].x],1);
}else{
ll res=mt.Search(op[d[i]].x);
if(res<d[i]){
mt.Update(res+1,d[i],op[d[i]].x);
}
}
}
forup(i,1,q){
printf("%lld\n",ans[i]);
}
}