题解：AT_abc403_g [ABC403G] Odd Position Sum Query

· · 题解

前情提要：超级好写的题。

知识：值域线段树。

对每个值域线段树的节点维护三个信息 len,even,odd 分别表示这个区间的长度（注意不能直接 r - l + 1 了，因为可能会有元素重复），区间内奇数位置的和，偶数位置的和。

我们发现，这种线段树是不用下传标记的，考虑上传的时候如果处理。

设 ls(u) 表示值域线段树上 u 的左儿子，rs(u) 表示值域线段树上 u 的右儿子。

然后就做完了，代码 27 行。

代码：

#include<iostream>
#define int long long
const int N = 2e5 + 5;
struct node{
    int len,even,odd;//区间长度，奇数位置的和，偶数位置的和 
}tr[N << 5];
int n,q,lst = 0,rt = 0,ls[N << 5],rs[N << 5],idx = 0,vl;
inline node operator + (const node & x,const node & y){
    return (node){x.len + y.len,x.even + ((x.len & 1) ? y.odd : y.even),x.odd + ((x.len & 1) ? y.even : y.odd)};
}
inline void ins(int &u,int l,int r,int x){
    if(!u) u = ++ idx;
    if(l == r) return (tr[u] = tr[u] + (node){1,l,0}),void();
    int mid = (l + r) >> 1;
    (x <= mid ? ins(ls[u],l,mid,x) : ins(rs[u],mid + 1,r,x));
    tr[u] = tr[ls[u]] + tr[rs[u]];
}
int32_t main(){
    std::cin >> q;
    for(int i = 1;i <= q; ++ i){
        std::cin >> vl;
        vl = (vl + lst) % 1000000000 + 1;
        ins(rt,1,1e9,vl);
        std::cout << (lst = tr[rt].even) << '\n';
    }
    return 0;
}