-
Notifications
You must be signed in to change notification settings - Fork 0
Home
hotman edited this page Oct 25, 2020
·
3 revisions
#pragma once
#include<vector>
#include"../alga/maybe.hpp"
/**
* @brief セグメント木
* @see https://en.wikipedia.org/wiki/Segment_tree
*/
template<typename T,typename F>
class segment_tree{
maybe<T>* node;
F op;
int n=1;
public:
segment_tree(){}
segment_tree(int sz,F op=F()):op(op){
while(n<=sz)n<<=1;
node=new maybe<T>[n*2];
for(int i=0;i<n*2;i++)node[i]=maybe<T>();
}
segment_tree(const std::vector<T>&v,F op=F()):op(op){
auto f=expand<T,F>(op);
const int sz=v.size();
while(n<=sz)n<<=1;
node=new maybe<T>[n*2]();
for(int i=0;i<sz;i++)node[i+n]=maybe<T>(v[i]);
for(int i=n-1;i>=1;i--)node[i]=f(node[i*2],node[i*2+1]);
}
maybe<T> get(int l,int r){
auto f=expand<T,F>(op);
l+=n;r+=n;
maybe<T> s,t;
while(l<r){
if(l&1)s=f(s,node[l++]);
if(r&1)t=f(node[--r],t);
l>>=1;r>>=1;
}
return f(s,t);
}
void apply(int t,T _val){
auto f=expand<T,F>(op);
t+=n;
maybe<T> val=maybe<T>(_val);
while(t){
node[t]=f(node[t],val);
t=t>>1;
}
}
void apply_left(int t,T _val){
auto f=expand<T,F>(op);
t+=n;
maybe<T> val=maybe<T>(_val);
while(t){
node[t]=f(val,node[t]);
t=t>>1;
}
}
void change(int t,T val){
auto f=expand<T,F>(op);
t+=n;
node[t]=maybe<T>(val);
while(t>1){
t=t>>1;
node[t]=f(node[t*2],node[t*2+1]);
}
}
};#pragma once
#include"../alga/maybe.hpp"
/**
* @brief 双対セグメント木
*/
template<typename T,typename F>
class dual_segment_tree{
struct node;
using np=node*;
using i64=long long;
struct node{
maybe<T> val;
np ch[2]={nullptr,nullptr};
node(maybe<T> val=maybe<T>()):val(val){}
};
np root=nullptr;
i64 n=1,sz;
F op;
public:
dual_segment_tree(i64 sz,F op=F()):sz(sz),op(op){while(n<sz)n<<=1;}
inline void update(i64 l,i64 r,T x){update(l,r,x,0,n,root);}
inline maybe<T> get(i64 x){return get(x,0,n,root);}
private:
void eval(np& t){
auto f=expand<T,F>(op);
if(t->val.is_none())return;
if(!t->ch[0])t->ch[0]=new node();
if(!t->ch[1])t->ch[1]=new node();
t->ch[0]->val=f(t->ch[0]->val,t->val);
t->ch[1]->val=f(t->ch[1]->val,t->val);
t->val=maybe<T>();
}
void update(i64 a,i64 b,T x,i64 l,i64 r,np& t){
auto f=expand<T,F>(op);
if(!t)t=new node();
if(r-l>1)eval(t);
if(r<=a||b<=l)return;
else if(a<=l&&r<=b)t->val=f(t->val,x);
else if(r-l>1){
update(a,b,x,l,(l+r)/2,t->ch[0]);
update(a,b,x,(l+r)/2,r,t->ch[1]);
}
}
maybe<T> get(i64 x,i64 l,i64 r,np& t){
auto f=expand<T,F>(op);
if(!t)t=new node();
if(r-l>1)eval(t);
if(x<l||r<=x)return maybe<T>();
else if(r-l==1){
return t->val;
}
else return f(get(x,l,(l+r)/2,t->ch[0]),get(x,(l+r)/2,r,t->ch[1]));
}
};#pragma once
#include"../alga/maybe.hpp"
template<typename T,typename E,typename F,typename G,typename H>
class lazy_segment_tree{
using i64=long long;
i64 n;
i64 sz;
struct node;
using np=node*;
struct node{
maybe<T> val=maybe<T>();
maybe<E> lazy=maybe<E>();
np lch=nullptr,rch=nullptr;
node(){}
};
np root=new node();
maybe<T> update(i64 a,i64 b,E x,i64 l,i64 r,np t){
auto f=expand<T,F>(_f);
eval(t,l,r);
//区間外
if(r<=a||b<=l)return t->val;
//全部区間内
if(a<=l&&r<=b){
t->lazy=x;
eval(t,l,r);
return t->val;
}
//一部区間内
return t->val=f(update(a,b,x,l,(l+r)/2,t->lch),update(a,b,x,(l+r)/2,r,t->rch));
}
maybe<T> get(i64 a,i64 b,i64 l,i64 r,np t){
auto f=expand<T,F>(_f);
eval(t,l,r);
//区間外
if(r<=a||b<=l)return maybe<T>();
//全部区間内
if(a<=l&&r<=b)return t->val;
//一部区間内
return f(get(a,b,l,(l+r)/2,t->lch),get(a,b,(l+r)/2,r,t->rch));
}
void eval(np t,i64 l,i64 r){
auto g=expand<E,G>(_g);
if(r-l>1){
if(!t->lch)t->lch=new node();
if(!t->rch)t->rch=new node();
t->lch->lazy=g(t->lch->lazy,t->lazy);
t->rch->lazy=g(t->rch->lazy,t->lazy);
}
t->val=h(t->val,t->lazy,l,r);
t->lazy=maybe<E>();
}
F _f;G _g;H _h;
maybe<T> h(const maybe<T>&s,const maybe<E>&t,int l,int r){
if(t.is_none())return s;
else return maybe<T>(_h(s,t.unwrap(),l,r));
}
public:
lazy_segment_tree(i64 sz,F f=F(),G g=G(),H h=H()):n(1),sz(sz),_f(f),_g(g),_h(h){while(n<sz)n<<=1;}
//0-indexed [a,b)
void update(i64 a,i64 b,E x){update(a,b,x,0,n,root);}
//0-indexed [a,b)
maybe<T> get(i64 a,i64 b){return get(a,b,0,n,root);}
};/**
* @brief Union Find
* @see https://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0
*/
class UF{
public:
vector<int> data;
int sz;
public:
UF(int sz):sz(sz){data.resize(sz,-1);}
bool unite(int x,int y){
x=root(x);y=root(y);
if(x==y)return 0;
if(data[x]>data[y])swap(x,y);
data[x]+=data[y];
data[y]=x;
sz--;
return 1;
}
inline int root(int x){return data[x]<0?x:data[x]=root(data[x]);}
inline bool same(int x, int y){return root(x)==root(y);}
inline int size(){return sz;}
inline int size(int x){return -data[root(x)];}
};#pragma once
#include<vector>
#include<numeric>
#include<limits>
/**
* @brief 根とのPathの中での最小値を返すUnionFind
*/
template<typename T>
struct uf_min{
constexpr static int inf=std::numeric_limits<T>::max();
std::vector<int>par,mnid;
std::vector<T>mn;
uf_min(int v){
par.resize(v);
mn.resize(v,inf);
mnid.resize(v);
std::iota(par.begin(),par.end(),0);
std::iota(mnid.begin(),mnid.end(),0);
}
int find(int v){
if(par[v]==v)return v;
int r=find(par[v]);
if(mn[v]>mn[par[v]]){
mnid[v]=mnid[par[v]];
mn[v]=mn[par[v]];
}
par[v]=r;
return r;
}
void set(int v,T x){
mn[v]=x;
}
T eval(int v){
find(v);
return mnid[v];
}
//xをyの親にする
void link(int x,int y){
par[y]=x;
}
};class UF{
public:
vector<int> data;
int sz;
public:
UF(int sz):sz(sz){
for(int i=0;i<sz;++i)data[i]=i;
}
bool unite(int x,int y){
data.swap(x,y);
return 1;
}
};template<typename T,typename F>
class UF_data{
public:
vector<int> data;
vector<T>val;
int sz;
F merge;
public:
UF_data(int sz,F merge=F()):sz(sz),merge(merge){data.resize(sz,-1);val.resize(sz,T());}
bool unite(int x,int y){
x=root(x);y=root(y);
if(x==y)return 0;
if(data[x]>data[y])swap(x,y);
data[x]+=data[y];
data[y]=x;
val[x]=merge(move(val[x]),move(val[y]));
sz--;
return 1;
}
inline void set(int x,const T&v){
x=root(x);
val[x]=v;
}
inline T get(int x){
return val[root(x)];
}
inline int root(int x){return data[x]<0?x:data[x]=root(data[x]);}
inline bool same(int x, int y){return root(x)==root(y);}
inline int size(){return sz;}
inline int size(int x){return -data[root(x)];}
};#pragma once
#include<vector>
/**
* @brief BinaryIndexedTree
*/
struct BIT{
std::vector<long long> bit;
int n;
BIT(long long n):n(n){
bit.resize(n+1,0);
}
//0-indexed [0,x)-sum
long long sum(long long x){
long long res=0;
for(int i=x;i;i-=i&-i)res+=bit[i];
return res;
}
//0-indexed [x,y)-sum
long long sum(long long x,long long y){
return sum(y)-sum(x);
}
//0-indexed
void add(long long x,long long val){
if(x>=n)return;
for(long long i=x+1;i<=n;i+=i&-i)bit[i]+=val;
}
};#bit vector
#pragma once
/**
* @brief BitVector
*/
class bitvec{
using u32=unsigned int;
using u8=unsigned char;
using lint=long long;
//4*10^6対応
//ブロック幅8,チャンク幅256
const int bw=8,cw=256;
const int len=15625,sz=4000000;
bool data[4000000]={0};
u32 chunk[15626];
u8 block[15625][33];
public:
bitvec(){}
void build(){
chunk[0]=0;
for(int i=0;i<15625;i++){
block[i][0]=0;
for(int j=0;j<31;j++){
block[i][j+1]=block[i][j];
for(int k=0;k<8;k++)block[i][j+1]+=data[i*cw+j*bw+k];
}
chunk[i+1]=chunk[i]+block[i][31];
for(int k=0;k<8;k++)chunk[i+1]+=data[i*cw+31*bw+k];
}
}
inline void set(int idx,bool b){data[idx]=b;}
inline bool get(int idx){return data[idx];}
inline int rank(int idx,bool b)const{
if(b)return rank1(idx);
else return idx-rank1(idx);
}
inline int rank1(int idx)const{
int a=idx/cw,b=idx%cw/bw,c=idx%bw;
int res=chunk[a]+block[a][b];
for(int i=1;i<c+1;i++)res+=data[idx-i];
return res;
}
inline int select(int num){
if (num==0)return 0;
if (rank1(sz)<num)return -1;
int ok=sz,ng=0;
while (ok-ng>1) {
int mid=(ok+ng)/2;
if (rank1(mid)>=num)ok =mid;
else ng=mid;
}
return ok;
}
};