daily 3

CF 722C

区间并查集，对于某个点来说，如果他左侧/右侧的点已经被加入集合中去了，那么就把该点的值加入对应的集合，我们倒着进行添加即可

vector<int>fa;
vector<ll>sum;
int find(int x){
  return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
  int fx=find(x),fy=find(y);
  if(fx==fy)return;
  sum[fx]+=sum[fy];
  fa[fy]=fx;
}
void solve(){
  int n;cin>>n;
  fa.resize(n+1);
  sum.resize(n+1);
  iota(fa.begin(),fa.end(),0);
  vector<int>ord(n+1),vis(n+2);
  for(int i=1;i<=n;++i)cin>>sum[i];
  for(int i=1;i<=n;++i)cin>>ord[i];
  vector<ll>ans(n+1);
  ll res=0;
  for(int i=n;i>=1;--i){
    ans[i]=res;
    if(vis[ord[i]-1]){
      merge(ord[i]-1,ord[i]);
    }
    if(vis[ord[i]+1]){
      merge(ord[i]+1,ord[i]);
    }
    int f=find(ord[i]);
    res=max(res,sum[find(ord[i])]);
    vis[ord[i]]=1;
  }
  for(int i=1;i<=n;++i){
    cout<<ans[i]<<"\n";
  }
  return;
}

CF 731F

后缀和好题,我们知道，对于某个落在 [ka[i],(k+1) \ a[i]的数，最终取值是k*a[i]，那么我们对后缀取后缀和，然后每一段进行计算，注意不要重复计算，标记vis数组即可

void solve(){
  int n;
  cin>>n;
  vector<int>a(n+1);
  vector<ll>sum(MAXN),vis(sum);
  for(int i=1;i<=n;++i){
    cin>>a[i];
    sum[a[i]]++;
  }
  sort(a.begin()+1,a.end());
  for(int i=a[n]-1;i>=0;--i){
    sum[i]+=sum[i+1];
  }
  ll ans=0;
  for(int i=1;i<=n;++i){
    if(vis[a[i]])continue;
    ll res=0;
    int cnt=1;
    for(int j=a[i];j<=a[n];j+=a[i]){
      res+=sum[j]*a[i];
      vis[j]=1;
    }
    ans=max(ans,res);
    vis[a[i]]=1;
  }
  cout<<ans<<'\n';
  return;
}

CF 721D

不会做，看了题解发现是低能题
首先我们可以证明，对绝对值比较小的数进行操作比较好(这里就不证明了，很sb)
然后我们拿个set存数就好了

using pii=pair<ll,int>;
void solve(){
  int n,k,x;
  cin>>n>>k>>x;
  vector<ll>a(n+1);
  bool sign=false;
  set<pii>st;
  for(int i=1;i<=n;++i){
    cin>>a[i];
    if(a[i]<0){
        sign=!sign;
    }
    st.insert({abs(a[i]),i});
  }
  for(int i=1;i<=k;++i){
    auto id=st.begin()->second;
    st.erase(st.begin());
    if(a[id]<0)sign=!sign;
    if(sign){
        a[id]+=x;
    }
    else
    {
        a[id]-=x;
    }
    if(a[id]<0)sign=!sign;
    st.insert({abs(a[id]),id});
  }
  for(int i=1;i<=n;++i){
    cout<<a[i]<<" \n"[i==n];
  }
  return;
}