题解：AT_abc403_g [ABC403G] Odd Position Sum Query

wmrqwq · 2025-04-28 12:45:52 · 题解

题目链接

[ABC403G] Odd Position Sum Query

解题思路

介绍一个根号做法。

考虑根号重构，设一个阀值 B，将询问分成 \displaystyle \lfloor \frac{n}{B} \rfloor 块，每 B 次询问重构一次，前 B 次操作暴力做。

这样在第 i 次询问就会有 \max(\displaystyle\lfloor\frac{i}{B}\rfloor , 1) 块，只需要支持块内插入一个数字即可，这里可以使用 vector 维护，那么插入一个数复杂度为 O(B + \displaystyle\lfloor\frac{n}{B}\rfloor) 总时间复杂度为 O(nB + n \lfloor\displaystyle\frac{n}{B}\rfloor)，B 取 \sqrt{n} 即可。

参考代码

ll n;
ll sq,x;
ll a[1000010];
ll last;
ll f(ll x){
    return ((x+last)%(ll)1e9)+1;
}
struct bl{
    ll l,r;
    vector<pii>v;
    ll s0,s1;
    ll S;
    ll maxn;
    void clear()
    {
        maxn=0;
        l=0,r=0;
        v.clear();
        s0=s1=0;
    }
    void add(ll x)
    {
        if(Max(maxn,x))
        {
            v.pb({x,1});
            return ;
        }
        bool P=0;
        vector<pii>v2;
        for(auto i:v)
        {
            if(x<i.x)
            {
                if(!P)
                    v2.pb({x,1}),
                    P=1;
                v2.pb(i);
            }
            else if(x==i.x)
                P=1,
                v2.pb({x,i.y+1});
            else
                v2.pb(i);
        }
        if(!P)
            v2.pb({x,1});
        v=v2;
        // for(auto j:v)
            // cout<<",,"<<j.x<<" "<<j.y<<endl;
    }
    void query()
    {
        s1=s0=0;
        S=0;
        ll now=1;
        for(auto i:v)
        {
            if(now)
            {
                s1+=(i.y+1)/2*i.x;
                s0+=i.y/2*i.x;
                now^=i.y&1;
            }
            else
            {
                s0+=(i.y+1)/2*i.x;
                s1+=i.y/2*i.x;
                now^=i.y&1;
            }
            S+=i.y;
        }
    }
}B[300010];
/*
2 6 4 3 1000000000
*/
void build(ll x)
{
    forl(i,1,x)
        B[i].clear();
    sort(a+1,a+1+x*sq);
    forl(i,1,x)
    {
        B[i].l=B[i-1].r+1;
        B[i].r=i*sq;
        forl(j,B[i].l,B[i].r)
        {
            ll R=j,S=1;
            while(R<B[i].r && a[R+1]==a[j])
                R++,
                S++;
            B[i].v.pb({a[j],S});
            j=R;
        }
        B[i].maxn=a[B[i].r];
        B[i].query();
        // cout<<i<<":"<<B[i].s0<<' '<<B[i].s1<<endl;
    }
}
void _clear(){}
void solve()
{
    _clear();
    cin>>n;
    sq=sqrt(n);
    forl(i,1,min(n,sq))
    {
        cin>>x;
        x=f(x);
        a[i]=x;
        sort(a+1,a+1+i);
        ll S=0;
        forll(j,1,i,2)
            S+=a[j];
        cout<<S<<endl;
        last=S;
    }
    forl(i,sq+1,n)
    {
        if(i%sq==1)
            build(i/sq);
        cin>>x;
        x=f(x);
        a[i]=x;
        ll P=0;
        forl(j,1,i/sq)
            if(x<=B[j].maxn)
            {
                // cout<<i<<" add "<<j<<endl;
                P=1;
                B[j].add(x);
                B[j].query();
                break;
            }
        if(!P)
            B[i/sq].add(x),
            B[i/sq].query();
        ll now=0;
        ll ans=0;
        forl(j,1,i/sq)
        {
            if(now==0)
            {    
                ans+=B[j].s1;
                now^=B[j].S&1;
            }
            else
            {
                ans+=B[j].s0;
                now^=B[j].S&1;
            }
        }
        cout<<ans<<endl;
        last=ans;
    }
}