题解：AT_abc403_g [ABC403G] Odd Position Sum Query

· · 题解

考虑对下标分奇偶建两棵平衡树 T_1,T_2（就是当前操作前奇数下标的放在第一棵树，偶数在第二棵），然后对于插入一个 x，在两棵树上查 x 的排名 rnk_1(x),rnk_2(x)，可以得到 x 在所有数中的排名 rk=rnk_1(x)+rnk_2(x)-1，根据 rk 的奇偶性即可确定 x 应该放到哪棵树上。插入 x 只会对下标比它大的数产生影响，也就是比它大的那些数的下标集体加一（也就是奇偶性互换）。

所以按值 x 分裂两棵树为四棵树 T_1\to a,b,T_2\to c,d，然后把 d 接到 a 上，b 接到 c 上即可完成互换（T_1\leftarrow a+d,T_2\leftarrow c+b）。最后把 x 插到对应的树上去即可，查询的答案即为 T_1 的所有元素的和。用 FHQ 实现，非常直观好写，时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+7;
int n;
#define ls tree[now].l
#define rs tree[now].r
int root[2],cnt;
struct node{
    int val,sum;
    int l,r,siz,wei;
}tree[maxn];
void pushup(int now){
    tree[now].siz=tree[ls].siz+tree[rs].siz+1;
    tree[now].sum=tree[ls].sum+tree[rs].sum+tree[now].val;
    // 维护子树和
}
int create(int val){
    tree[++cnt]={val,val,0,0,1,rand()};
    return cnt;
}
void split(int now,int val,int &rt1,int &rt2){
    if(!now){ rt1=rt2=0; return; }
    if(tree[now].val<=val){
        rt1=now;
        split(rs,val,rs,rt2);
    }else{
        rt2=now;
        split(ls,val,rt1,ls);
    }
    pushup(now);
}
int merge(int rt1,int rt2){
    if(!rt1||!rt2) return rt1+rt2;
    if(tree[rt1].wei>tree[rt2].wei){
        tree[rt1].r=merge(tree[rt1].r,rt2);
        pushup(rt1);
        return rt1;
    }else{
        tree[rt2].l=merge(rt1,tree[rt2].l);
        pushup(rt2);
        return rt2;
    }
}
void ins(int val,int wt){
    int x,y;
    split(root[wt],val-1,x,y);
    root[wt]=merge(merge(x,create(val)),y);
}
int rnk(int val,int wt){
    int x,y,rks;
    split(root[wt],val-1,x,y);
    rks=tree[x].siz+1;
    root[wt]=merge(x,y);
    return rks;
} // 板子
void swp(int x){ // 交换
    int a,b,c,d;
    split(root[0],x-1,a,b);
    split(root[1],x-1,c,d);
    root[0]=merge(a,d);
    root[1]=merge(c,b);
}
signed main(){
    cin>>n;
    int z=0; 
    for(int i=1,y,x;i<=n;i++){
        cin>>y; x=(y+z)%1000000000+1;
        int pos=rnk(x,0)+rnk(x,1)-1;
        swp(x); ins(x,pos&1);
        cout<<tree[root[1]].sum<<'\n';
        z=tree[root[1]].sum;
    }
    return 0;
}