[ABC403G] Odd Position Sum Query 题解

· · 题解

本篇题解参考了 __gnu_pbds 中 tree 的扩展应用，在此表示对作者的感谢。

你说得对，但是 __gnu_pbds::tree 是可以支持自定义 pushup 的。

前置知识：__gnu_pbds::tree 的基本使用方法

考虑如何设计信息：需要维护的是，对于两个区间 [l_1,r_1],[l_2,r_2]，将 [l_2,r_2] 接在 [l_1,r_1] 之后所有奇数位置的和。维护信息 (s,o,e) 分别表示当前区间大小、奇数下标和与偶数下标和；合并 (s_1,o_1,e_1) 与 (s_2,o_2,e_2) 时分类讨论：

使用一个 tuple<int,long long,long long> 来存储信息。以下是一个信息合并的函数的例子：

typedef long long ll;
typedef tuple<int,ll,ll> tpi;
inline tpi operator +(const tpi &x,const tpi &y){
  return make_tuple(get<0>(x)+get<0>(y),
    get<1>(x)+(get<0>(x)&1?get<2>(y):get<1>(y)),
    get<2>(x)+(get<0>(x)&1?get<1>(y):get<2>(y)));
}

先定义一个结构体表示 tree 存储的类型（其中包含 key，即比较的关键字，以及其他你想维护的信息）。以下是一个本题中可以使用的结构体的例子：

struct S{
  int key; mutable tpi c;
  // 使用 mutable 是因为需要修改
  S(int key=0,int x=0,ll y=0,ll z=0):key(key),c(x,y,z){}
  bool operator <(const S &b)const{return key<b.key;}
  // 按照 key 排序
};

接下来自定义平衡树中的信息合并：即在 tree 中 Node_Update 的位置放上一个自己定义的更新。

template<class Node_CItr,class Node_Itr,class Cmp_Fn,class _Alloc> struct op{
  typedef tpi metadata_type;
  // 维护的额外信息
  void operator()(Node_Itr it,Node_CItr end_it){
    Node_Itr itl=it.get_l_child();
    Node_Itr itr=it.get_r_child();
    tpi l,r;
    if(itl!=end_it)l=itl.get_metadata();
    if(itr!=end_it)r=itr.get_metadata();
    const_cast<tpi&>(it.get_metadata())=l+(*it)->c+r;
    // 信息合并，注意顺序
  }
  virtual Node_CItr node_begin()const=0;
  virtual Node_CItr node_end()const=0;
};

为了方便操作，从 __gnu_pbds::tree 继承过来一个结构体，直接在里面定义操作：

struct rbt:tree<S,null_type,less<S>,rb_tree_tag,op>{
  inline void update(iterator x){
    update_to_top(x.m_p_nd,(node_update*)this);
  }
  // 修改一个结点的信息不会自动更新可能被影响到的结点
  // 需要一路手动更新上去
  inline void ist(int x){
    auto it=lower_bound(S(x,0,0,0));
    if(it==end()||it->key!=x)insert(S(x,1,x,0));
    else{
      get<0>(it->c)++;
      if(get<1>(it->c)>get<2>(it->c))get<2>(it->c)+=x;
      else get<1>(it->c)+=x;
      // 插入了多个 x
      update(it);
    }
  }
  inline ll all_prod(){
    return get<1>(node_begin().get_metadata());
    // 查询全局的答案
  }
}t;

以下给出完整代码供参考。

参考代码（GNU C++ 17）：

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tuple<int,ll,ll> tpi;
const int M=1e9;
struct S{
  int key; mutable tpi c;
  S(int key=0,int x=0,ll y=0,ll z=0):key(key),c(x,y,z){}
  bool operator <(const S &b)const{return key<b.key;}
};
inline tpi operator +(const tpi &x,const tpi &y){
  return make_tuple(get<0>(x)+get<0>(y),
    get<1>(x)+(get<0>(x)&1?get<2>(y):get<1>(y)),
    get<2>(x)+(get<0>(x)&1?get<1>(y):get<2>(y)));
}
template<class Node_CItr,class Node_Itr,class Cmp_Fn,class _Alloc> struct op{
  typedef tpi metadata_type;
  void operator()(Node_Itr it,Node_CItr end_it){
    Node_Itr itl=it.get_l_child();
    Node_Itr itr=it.get_r_child();
    tpi l,r;
    if(itl!=end_it)l=itl.get_metadata();
    if(itr!=end_it)r=itr.get_metadata();
    const_cast<tpi&>(it.get_metadata())=l+(*it)->c+r;
  }
  virtual Node_CItr node_begin()const=0;
  virtual Node_CItr node_end()const=0;
};
struct rbt:tree<S,null_type,less<S>,rb_tree_tag,op>{
  inline void update(iterator x){
    update_to_top(x.m_p_nd,(node_update*)this);
  }
  inline void ist(int x){
    auto it=lower_bound(S(x,0,0,0));
    if(it==end()||it->key!=x)insert(S(x,1,x,0));
    else{
      get<0>(it->c)++;
      if(get<1>(it->c)>get<2>(it->c))get<2>(it->c)+=x;
      else get<1>(it->c)+=x;
      update(it);
    }
  }
  inline ll all_prod(){
    return get<1>(node_begin().get_metadata());
  }
}t;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int q; ll l=0; cin>>q;
  for(int i=0;i<q;i++){
    ll y; cin>>y;
    (y+=l)%=M,y++,t.ist(y);
    cout<<(l=t.all_prod())<<'\n';
  }
  return 0;
}