您现在的位置是:首页 > 正文

bzoj4184 shallot(线段树时间分治+线性基)

2024-04-01 00:55:46阅读 1

我们按时间建线段树,把所有数的存在时间求出来,一定是一个连续的区间,插到线段树对应区间上。线段树每个节点挂一个vector来存数。这样就把删除操作避免掉了。然后从上到下dfs一遍线段树,把每个叶子的线性基合并出来即可,复杂度 O(nlognlogw) O ( n l o g n l o g w )
空间 O(nlogn+nlogw) O ( n l o g n + n l o g w )

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 500010
#define pi pair<int,int>
inline char gc(){
    static char buf[1<<16],*S,*T;
    if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
    return x*f;
}
int n;
set<pi>st;set<pi>::iterator it;
struct Icefox{
    int b[31];
    inline void ins(int x){
        for(int i=30;i>=0;--i){
            if(!(x>>i&1)) continue;
            if(b[i]) x^=b[i];
            else{b[i]=x;return;}
        }
    }inline int ans(){
        int res=0;
        for(int i=30;i>=0;--i) if((res^b[i])>res) res^=b[i];return res;
    }
}zero;
vector<int>tr[N<<2];
inline void ins1(int p,int l,int r,int x,int y,int val){
    if(x<=l&&r<=y){tr[p].push_back(val);return;}
    int mid=l+r>>1;
    if(x<=mid) ins1(p<<1,l,mid,x,y,val);
    if(y>mid) ins1(p<<1|1,mid+1,r,x,y,val);
}
inline void dfs(int p,int l,int r,Icefox x){
    for(int i=0;i<tr[p].size();++i) x.ins(tr[p][i]);
    if(l==r){printf("%d\n",x.ans());return;}
    int mid=l+r>>1;
    dfs(p<<1,l,mid,x);dfs(p<<1|1,mid+1,r,x);
}
int main(){
//  freopen("a.in","r",stdin);
    n=read();
    for(int i=1;i<=n;++i){
        int x=read();
        if(x>0){st.insert(make_pair(x,i));continue;}
        it=st.lower_bound(make_pair(-x,0));
        ins1(1,1,n,(*it).second,i-1,-x);st.erase(it);
    }for(it=st.begin();it!=st.end();++it) ins1(1,1,n,(*it).second,n,(*it).first);
    dfs(1,1,n,zero);
    return 0;
}

网站文章

  • html5 学习之路 一(视频、音频、拖放)

    html5 基本概念:

    2024-04-01 00:55:21
  • python面向对象

    面向对象属性查找1.先从对象的名称空间找2.再从对象类的类变量找3.在找父类的类变量先对象本身-->类-->父类-->父类的父类-->object-->自己定制的元类-->typeclass people(): v_id=0 def __init__(self,name): self.name=namec...

    2024-04-01 00:55:15
  • easyheap

    easyheap

    首先,检查一下程序的保护机制,发现没开PIE,且got表可写然后,我们用IDA分析一下,发现没有show功能出现了很多sub_4008F1()函数我们一个个点开看一下,发现最后一个是创建,为了便于分析我们可以改成add(n)可以看出创建节点功能里,存在ptr[i]堆内容未初始化的漏洞经过分析,节点的结构体如下struct Obj{ char *Data; int Size...

    2024-04-01 00:55:06
  • 障碍物决策横纵向标签

    决策

    2024-04-01 00:55:00
  • SFP光纤笼子 别称 作用 性能要点 工程要素

    SFP光纤笼子 别称 作用 性能要点 工程要素

    2023年,Hqst盈盛电子于下属五金部开发生产SFP光纤连接器笼子等系列产品,所有产品生产及性标准都将参照连接器产品常用测试标准EIA-364-C等标准,以下为我司常规SFP光纤连接器基本性能要求。...

    2024-04-01 00:54:35
  • MySQL之深入InnoDB存储引擎——Buffer Pool

    MySQL之深入InnoDB存储引擎——Buffer Pool

    以这个算法为核心,InnoDB维护了一个LRU链表,如果页不在Buffer Pool中,在把该页从磁盘加载到Buffer Pool的时候,就把该缓冲页对应的控制块作为节点添加到LRU链表的头部,如果使...

    2024-04-01 00:54:27
  • 攻防世界Web新手区题解(超详细)

    攻防世界Web新手区题解(超详细)

    Web新手区题解

    2024-04-01 00:54:20
  • python读取和保存json文件

    json文件是一种常见的数据存储文件,比txt看着高级点,比xml看着人性化一点。 同时,json作为一种通用协议的文件格式,可以被各种语言方便地读取。所以,json非常适合用来存储结构化的数据。 json的具体介绍和使用规范:https://www.json.org/json-en.html 本文将关于python读取json做一个小小的记录和总结。 1. 读取json 一般情况下的j...

    2024-04-01 00:53:52
  • 求教:MyBatis的缓存到底有用吗?

    前言:今天看了下mybatis的缓存,发现其实这个缓存基本可以说是没有用的,以下是一些个人观点: 为什么没有用呢? 首先:MyBatis分为一级缓存和二级缓存 一级缓存:存在于SqlSession的生...

    2024-04-01 00:53:40
  • GitHub修改仓库文件

    GitHub修改仓库文件

    GitHub修改仓库文件1.初始化git环境:git init2.创建并修改本地文件(以README文件为例):vi README.md3.添加到暂存区:git add README.md4.保存提交...

    2024-04-01 00:53:31