BZOJ 4184: shallot

时间:2023-01-05 18:37:50

Description

在某时刻加入或删除一个点,问每个时刻的集合中能异或出来的最大值是多少.

Sol

线段树+按时间分治+线性基.

按时间分治可以用 \(logn\) 的时间来换取不进行删除的操作.

把一个数字的存在时间挂在线段树的区间上,不超过 \(logn\) 个区间,所以总和不超过 \(nlogn\) 个节点信息.

然后从上往下走遍历整个线段树,每次到根节点统计一下答案,这里跟线性基有些不同,线性基转置矩阵就是普通的高斯消元,这时候维护线性基,每次插入一个数,更新的贡献,统计答案的时候从上往下贪心,选一个最大值,而不是回带...

Code

/**************************************************************
Problem: 4184
User: BeiYu
Language: C++
Result: Accepted
Time:11256 ms
Memory:37624 kb
****************************************************************/ #include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int N = 5e5+50;
const int M = 35; int n;
map< int,int > mp;
LL pow2[M],ans[N]; struct Py {
LL b[M];
Py() { memset(b,0,sizeof(b)); }
void insert(int x) {
for(int i=M-1;~i;i--) if(x&pow2[i]) {
if(!b[i]) { b[i]=x;break; }
else x^=b[i];
}
}
LL GetAns() {
LL ans=0;
for(int i=M-1;~i;i--) if((ans^b[i])>ans) ans^=b[i];
return ans;
}
}piyan;
struct SegMentTree {
vector< int > d[N<<2];
#define lc (o<<1)
#define rc (o<<1|1)
#define mid ((l+r)>>1) void insert(int o,int l,int r,int L,int R,int x) {
if(L<=l && r<=R) return void(d[o].push_back(x));
if(L<=mid) insert(lc,l,mid,L,R,x);
if(R>mid) insert(rc,mid+1,r,L,R,x);
}
void DFS(int o,int l,int r,Py py) {
for(vector< int > ::iterator i=d[o].begin();i!=d[o].end();i++) py.insert(*i);
if(l==r) return void(ans[l]=py.GetAns());
DFS(lc,l,mid,py),DFS(rc,mid+1,r,py);
}
}seg; inline int in(int x=0,char ch=getchar(),int v=1) {
while(ch>'9' || ch<'0') v=ch=='-' ? -1 : v,ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*v;
}
int main() {
n=in();
for(int i=1;i<=n;i++) {
int x=in();
if(x>=0) mp[x]=i;
else x=-x,seg.insert(1,1,n,mp[x],i-1,x),mp.erase(x);
}
for(map< int,int > ::iterator i=mp.begin();i!=mp.end();i++)
if((*i).second) seg.insert(1,1,n,(*i).second,n,(*i).first);
pow2[0]=1;for(int i=1;i<M;i++) pow2[i]=pow2[i-1]<<1;
seg.DFS(1,1,n,piyan);
for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
return 0;
}

BZOJ 4184: shallot的更多相关文章

  1. BZOJ&period;4184&period;shallot&lpar;线段树分治 线性基&rpar;

    BZOJ 裸的线段树分治+线性基,就是跑的巨慢_(:з」∠)_ . 不知道他们都写的什么=-= //41652kb 11920ms #include <map> #include < ...

  2. bzoj 4184 shallot——线段树分治&plus;线性基

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4184 本来想了可持久化trie,不过空间是 nlogn (出一个节点的时候把 tot 复原就 ...

  3. bzoj 4184&colon; shallot (线段树维护线性基)

    题面 \(solution:\) 这一题绝对算的上是一道经典的例题,它向我们诠释了一种新的线段树维护方式(神犇可以跳过了).像这一类需要加入又需要维护删除的问题,我们曾经是遇到过的像莫对,线段树... ...

  4. 「bzoj 4184&colon; shallot」

    权限题 线段树分治加线性基 首先这个题要求删除线性基肯定是没法处理的 于是我们套上一个线段树分治 线段树分治就是一种能够避免删除的神仙操作 我们发现询问是对一个时间的单点询问,而每一个数存在的时间却是 ...

  5. BZOJ 4184 shallot 线性基&plus;分治

    Description 小苗去市场上买了一捆小葱苗,她突然一时兴起,于是她在每颗小葱苗上写上一个数字,然后把小葱叫过来玩游戏. 每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗,并且让小葱从 ...

  6. bzoj 4184 shallot 时间线建线段树&plus;vector&plus;线性基

    题目大意 n个时间点 每个时间点可以插入一个权值或删除一个权值 求每个时间点结束后异或最大值 分析 异或最大值用线性基 但是线性基并不支持删除操作 我们可以对时间线建一棵线段树 离线搞出每个权值出现的 ...

  7. bzoj 4184&colon; shallot【线性基&plus;时间线段树】

    学到了线段树新姿势! 先离线读入,根据时间建一棵线段树,每个节点上开一个vector存这个区间内存在的数(使用map来记录每个数出现的一段时间),然后在线段树上dfs,到叶子节点就计算答案. 注意!! ...

  8. BZOJ 4184 线段树&plus;高斯消元

    思路: 线段树表示的是时间 每回最多log个段 区间覆盖 一直到叶子 的线性基 xor 一下 就是答案 一开始没有思路 看了这篇题解 豁然开朗 http://www.cnblogs.com/joyou ...

  9. LOJ 2312&lpar;洛谷 3733&rpar; 「HAOI2017」八纵八横——线段树分治&plus;线性基&plus;bitset

    题目:https://loj.ac/problem/2312 https://www.luogu.org/problemnew/show/P3733 原本以为要线段树分治+LCT,查了查发现环上的值直 ...

随机推荐

  1. Bungee Jumping&lbrack;HDU1155&rsqb;

    Bungee JumpingTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total ...

  2. JavaScript中with语句的理解

    with语句的作用是暂时改变作用域链.减少的重复输入. 其语法结构为: with(object){ //statements } 举一个实际例子吧: with(document.forms[0]){ ...

  3. 探究MaxxBass音效

    MaxxBass是什么?官方的介绍是这样的: — Patented Waves MaxxBass psycho-acoustic bassextension delivers a more natur ...

  4. C&plus;&plus;文件操作&lpar;输入输出、格式控制、文件打开模式、测试流状态、二进制读写&rpar;

    1.向文件写数据 头文件#include <ofstream> ①Create an instance of ofstream(创建ofstream实例) ②Open the file w ...

  5. URAL 1920 Titan Ruins&colon; the Infinite Power of Magic

    大意: 有一张N*N的网格,你每次可以走一步,每格只能走一次,有没有一种方法让走了L步后回到一个距原点1步远的格子?  没有输出Unsuitable device,否则输出Overwhelming p ...

  6. php&period;ini 配置文件的深入解析

    [PHP] ; PHP还是一个不断发展的工具,其功能还在不断地删减 ; 而php.ini的设置更改可以反映出相当的变化, ; 在使用新的PHP版本前,研究一下php.ini会有好处的 ;;;;;;;; ...

  7. Delegate&comma;Action&comma;Func&comma;Predicate的使用与区别

    C#4.0推出后,类似Linq,Lamda表达式等许多新的程序写法层次不穷.与之相关的Delegate,Action,Func,Predicate的使用和区别也常常让大家迷惑,此处就结合实际的应用,对 ...

  8. Navicat Mac 快捷键详解

    Navicat 是数据库管理工具,满足了大家对数据库的存储过程.事件.触发器.函数.视图等功能,并且支持MySQL.MariaDB.SQL Server.SQLite.Oracle 和 Postgre ...

  9. 5&period;Java中的数组&period;md

    1.Java的数组定义 Java中的定义有两种形式: type[] arraryName; //推荐形式 type arrayName[]; //不推荐 前一种有更好的语义,可读性更好.但是需要注意的 ...

  10. tp5 excel导出类

    1.引入Loader use think\Loader; 2.导出方法: /** * excel表格导出 * @param string $fileName 文件名称 * @param array $ ...