专栏文章

2025.7.15

LLeNotFound
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miovmpbr
此快照首次捕获于
2025/12/03 01:53
3 个月前
此快照最后确认于
2025/12/03 01:53
3 个月前
查看原文
先咕着，明天更😋
我昨天都要写啥来着
开场被 aloha 带飞了，签到题他直接秒了。
在线编辑器写代码的奆佬 Orz。
然后一个结论题，一开始打表范围不够广，导致有些后边才覆盖到的样例没被筛掉，把 OEIS 到的正确结论给否了。
后来是注意力惊人阶段，注意到数列本质上是把 44 和 %4==2\%4==2 的数都扣掉之后的结果。
然后就是实现计数了，这里花了好多时间，还是要练代码能力QAQ。
最后一个线段树题，aloha 的理论对了但是……代码不会写。
大意是线段树维护排序后数组每个数字的出现次数和位置，然后粗略算了一下要开 1e18+1 棵线段树，对于离散化只会 map 的我
赛后试了一下，先把输入都离线下来，然后离散化出 n+qn+q 大小的数组，保存每个数字可能的值，再用这个建树，之后对每次操作就查询小于第 ⌈n−12⌉\lceil \frac{n-1}{2} \rceil 个数的个数就行了。
然后就是……与空气斗智斗勇的阶段，调了好久，最后发现是单点修改没 pushup()
我甚至怀疑过取整精度……
后来通过率卡到 70% 多，以为是清空操作导致的超时，然后改成结构体线段树发现没变。
最后把大小改到 4×(n+q)4 \times (n+q) 就过了，毕竟离散化之后就不用开原来那么大了。
CPP
struct sgt
{
    vector<ll> w;

    sgt(ll siz)
    {
        w.resize(siz<<2,0);
    }

    void pushup(ll u)
    {
        w[u]=w[u<<1]+w[u<<1|1];
    }
    
    bool inrange(ll L,ll R,ll l,ll r)
    {
        return L>=l && R<=r;
    }
    
    bool outofrange(ll L,ll R,ll l,ll r)
    {
        return L>r || R<l;
    }
    
    ll query(ll u,ll L,ll R,ll l,ll r)
    {
        if(inrange(L,R,l,r))
        {
            return w[u];
        }
        else if(!outofrange(L,R,l,r))
        {
            ll M=(L+R)>>1;
            return query(u<<1,L,M,l,r)+query(u<<1|1,M+1,R,l,r);
        }
        else 
        {
            return 0LL;
        }
    }
    
    void modify(ll u,ll L,ll R,ll p,ll x)
    {
        if(L==R)
        {
            w[u]+=x;
            return ;
        }
        else 
        {
            ll M=(L+R)>>1;
            if(p<=M)
            {
                modify(u<<1,L,M,p,x);
            }
            else 
            {
                modify(u<<1|1,M+1,R,p,x);
            }
            pushup(u);
        }
    }
    
    ll kth(ll u,ll L,ll R,ll k)
    {
        if(L==R)
        {
            return L;
        }
        else 
        {
            ll M=(L+R)>>1;
            if(w[u<<1]>=k)
            {
                return kth(u<<1,L,M,k);
            }
            else 
            {
                return kth(u<<1|1,M+1,R,k-w[u<<1]);
            }
        }
    }
};

void solution()
{
    ll n=read();
    ll q=read();

    // init();

    vector<ll> a;
    vector<ll> b;
    
    a.resize(n+1);
    b.resize(n+1);
    
    vector<ll> vals;
    vals.reserve(n+q);
    
    for(ll i=1;i<=n;i++)
    {
        a[i]=read();
        b[i]=a[i];
        vals.push_back(a[i]);
    }
    
    vector<pair<ll,ll>> op;
    
    for(ll i=1;i<=q;i++)
    {
        ll id=read();
        ll x=read();
        op.push_back((make_pair(id,x)));
        b[id]+=x;
        vals.push_back(b[id]);
        // vals.push_back(a[id]+x);
    }
    
    sort(vals.begin(),vals.end());
    vals.erase(unique(vals.begin(),vals.end()),vals.end());
    ll m=vals.size();
    sgt t(m);

    for(ll i=1;i<=n;i++)
    {
        ll p=lower_bound(vals.begin(),vals.end(),a[i])-vals.begin();
        t.modify(1,0,m-1,p,1);
    }

    ll k=ceill((ld)(n-1)/2.0L);
    // ll k=n/2;
    // ll k=(n-1+1)/2;

    ll num=n-k+1;

    for(ll i=0;i<q;i++)
    {
        ll p=op[i].first;
        ll x=op[i].second;

        ll ori=lower_bound(vals.begin(),vals.end(),a[p])-vals.begin();
        t.modify(1,0,m-1,ori,-1);
        a[p]+=x;
        ll now=lower_bound(vals.begin(),vals.end(),a[p])-vals.begin();
        t.modify(1,0,m-1,now,1);

        ll id=t.kth(1,0,m-1,num);
        ll ans=t.query(1,0,m-1,0,id-1);
        // ll ans=id>0?query(1,0,m-1,0,id-1):0;

        cout<<ans;
        putchar('\n');
    }
}
等明天的新手向题解吧，今天直播只能看懂前 6min QAQ。
招新的策划找齐了，然后明天分配下任务，新生赛出题工作也安排下去。
给项目组的人安排了完善官网的活，工作量有亿点大，关键是 theme 还是魔改的，虽然控制台有报错但是目前并不影响使用，希望别炸。
mkdocs-simple-blog
这下可以狠狠提需求了😋

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...