[ABC438G] Sum of Min 题解

· · 题解

简单题。枚举 A_i 并考虑能和它一起产生贡献的 B_j，这样的 j 必然形如 (i+KN)\bmod M(K\ge 0)。

连边 j\to(j+N)\bmod M，会形成若干个环，A_i 的贡献就是 i\bmod M 所在的环从 i\bmod M 开始，往后走若干圈，最后再走一小段（具体走多远取决于 K）。记这样走形成的序列为 B_i，那么 A_i 的贡献即为 \sum\limits_{j=1}^{|B_i|}\min\{A_i,B_{i,j}\}。

经典套路，把 \min 拆开，分别计算 B_{i,j}\le A_i 与 B_{i,j}>A_i 的贡献。于是问题转换成了，查询环上一段区间内 \le A_i 的元素之和。这个方法很多，可以离线树状数组做，也可以直接 Merge Sort Tree（多个 \log）。赛时手头上正好有一份板子，就选用了后者。

令 N,M 同阶，时间复杂度 O(N\log N) 或 O(N\log^2 N)，取决于实现。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> R;
const int P=998244353;
inline int add(int x,int y){
  int s=x+y; if(s>=P)s-=P; return s;
}
inline void self_add(int &x,int y){
  if((x+=y)>=P)x-=P;
}
struct S{
  vector<ll> v,s;
  S(vector<ll> v={}):v(v),s(v.size()){
    partial_sum(v.begin(),v.end(),s.begin(),plus<ll>());
  }
  R query(int x){
    int p=upper_bound(v.begin(),v.end(),x)-v.begin()-1;
    return make_pair(p+1,~p?s[p]:0);
  }
};
inline S op(S x,S y){
  vector<ll> v(x.v.size()+y.v.size());
  merge(x.v.begin(),x.v.end(),y.v.begin(),y.v.end(),v.begin());
  return v;
}
inline R op(R x,R y){
  return R(x.first+y.first,x.second+y.second);
}
class segtree{
  private:
    int k,m;
    vector<S> w;
    void pushup(int u){
      w[u]=op(w[u<<1],w[u<<1|1]);
    }
  public:
    segtree(vector<S> a){
      int n=a.size();
      k=__lg(n)+(__builtin_popcount(n)>1);
      w.resize((m=1<<k)<<1);
      for(int i=0;i<n;i++)
        w[i+m]=a[i];
      for(int i=m-1;i;i--)
        pushup(i);
    }
    R query(int l,int r,int x){
      if(l>r)return R();
      R c; l+=m,r+=m+1;
      while(l<r){
        if(l&1)c=op(c,w[l++].query(x));
        if(r&1)c=op(w[--r].query(x),c);
        l>>=1,r>>=1;
      }
      return c;
    } // 查询区间 <= x 的元素之和
}; // Merge Sort Tree 模板
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,m,w=0; ll k; cin>>n>>m>>k;
  vector<int> a(n),b(m);
  for(auto &i:a)cin>>i;
  for(auto &i:b)cin>>i;
  vector<segtree> T;
  vector id(m,pii(-1,-1));
  vector<int> sz;
  for(int i=0;i<m;i++)
    if(id[i].first<0){
      vector<int> v;
      int s=i;
      do{
        id[s]=make_pair(T.size(),v.size());
        v.emplace_back(s),(s+=n%m)%=m;
      }while(s!=i);
      sz.emplace_back(v.size());
      vector<S> w(v.size());
      for(int i=0;i<v.size();i++)
        w[i]=S(vector<ll>({b[v[i]]}));
      T.emplace_back(w);
    } // 预处理环及环上元素
  for(int i=0;i<n;i++){
    auto [x,y]=id[i%m];
    ll q=k/n+(i<k%n);
    auto qry=[&](int l,int r){
      if(l<=r)return T[x].query(l,r,a[i]);
      R s1=T[x].query(l,sz[x]-1,a[i]),s2=T[x].query(0,r,a[i]);
      return op(s1,s2);
    }; // 环上区间查询，转换到链上做，拆一下询问
    int r=q%sz[x];
    if(r){
      auto [c,s]=qry(y,(y+r-1)%sz[x]);
      self_add(w,(((ll)(r-c)*a[i]+s)%P+P)%P);
    } // 有多出一段单独算
    ll p=q/sz[x];
    auto [c,s]=qry(0,sz[x]-1);
    self_add(w,(((ll)(sz[x]-c)*a[i]+s)%P*(p%P)%P+P)%P); // 整圈的贡献
  }
  cout<<w<<endl;
  return 0;
}