题解：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)

。

CPP

#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;
}

题解：AT_abc403_g [ABC403G] Odd Position Sum Query

文章操作

相关推荐

评论

题解：AT_abc403_g [ABC403G] Odd Position Sum Query