主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：AT_abc403_g [ABC403G] Odd Position Sum Query
最后更新于 2025-08-27 19:50:40
作者
AvisD
分类
题解
题解
AT_abc403_g
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
G 题竟然是个板子，还挺简单的。 现在的加入的数关系到上一个的答案，所以这题不能离线了。 注意到如果值域在 $10^5$ 以内我们可以用线段树直接解决了。 但现在的值域在 $10^9$ 里，那么用一个动态开点线段树就好了！ 最多加入 $3\times 10^5$ 个数，$\log V$ 最大是 $30$，其中 $V$ 代表值域，那开 $9\times 10^6$ 的数组就行了。 别忘记开 `long long`！ ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int N=9e6+10; int T,rt,x,ans,lim=1000000000; int tot,lc[N],rc[N],sz[N],t1[N],t2[N]; void modify(int &p,int l,int r,int v) { if(!p)p=++tot; if(l==r){sz[p]++,t1[p]=(sz[p]+1>>1)*v,t2[p]=(sz[p]>>1)*v;return;} int mid=l+r>>1; if(v<=mid)modify(lc[p],l,mid,v); else modify(rc[p],mid+1,r,v); sz[p]=sz[lc[p]]+sz[rc[p]]; if(sz[lc[p]]&1)t1[p]=t1[lc[p]]+t2[rc[p]],t2[p]=t2[lc[p]]+t1[rc[p]]; else t1[p]=t1[lc[p]]+t1[rc[p]],t2[p]=t2[lc[p]]+t2[rc[p]]; return; } signed main() { scanf("%lld",&T); while(T--) { scanf("%lld",&x); modify(rt,1,lim,(x+ans)%lim+1); ans=t1[1]; printf("%lld\n",ans); } return 0; } ```
正在渲染内容...
点赞
0
收藏
0
