BZOJ_4184_shallot_线段树按时间分治维护线性基
2024-08-25 16:39:56
BZOJ_4184_shallot_线段树按时间分治维护线性基
Description
小苗去市场上买了一捆小葱苗,她突然一时兴起,于是她在每颗小葱苗上写上一个数字,然后把小葱叫过来玩游戏。
每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗,并且
让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。
这种小问题对于小葱来说当然不在话下,但是他的身边没有电脑,于是他打电话给同为Oi选手的你,你能帮帮他吗?
你只需要输出最大的异或和即可,若小葱手中没有小葱苗则输出0。
Input
第一行一个正整数n表示总时间;第二行n个整数a1,a2...an,若ai大于0代表给了小葱一颗数字为ai的小葱苗,否则代表从小葱手中拿走一颗数字为-ai的小葱苗。
Output
输出共n行,每行一个整数代表第i个时刻的最大异或和。
Sample Input
6
1 2 3 4 -2 -3
Sample Output
1
3
3
7
7
5
3
3
7
7
5
HINT
N<=500000,Ai<=2^31-1
感觉学到一个有用的东西。
有些问题支持插入但不支持删除或者支持删除但不支持插入。
这时我们可以发现每个元素在时间轴上都出现了一段区间,然后这个区间用线段树来维护。
比如这道题,我们知道线性基支持O(logn)的插入但不支持快速删除一个元素。
于是线段树每个节点维护一颗线性基。
我们可以求出每个数出现的区间,把这段区间在线段树上对应的log个节点插入这个数。
最后dfs一遍线段树,每次暴力pushdown,每个叶子就对应着这一个时间点的答案。
这样空间复杂度是O(4nlogn)的,过不去。
线段树每个节点没必要真开出来一个线性基,在下传的时候加一个线性基的参数即可。
这样意味着我们区间修改时不能直接插入,可以先用vector存下每个节点对应要插哪些数。
然后再把标记下传,这样空间是vector的O(nlogn),可过。
本题数据保证不会出现形如A....A....-A....-A的情况,于是求每个数对应的区间可以直接用map求。
代码:
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
#define N 500050
#define ls p<<1
#define rs p<<1|1
map<int,int>mp;
vector<int>v[N<<2];
struct LB {
int b[31];
LB() {memset(b,0,sizeof(b));}
void insert(int x) {
int i;
for(i=30;i>=0;i--) if(x&(1<<i)) {
if(b[i]) x^=b[i];
else {
b[i]=x; return ;
}
}
}
int query() {
int ans=0,i;
for(i=30;i>=0;i--) {
if(b[i]) ans=max(ans,b[i]^ans);
}
return ans;
}
};
int n,ans[N],a[N];
void update(int l,int r,int x,int y,int va,int p) {
if(x<=l&&y>=r) {v[p].push_back(va); return ;}
int mid=(l+r)>>1;
if(x<=mid) update(l,mid,x,y,va,ls);
if(y>mid) update(mid+1,r,x,y,va,rs);
}
void solve(int l,int r,int p,LB t) {
int i,lim=v[p].size();
for(i=0;i<lim;i++) {
t.insert(v[p][i]);
}
if(l==r) {
ans[l]=t.query(); return ;
}
int mid=(l+r)>>1;
solve(l,mid,ls,t);
solve(mid+1,r,rs,t);
}
int main() {
scanf("%d",&n);
int i,x;
for(i=1;i<=n;i++) {
scanf("%d",&a[i]);
if(a[i]>0) mp[a[i]]=i;
else update(1,n,mp[-a[i]],i-1,-a[i],1),mp[-a[i]]=0;
}
for(i=1;i<=n;i++) {
if(a[i]>0&&mp[a[i]]) update(1,n,mp[a[i]],n,a[i],1);
}
LB base; memset(base.b,0,sizeof(base));
solve(1,n,1,base);
for(i=1;i<=n;i++) printf("%d\n",ans[i]);
}
最新文章
- (Python )控制流语句if、for、while
- 用EF6更新数据库时出现外键错误解决方式
- Nginx工作原理和优化、漏洞
- 【ASP.NET基础】简单企业产品展示网站--产品编辑CRUD
- Canvas旋转图片--保持相同大小的算法
- easyui struts后台实现tree返回json数据
- 如何让你的传输更安全--基于SSL协议的通信模式
- None.js 第四步 事件驱动程序
- Java内存管理-Stackoverflow问答-Java是传值还是传引用?(十一)
- websocket 的客户端 websocket-sharp
- InnoDB表回收空间
- c语言数字图像处理(一):bmp图片格式及灰度图片转换
- 180801-Spring之定时任务基本使用篇
- P4093 [HEOI2016/TJOI2016]序列
- 数据库——MySQL——索引
- 调用SMTP发送有附件的邮件
- Redis高级进阶(二)
- Framework7:不会Objective-C,也能开发iOS7应用
- Linux常用命令大全3
- java visualVM 使用
热门文章
- 谁才是最强战舰!-From 南京理工大学第八届程序设计大赛(校外镜像),博弈~~
- 希尔排序(shell)
- CDN是什么与CDN加速的原理
- spring-security 理解 笔记 介绍以及使用(持续更新)
- easyshell 安装
- 【Arcgis Server】程序动态发布MXD到Arcgis Server
- 有多个git项目要用多个秘钥
- [RxJS] Chain RxJS Operators Together with a Custom `pipe` Function using Array.reduce
- 单点登录cas常见问题(二) - 子系统是否会频繁訪问cas中心?
- 新浪微博发送消息和授权机制原理(WeiboSDK)