OI模板-数据结构
笛卡尔树
笛卡尔树满足
- 每个节点的编号满足二叉搜索树的性质。
- 节点 $i$ 的权值为 $p_i$，每个节点的权值满足小根堆的性质。
构建的复杂度为 $\mathcal{O}(n)$
// 2024年06月13日 22:24:45
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e7 + 15))
int n, top, a[N], ls[N], rs[N], stk[N];
void build()
{
for(int i = 1; i <= n; i++)
{
int tmp = top;
while(top > 0 && a[stk[top]] > a[i]) --top;
if(top > 0) rs[stk[top]] = i; // a[stk[top]] <= a[i]
if(top < tmp) ls[i] = stk[top + 1]; // a[stk[top + 1]] > a[i]
stk[++top] = i;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
build(); ll res1 = 0, res2 = 0;
for(int i = 1; i <= n; i++)
{
res1 ^= (ll)i * (ls[i] + 1);
res2 ^= (ll)i * (rs[i] + 1);
}
cout << res1 << ' ' << res2 << '\n';
return 0;
}并查集
具@Roundgod老师说
按秩合并+路径压缩才能保证并查集查询的复杂度为 $O(\alpha(n))$
只用一个就是 $O(\log n)$ 的，不过要特意构造数据卡才会到这个上界
基于子树大小的按秩合并：
void init(int n){for(int i=1; i<=n; i++) f[i]=i,sz[i]=1;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int u,int v)
{
int x=find(u),y=find(v);
if(sz[x] > sz[y]) swap(x,y);
f[x]=y; sz[y] += sz[x];
}基于深度的按秩合并：
int f[N],r[N]; // r[] 为深度
void init(int n){for(int i=1; i<=n; i++) f[i]=i,r[i]=0;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int x,int y)
{
x=find(x); y=find(y);
if(x==y) return;
if(r[x]<r[y]) f[x]=y;
else f[y]=x,r[x]+=r[x]==r[y];
}种类并查集
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e4+15)
int n,Q,f[N<<2];
void init(int n){for(int i=1; i<=n; i++) f[i]=i;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int u,int v){f[find(u)]=find(v);}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> Q;
int res=0; init(3*n);
for(int op,x,y; Q--;)
{
cin >> op >> x >> y;
if(x>n||y>n){++res; continue;}
if(op==1)
{
if(find(x)==find(y+n)||find(x)==find(y+2*n)){++res; continue;}
merge(x,y); merge(x+n,y+n); merge(x+2*n,y+2*n);
}else
{
if(find(x)==find(y)||find(x)==find(y+n)){++res; continue;}
merge(x,y+2*n); merge(x+n,y); merge(x+2*n,y+n);
}
}
cout << res << '\n';
return 0;
}
带权并查集
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e5+15)
char op;
int n,f[N],sz[N],d[N];
void init(int n)
{
for(int i=1; i<=n; i++)
f[i]=i, sz[i]=1, d[i]=0;
}
int find(int x)
{
if(f[x] == x)return x;
int top = find(f[x]);
d[x] += d[f[x]]; sz[x] = sz[top];
return f[x]=top;
}
void merge(int u,int v)
{
u=find(u); v=find(v);
f[u] = v; d[u] += sz[v];
sz[u] = sz[v] += sz[u];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n; init(n);
for(int i=1,x,y; i<=n; i++)
{
cin >> op >> x >> y;
if(op=='M') merge(x,y);
else
{
if(find(x)!=find(y))cout << "-1\n";
else cout << abs(d[x]-d[y])-1 << '\n';
}
}
return 0;
}线性基
板子题：LOJ113 最大异或和 | LOJ114 k 大异或和
未经过严格检查的代码
最大值1个log，k大值2个log
时间复杂度 $O((n+q)\log^2 a_i)$
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(66))
const int mx = 51;
int n,ck,a[N],tmp[N],o[N];
void insert(int x)
{
for(int i=mx; i>=0; i--)
if((x >> i) & 1)
{
if(!a[i]) { a[i]=x; return; }
else x ^= a[i];
}
ck=1;
}
int qmax(int res=0)
{
for(int i=mx; i>=0; i--) up(res, res^a[i]);
return res;
}
int qmin()
{
if(ck) return 0;
for(int i=0; i<=mx; i++)
if(a[i]) return a[i];
return INF;
}
int kth(int k)
{
int res=0, cnt=0;
k-=ck; if(!k) return 0;
for(int i=0; i<=mx; i++)
{
for(int j=i-1; j>=0; j--)
if((a[i] >> j) & 1) a[i] ^= a[j];
if(a[i]) o[cnt++]=a[i];
}
if(k >= (1ll << cnt)) return -1;
for(int i=0; i<cnt; i++) if((k >> i) & 1) res ^= o[i];
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i=1,x; i<=n; i++) cin >> x, insert(x);
int Q,k; cin >> Q; while(Q--) cin >> k, cout << kth(k) << '\n';
return 0;
}单调队列
时间复杂度 $O(n)$
空间复杂度 $O(n)$
手写版本（20220514）
队列用的 (l,r] 写法
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(1e6+15)
int n,k,a[N],st,en,q[N];
void solve(int n,int len,int f)
{
st=en=0;
for(int i=1; i<=n; i++)
{
if(f==1)while(st<en&&a[i]<a[q[en]])--en;
if(f==2)while(st<en&&a[i]>a[q[en]])--en;
q[++en]=i;
while(st<en&&q[st+1]+len<=i)++st;
if(i>=len)write(a[q[st+1]]),pc(" \n"[i==n]);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
read(n);read(k);
for(int i=1; i<=n; i++)
read(a[i]);
solve(n,k,1); // min
solve(n,k,2); // max
return 0;
}stl版本（20211022）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
#define MAXN (int)(1e6+5)
template<typename T>inline void read(T &k)
{char ch=gc();T x=0,f=1;while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}k=x*f;}
template<typename T>inline void write(T k)
{if(k<0){k=-k;pc('-');}if(k>9)write(k/10);pc(k%10+'0');}
struct node
{
int id,num; // 下标，数
};
int n,k;
int a[MAXN];
deque<node> q1,q2;
signed main()
{
read(n);read(k);
for(int i=1; i<=n; i++)
read(a[i]);
for(int i=1; i<=n; i++) // min
{
while(!q1.empty()&&a[i]<q1.back().num)q1.pop_back();
q1.push_back({i,a[i]});
while(!q1.empty()&&q1.front().id<=i-k)q1.pop_front();
if(i>=k){write(q1.front().num);pc(" \n"[i==n]);}
}
for(int i=1; i<=n; i++) // max
{
while(!q2.empty()&&a[i]>q2.back().num)q2.pop_back();
q2.push_back({i,a[i]});
while(!q2.empty()&&q2.front().id<=i-k)q2.pop_front();
if(i>=k){write(q2.front().num);pc(" \n"[i==n]);}
}
return 0;
}二叉堆
时间复杂度 $O(n\log n)$
空间复杂度 $O(m^2)$
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
// #define int long long
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(2e6+15)
int n,d[N],pos;
void push(int x)
{
for(int f=x>>1;f>0&&d[f]>d[x];swap(d[f],d[x]),x=f,f>>=1);
}
void pop(int x)
{
for(int s=x<<1; s<=pos;)
{
if(s<pos&&d[s]>d[s|1])s|=1; // 左右中最大的
if(d[x]>d[s])swap(d[x],d[s]),x=s,s<<=1; // 去掉中间的
else break;
}
}
signed main()
{
read(n);
for(int i=1; i<=n; i++)
{
int op,x;read(op);
if(op==1){read(x);d[++pos]=x;push(pos);}
if(op==2){write(d[1]);pc('\n');}
if(op==3){swap(d[1],d[pos]);--pos;pop(1);}
}
return 0;
}左偏树（可并堆）
时间复杂度 $O(n\log n)$
写法1
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(1e5+15)
int n,m;
int ls[N],rs[N],del[N],dist[N],rt[N];
struct node
{
int num,id;
bool operator<(node &o)const
{
if(num==o.num)return id<o.id;
return num<o.num;
}
}v[N];
int merge(int x,int y)
{
if(!x||!y)return x|y;
if(v[y]<v[x])swap(x,y);
rs[x]=merge(rs[x],y);
if(dist[rs[x]]>dist[ls[x]])swap(ls[x],rs[x]);
dist[x]=dist[rs[x]]+1;
return x;
}
int find(int x){return rt[x]==x?x:rt[x]=find(rt[x]);}
signed main()
{
read(n);read(m);
for(int i=1; i<=n; i++)
{
read(v[i].num);
v[i].id=i;rt[i]=i;
}
while(m--)
{
int op,x,y;
read(op);read(x);
if(op==1)
{
read(y);
if(del[x]||del[y])continue;
x=find(x);y=find(y);
if(x!=y)rt[x]=rt[y]=merge(x,y);
}else
{
if(del[x]){puts("-1");continue;}
x=find(x);del[x]=1;
write(v[x].num);pc('\n');
rt[ls[x]]=rt[rs[x]]=rt[x]=merge(ls[x],rs[x]);
ls[x]=rs[x]=dist[x]=0; // 这句可以不写，这样最多就安全一点（？
}
}
return 0;
}写法2（封装）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(1e5+15)
#define ls(at) t[at].ch[0]
#define rs(at) t[at].ch[1]
int n,m;
struct node
{
int ch[2],num,id,del,dist,rt;
bool operator<(node &o)const
{
if(num==o.num)return id<o.id;
return num<o.num;
}
}t[N];
int merge(int x,int y)
{
if(!x||!y)return x|y;
if(t[y]<t[x])swap(x,y);
rs(x)=merge(rs(x),y);
if(t[rs(x)].dist>t[ls(x)].dist)swap(ls(x),rs(x));
t[x].dist=t[rs(x)].dist+1;
return x;
}
int find(int x)
{
return t[x].rt==x?x:t[x].rt=find(t[x].rt);
}
signed main()
{
read(n);read(m);
for(int i=1; i<=n; i++)
{
read(t[i].num);
t[i].id=i;t[i].rt=i;
}
while(m--)
{
int op,x,y;
read(op);read(x);
if(op==1)
{
read(y);
if(t[x].del||t[y].del)continue;
x=find(x);y=find(y);
if(x!=y)t[x].rt=t[y].rt=merge(x,y);
}else
{
if(t[x].del){puts("-1");continue;}
x=find(x);t[x].del=1;
write(t[x].num);pc('\n');
t[ls(x)].rt=t[rs(x)].rt=t[x].rt=merge(ls(x),rs(x));
}
}
return 0;
}珂朵莉树
CF896C Willem, Chtholly and Seniorious
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define mod (int)(1e9+7)
#define MAXN (int)(1e5+5)
int n,m,seed,vmax;
int qpow(R int a,R int b,R int p)
{
R int ans=1,base=a;
while(b)
{
if(b&1)ans=(ans%p*base%p)%p;
base=(base%p*base%p)%p;
b>>=1;
}
return ans%p;
}
struct node
{
int l,r;
mutable int v;
const bool operator<(const node &o)const
{
return l<o.l;
}
};
int rnd()
{
R int ret=seed;
seed=(seed*7+13)%mod;
return ret;
}
int a[MAXN];
set<node> s;
set<node>::iterator split(R int pos)
{
set<node>::iterator it=s.lower_bound({pos});
if(it!=s.end()&&it->l==pos) return it;
it--;
if(it->r<pos)return s.end();
R int l=it->l,r=it->r,v=it->v;
s.erase(it);
s.insert({l,pos-1,v});
return s.insert({pos,r,v}).first;
}
inline void add(R int l,R int r,R int k)
{
set<node>::iterator itr=split(r+1),itl=split(l);
for(R set<node>::iterator it=itl; it!=itr; it++)
it->v+=k;
}
inline void assign(R int l,R int r,R int k)
{
set<node>::iterator itr=split(r+1),itl=split(l);
s.erase(itl,itr);//[itl,itr)
s.insert({l,r,k});
}
struct Rank
{
int num,cnt;
const bool operator<(const Rank &o)const
{
return num<o.num;
}
};
inline int rnk(R int l,R int r,R int k)
{
set<node>::iterator itr=split(r+1),itl=split(l);
vector<Rank> v;
for(R set<node>::iterator it=itl; it!=itr; it++)
v.push_back({it->v,it->r - it->l +1});
sort(v.begin(),v.end());
for(R int i=0; i<v.size(); i++)
if(v[i].cnt<k)k-=v[i].cnt;
else return v[i].num;
return -1;
}
inline int calP(R int l,R int r,R int x,R int y)
{
R int ans=0;
set<node>::iterator itr=split(r+1),itl=split(l);
for(set<node>::iterator it=itl; it!=itr; it++)
ans=(ans%y+qpow(it->v,x,y)%y*(it->r - it->l +1)%y)%y;
return ans;
}
signed main()
{
scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
for(R int i=1; i<=n; i++)
{
a[i]=(rnd()%vmax)+1;
s.insert({i,i,a[i]});
}
for(R int i=1; i<=m; i++)
{
R int op,l,r,x,y;
///
op=(rnd()%4)+1;
l=(rnd()%n)+1;
r=(rnd()%n)+1;
if(l>r)swap(l,r);
if(op==3){x=(rnd()%(r-l+1))+1;}
else {x=(rnd()%vmax)+1;}
if(op==4){y=(rnd()%vmax)+1;}
///
if(op==1)
add(l,r,x);
else if(op==2)
assign(l,r,x);
else if(op==3)
printf("%lld\n",rnk(l,r,x));
else printf("%lld\n",calP(l,r,x,y));
}
return 0;
}平衡树
FHQ_Treap
时间复杂度 $O(n\log n)$
空间复杂度 $O(n)$
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
#define gc() getchar()
#define pc(a) putchar(a)
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n;
namespace FHQ_Treap
{
struct node
{
int ch[2],num,rnd,sz;
}t[N];
int tot,rt;
mt19937_64 rd(time(0));
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
void push_up(int x)
{
t[x].sz=t[ls(x)].sz+t[rs(x)].sz+1;
}
int New(int x)
{
t[++tot]={0,0,x,(int)rd(),1};
return tot;
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
if(t[x].rnd<t[y].rnd)
{
rs(x)=merge(rs(x),y);
push_up(x);return x;
}else
{
ls(y)=merge(x,ls(y));
push_up(y);return y;
}
}
void split(int at,int k,int &x,int &y)
{
if(!at)x=y=0;
else
{
if(t[at].num<=k)
x=at,split(rs(at),k,rs(at),y);
else
y=at,split(ls(at),k,x,ls(at));
push_up(at);
}
}
int kth(int at,int x)
{
while(1)
{
if(x<=t[ls(at)].sz)
at=ls(at);
else if(x==t[ls(at)].sz+1)
return at;
else
{
x-=t[ls(at)].sz+1;
at=rs(at);
}
}
}
void insert(int a)
{
int x,y;
split(rt,a,x,y);
rt=merge(merge(x,New(a)),y);
}
void remove(int a)
{
int x,y,z;
split(rt,a,x,z);
split(x,a-1,x,y);
y=merge(ls(y),rs(y));
rt=merge(merge(x,y),z);
}
void getrank(int a)
{
int x,y;
split(rt,a-1,x,y);
write(t[x].sz+1);pc('\n');
rt=merge(x,y);
}
void getkth(int a)
{
write(t[kth(rt,a)].num);
pc('\n');
}
void getpre(int a)
{
int x,y;
split(rt,a-1,x,y);
if(!x)write(-INF);
else write(t[kth(x,t[x].sz)].num);
pc('\n');rt=merge(x,y);
}
void getnext(int a)
{
int x,y;
split(rt,a,x,y);
if(!y)write(INF);
else write(t[kth(y,1)].num);
pc('\n');rt=merge(x,y);
}
}
signed main()
{
using namespace FHQ_Treap;
read(n);
for(int i=1,op,a; i<=n; i++)
{
read(op);read(a);
if(op==1){insert(a);}
if(op==2){remove(a);}
if(op==3){getrank(a);}
if(op==4){getkth(a);}
if(op==5){getpre(a);}
if(op==6){getnext(a);}
}
}替罪羊树
小常数还好写
时间复杂度 $O(n\log n)$
空间复杂度 $O(n)$
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
namespace BT
{
#define N (int)(1e5+15)
struct node
{
int ch[2],num,cnt,s,sz,sd;
}t[N];
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
double alpha=0.7;
int tot,rt;
int tmp[N];
int New(int x)
{
t[++tot]={0,0,x,1,1,1,1};
return tot;
}
void push_up(int at)
{
t[at].s=t[ls(at)].s+t[rs(at)].s+1;
t[at].sz=t[ls(at)].sz+t[rs(at)].sz+t[at].cnt;
t[at].sd=t[ls(at)].sd+t[rs(at)].sd+(t[at].cnt!=0);
}
bool CanR(int at)
{
double x=t[at].s*alpha;
return (t[at].cnt)&&(x<=(double)max(t[ls(at)].s,t[rs(at)].s)||
(double)t[at].sd<=x);
}
void CanR_flatten(int &idx,int at)
{
if(!at)return;
CanR_flatten(idx,ls(at));
if(t[at].cnt)tmp[++idx]=at;
CanR_flatten(idx,rs(at));
}
int CanR_build(int l,int r)
{
if(l>=r)return 0;
int mid=(l+r)>>1;
int &at=tmp[mid];
ls(at)=CanR_build(l,mid);
rs(at)=CanR_build(mid+1,r);
push_up(at);
return at;
}
void rebuild(int &at)
{
int idx=0;
CanR_flatten(idx,at);
at=CanR_build(1,idx+1);
}
void insert(int x,int &at)
{
if(!at){at=New(x);return;}
if(t[at].num==x)++t[at].cnt;
else if(x<t[at].num)insert(x,ls(at));
else insert(x,rs(at));
push_up(at);
if(CanR(at))rebuild(at);
}
void remove(int x,int &at)
{
if(!at)return;
if(t[at].num==x)
{
if(t[at].cnt)--t[at].cnt;
}else if(x<t[at].num)remove(x,ls(at));
else remove(x,rs(at));
push_up(at);
if(CanR(at))rebuild(at);
}
int getval(int x,int at)
{
if(!at)return INF;
if(x<=t[ls(at)].sz)return getval(x,ls(at));
if(x<=t[ls(at)].sz+t[at].cnt)return t[at].num;
else return getval(x-t[ls(at)].sz-t[at].cnt,rs(at));
}
int uprbd(int x,int at)
{
if(!at)return 1;
if(x==t[at].num&&t[at].cnt)return t[ls(at)].sz+t[at].cnt+1;
else if(x<t[at].num)return uprbd(x,ls(at));
else return uprbd(x,rs(at))+t[ls(at)].sz+t[at].cnt;
}
int uprbd_gt(int x,int at)
{
if(!at)return 0;
if(x==t[at].num&&t[at].cnt)return t[ls(at)].sz;
else if(x<t[at].num)return uprbd_gt(x,ls(at));
else return uprbd_gt(x,rs(at))+t[ls(at)].sz+t[at].cnt;
}
int getpre(int x,int at){return getval(uprbd_gt(x,at),at);}
int getnext(int x,int at){return getval(uprbd(x,at),at);}
}
signed main()
{
using namespace BT;
int n;read(n);
for(int i=1; i<=n; i++)
{
int op,x;
read(op);read(x);
if(op==1)insert(x,rt);
if(op==2)remove(x,rt);
if(op==3){write(uprbd_gt(x,rt)+1);pc('\n');}
if(op==4){write(getval(x,rt));pc('\n');}
if(op==5){write(getpre(x,rt));pc('\n');}
if(op==6){write(getnext(x,rt));pc('\n');}
}
return 0;
}Splay
大常数
时间复杂度 $O(n\log n)$
空间复杂度 $O(n)$
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gc() getchar()
#define pc(a) putchar(a)
#define INF 0x3f3f3f3f3f3f3f3f
#define MAXN (int)(1e5+5)
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n;
namespace Splay
{
struct node
{
int ch[2],num,fa,cnt,sz;
}t[MAXN];
int tot,rt;
int New(int x,int f)
{
t[++tot]={0,0,x,f,1,1};
if(f)t[f].ch[x>t[f].num]=tot;
return tot;
}
void push_up(int at)
{
t[at].sz=t[t[at].ch[0]].sz
+t[t[at].ch[1]].sz+t[at].cnt;
}
void rotate(int x)
{
int y=t[x].fa;
int z=t[y].fa;
int k=t[y].ch[1]==x;
t[z].ch[t[z].ch[1]==y]=x;
t[x].fa=z;
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].fa=y;
t[x].ch[k^1]=y;
t[y].fa=x;
push_up(y);
push_up(x);
}
void splay(int x,int goal)
{
while(t[x].fa!=goal)
{
int y=t[x].fa;
int z=t[y].fa;
if(z!=goal)
(t[y].ch[1]==x)^(t[z].ch[1]==y)?rotate(x):rotate(y);
rotate(x);
}
if(!goal)rt=x;
}
void find(int x)
{
int at=rt;
if(!at)return;
while(t[at].ch[x>t[at].num]&&x!=t[at].num)
at=t[at].ch[x>t[at].num];
splay(at,0);
}
int get(int x,int f)
{
find(x);
int at=rt;
if(t[at].num<x&&!f)return at;
if(t[at].num>x&&f)return at;
at=t[at].ch[f];
while(t[at].ch[f^1])at=t[at].ch[f^1];
return at;
}
void insert(int x)
{
int at=rt,f=0;
while(at&&x!=t[at].num)
f=at,at=t[at].ch[x>t[at].num];
if(at)++t[at].cnt;
else at=New(x,f);
splay(at,0);
}
void remove(int x)
{
int pre=get(x,0);
int nxt=get(x,1);
splay(pre,0);splay(nxt,pre);
int &del=t[nxt].ch[0];
if(t[del].cnt>1)
{
--t[del].cnt;
splay(del,0);
}else del=0;
}
int kth(int x)
{
int at=rt;
if(t[at].sz<x)
return INF;
while(1)
{
int p=t[at].ch[0];
if(x>t[p].sz+t[at].cnt)
{
x-=t[p].sz+t[at].cnt;
at=t[at].ch[1];
}else
{
if(x<=t[p].sz)
at=p;
else return t[at].num;
}
}
}
}
signed main()
{
using namespace Splay;
insert(-INF);
insert(INF);
read(n);
for(int i=1; i<=n; i++)
{
int op,x;
read(op);read(x);
if(op==1){insert(x);}
if(op==2){remove(x);}
if(op==3){find(x);write(t[t[rt].ch[0]].sz);pc('\n');}
if(op==4){write(kth(x+1));pc('\n');}
if(op==5){write(t[get(x,0)].num);pc('\n');}
if(op==6){write(t[get(x,1)].num);pc('\n');}
}
return 0;
}文艺平衡树
采用 Splay ，支持区间翻转。其实就是在原基础上打个标记而已。
// 2024年06月08日 16:36:55
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
int n;
namespace Splay
{
int tot, rt;
#define ls(at) t[at].ch[0]
#define rs(at) t[at].ch[1]
struct node { int ch[2], num, fa, cnt, sz, tag; } t[N];
int New(int x, int f)
{
t[++tot] = {0, 0, x, f, 1, 1, 0};
if(f) t[f].ch[x > t[f].num] = tot;
return tot;
}
void push_up(int at) {
t[at].sz = t[ls(at)].sz + t[rs(at)].sz + t[at].cnt;
}
void push_down(int at)
{
if(t[at].tag)
{
if(ls(at)) t[ls(at)].tag ^= 1;
if(rs(at)) t[rs(at)].tag ^= 1;
t[at].tag = 0; swap(ls(at), rs(at));
}
}
void rotate(int x)
{
int y = t[x].fa, z = t[y].fa, k = rs(y) == x;
t[z].ch[rs(z) == y] = x; t[x].fa = z;
t[y].ch[k] = t[x].ch[k ^ 1]; t[t[x].ch[k ^ 1]].fa = y;
t[x].ch[k ^ 1] = y; t[y].fa = x;
push_up(y); push_up(x);
}
void splay(int x, int goal)
{
while(t[x].fa != goal)
{
int y = t[x].fa, z = t[y].fa;
push_down(z); push_down(y); push_down(x);
if(z != goal) ((rs(y) == x) ^ (rs(z) == y)) ? rotate(x) : rotate(y);
rotate(x);
}
if(!goal) rt = x;
}
void insert(int x)
{
int at = rt, f = 0;
while(at && x != t[at].num) {
f = at; at = t[at].ch[x > t[at].num];
}
if(at) ++t[at].cnt; else at = New(x, f);
splay(at, 0);
}
int kth(int x)
{
int at = rt; if(t[at].sz < x) return INF;
while(1)
{
push_down(at); int p = ls(at);
if(x > t[p].sz + t[at].cnt)
{
x -= t[p].sz + t[at].cnt;
at = t[at].ch[1];
}else
{
if(x <= t[p].sz) at = p;
else return t[at].num;
}
}
}
}using namespace Splay;
void work(int l, int r)
{
l = kth(l); r = kth(r + 2);
splay(l, 0); splay(r, l);
t[ls(rs(rt))].tag ^= 1;
}
void output(int at)
{
push_down(at);
if(ls(at)) output(ls(at));
if(t[at].num > 1 && t[at].num < n + 2) cout << t[at].num - 1 << ' ';
if(rs(at)) output(rs(at));
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int q; cin >> n >> q;
for(int i = 1; i <= n + 2; i++) insert(i);
while(q--) { int l, r; cin >> l >> r; work(l, r); }
return output(rt), 0;
}可持久化平衡树
采用FHQ_Treap
时间复杂度 $O(n\log n)$
空间复杂度 $O(n\log n)$
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e5+15)
#define gc() getchar()
#define pc(a) putchar(a)
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n;
namespace FHQ_Treap
{
struct node
{
int ch[2],num,rnd,sz;
}t[N*50];
int tot,T[N];
mt19937_64 rd(time(0));
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
void push_up(int x)
{
t[x].sz=t[ls(x)].sz+t[rs(x)].sz+1;
}
int New(int x)
{
t[++tot]={0,0,x,(int)rd(),1};
return tot;
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
if(t[x].rnd<t[y].rnd)
{
int p=++tot;t[p]=t[x];
rs(p)=merge(rs(p),y);
push_up(p);return p;
}else
{
int p=++tot;t[p]=t[y];
ls(p)=merge(x,ls(p));
push_up(p);return p;
}
}
void split(int at,int k,int &x,int &y)
{
if(!at)x=y=0;
else
{
if(t[at].num<=k)
{
x=++tot;t[x]=t[at];
split(rs(x),k,rs(x),y);
push_up(x);
}
else
{
y=++tot;t[y]=t[at];
split(ls(y),k,x,ls(y));
push_up(y);
}
}
}
int kth(int at,int x)
{
while(1)
{
if(x<=t[ls(at)].sz)
at=ls(at);
else if(x==t[ls(at)].sz+1)
return at;
else
{
x-=t[ls(at)].sz+1;
at=rs(at);
}
}
}
void insert(int a,int &rt)
{
int x,y;
split(rt,a,x,y);
rt=merge(merge(x,New(a)),y);
}
void remove(int a,int &rt)
{
int x,y,z;
split(rt,a,x,z);
split(x,a-1,x,y);
y=merge(ls(y),rs(y));
rt=merge(merge(x,y),z);
}
void getrank(int a,int &rt)
{
int x,y;
split(rt,a-1,x,y);
write(t[x].sz+1);pc('\n');
rt=merge(x,y);
}
void getkth(int a,int &rt)
{
write(t[kth(rt,a)].num);
pc('\n');
}
void getpre(int a,int &rt)
{
int x,y;
split(rt,a-1,x,y);
if(!x)write(-2147483647+1);
else write(t[kth(x,t[x].sz)].num);
pc('\n');rt=merge(x,y);
}
void getnext(int a,int &rt)
{
int x,y;
split(rt,a,x,y);
if(!y)write(2147483647-1);
else write(t[kth(y,1)].num);
pc('\n');rt=merge(x,y);
}
}
signed main()
{
using namespace FHQ_Treap;
read(n);
for(int i=1,op,a,now; i<=n; i++)
{
read(now);read(op);read(a);
T[i]=T[now];
if(op==1){insert(a,T[i]);}
if(op==2){remove(a,T[i]);}
if(op==3){getrank(a,T[i]);}
if(op==4){getkth(a,T[i]);}
if(op==5){getpre(a,T[i]);}
if(op==6){getnext(a,T[i]);}
}
}ST表
一定要预处理 $\log_2 n$ ！！ 不然查询的复杂度是假的！
因为 log() 函数的复杂度不超过log级，但是常数大！
时间复杂度 $O(n\log n)$
空间复杂度 $O(n\log n)$
代码1：
// 2023年04月02日 14:00:16
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
int n,Q,lg[N],st[18][N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> Q;
for(int i = 1; i <= n; i++) cin >> st[0][i];
for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for(int j = 0; 1 << (j + 1) <= n; j++)
{
int *f = st[j], *g = st[j + 1];
for(int i = 1; i + (1 << j) - 1 <= n; i++)
g[i] = max(f[i], f[i + (1 << j)]);
}
for(int l,r; Q--; )
{
cin >> l >> r; int k = lg[r - l + 1]; // 这里写 r - l 也是可以的
cout << max(st[k][l], st[k][r - (1 << k) + 1]) << '\n';
}
return 0;
}代码2：
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(1e5+5)
int n,m,lg[N],f[N][21];
void change(int u,int x)
{
f[u][0]=x;
for(int i=1; u>=(1<<i); i++)
f[u][i]=max(f[u][i-1],f[u-(1<<(i-1))][i-1]);
}
int query(int l,int r)
{
int k=lg[r-l+1];
return max(f[l+(1<<k)-1][k],f[r][k]);
}
signed main()
{
read(n);read(m);
for(int i=1,x; i<=n; i++)
{
read(x); change(i,x);
lg[i]=(double)log(i)/log(2);
}
for(int i=1,l,r; i<=m; i++)
{
read(l);read(r);
write(query(l,r));pc('\n');
}
return 0;
}树链剖分
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(1e5+5)
struct Edge
{
int u,v,next;
}e[N<<2];
int pos=1,n,Q,rt,p,head[N];
int id[N],idx,t[N],a[N],fa[N],son[N];
int sz[N],top[N],ans[N<<2],tag[N<<2],dep[N];
void addEdge(int u,int v)
{
e[pos]={u,v,head[u]};
head[u]=pos++;
}
void dfs(int u,int f,int d)
{
fa[u]=f;
sz[u]=1;
dep[u]=d;
int mx=-1;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(v==f)continue;
dfs(v,u,d+1);
sz[u]+=sz[v];
if(sz[v]>mx)mx=sz[v],son[u]=v;
}
}
void dfs(int u,int ftop)
{
id[u]=++idx;
top[u]=ftop;
a[idx]=t[u];
if(!son[u])return;
dfs(son[u],ftop);
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(v==fa[u]||v==son[u])continue;
dfs(v,v);
}
}
void push_up(int at)
{ans[at]=ans[at<<1]+ans[at<<1|1];}
void proc(int l,int r,int at)
{
int u=at>>1;
ans[at]=(ans[at]+tag[u]*(r-l+1)%p)%p;
tag[at]=(tag[at]+tag[u])%p;
}
void push_down(int l,int r,int at)
{
int mid=(l+r)>>1;
proc(l,mid,at<<1);
proc(mid+1,r,at<<1|1);
tag[at]=0;
}
void build(int l,int r,int at)
{
tag[at]=0;
if(l==r){ans[at]=a[l];return;}
int mid=(l+r)>>1;
build(l,mid,at<<1);
build(mid+1,r,at<<1|1);
push_up(at);
}
void update(int nl,int nr,int l,int r,int k,int at)
{
if(nl<=l&&r<=nr)
{
ans[at]=(ans[at]+k%p*(r-l+1)%p)%p;
tag[at]=(tag[at]+k)%p;
return;
}
push_down(l,r,at);
int mid=(l+r)>>1;
if(nl<=mid)update(nl,nr,l,mid,k,at<<1);
if(nr>mid)update(nl,nr,mid+1,r,k,at<<1|1);
push_up(at);
}
int query(int nl,int nr,int l,int r,int at)
{
int res=0;
if(nl<=l&&r<=nr)
{return ans[at]%p;}
int mid=(l+r)>>1;
push_down(l,r,at);
if(nl<=mid)res=(res+query(nl,nr,l,mid,at<<1))%p;
if(nr>mid)res=(res+query(nl,nr,mid+1,r,at<<1|1))%p;
return res;
}
void upRange(int x,int y,int k)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(id[top[x]],id[x],1,n,k,1);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(id[x],id[y],1,n,k,1);
}
int qRange(int x,int y)
{
int res=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
res=(res+query(id[top[x]],id[x],1,n,1))%p;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
res=(res+query(id[x],id[y],1,n,1))%p;
return res;
}
void upSon(int x,int k){update(id[x],id[x]+sz[x]-1,1,n,k,1);}
int qSon(int x){return query(id[x],id[x]+sz[x]-1,1,n,1)%p;}
signed main()
{
read(n);read(Q);read(rt);read(p);
for(int i=1; i<=n; i++)
read(t[i]);
for(int i=1,u,v; i<n; i++)
{
read(u);read(v);
addEdge(u,v);addEdge(v,u);
}
dfs(rt,0,1);
dfs(rt,rt);
build(1,n,1);
while(Q--)
{
int op,x,y,k;
read(op);
if(op==1)
{
read(x);read(y);read(k);
upRange(x,y,k);
}
if(op==2)
{
read(x);read(y);
write(qRange(x,y));pc('\n');
}
if(op==3)
{
read(x);read(k);
upSon(x,k);
}
if(op==4)
{
read(x);
write(qSon(x));pc('\n');
}
}
return 0;
}树套树
1. 位置线段树套权值平衡树
注意二分的方向
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 2147483647
// #define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(1e5+15)
int n,Q,a[N];
namespace BT
{
struct node
{
int ch[2],num,cnt,s,sz,sd;
}t[N*35];
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
const double alpha=0.75;
int tot,rt,tmp[N*35];
int New(int x)
{
t[++tot]={0,0,x,1,1,1,1};
return tot;
}
void push_up(int at)
{
t[at].s=t[ls(at)].s+t[rs(at)].s+1;
t[at].sz=t[ls(at)].sz+t[rs(at)].sz+t[at].cnt;
t[at].sd=t[ls(at)].sd+t[rs(at)].sd+(t[at].cnt!=0);
}
bool CanR(int at)
{
double x=t[at].s*alpha;
return (t[at].cnt)
&&(x<=(double)max(t[ls(at)].s,t[rs(at)].s)||(double)t[at].sd<=x);
}
void CanR_flatten(int &idx,int at)
{
if(!at)return;
CanR_flatten(idx,ls(at));
if(t[at].cnt)tmp[++idx]=at;
CanR_flatten(idx,rs(at));
}
int CanR_build(int l,int r)
{
if(l>=r)return 0;
int mid=(l+r)>>1;
int &at=tmp[mid];
ls(at)=CanR_build(l,mid);
rs(at)=CanR_build(mid+1,r);
push_up(at);
return at;
}
void rebuild(int &at)
{
int idx=0;
CanR_flatten(idx,at);
at=CanR_build(1,idx+1);
}
void insert(int x,int &at)
{
if(!at){at=New(x);return;}
if(t[at].num==x)++t[at].cnt;
else if(x<t[at].num)insert(x,ls(at));
else insert(x,rs(at));
push_up(at);
if(CanR(at))rebuild(at);
}
void remove(int x,int &at)
{
if(!at)return;
if(t[at].num==x)
{
if(t[at].cnt)--t[at].cnt;
}else if(x<t[at].num)remove(x,ls(at));
else remove(x,rs(at));
push_up(at);
if(CanR(at))rebuild(at);
}
int getval(int x,int at)
{
if(!at)return INF;
if(x<=t[ls(at)].sz)return getval(x,ls(at));
if(x<=t[ls(at)].sz+t[at].cnt)return t[at].num;
else return getval(x-t[ls(at)].sz-t[at].cnt,rs(at));
}
int uprbd(int x,int at)
{
if(!at)return 1;
if(x==t[at].num&&t[at].cnt)return t[ls(at)].sz+t[at].cnt+1;
else if(x<t[at].num)return uprbd(x,ls(at));
else return uprbd(x,rs(at))+t[ls(at)].sz+t[at].cnt;
}
int uprbd_gt(int x,int at)
{
if(!at)return 0;
if(x==t[at].num&&t[at].cnt)return t[ls(at)].sz;
else if(x<t[at].num)return uprbd_gt(x,ls(at));
else return uprbd_gt(x,rs(at))+t[ls(at)].sz+t[at].cnt;
}
int getpre(int x,int at)
{
int res=getval(uprbd_gt(x,at),at);
return res==INF?-INF:res;
}
int getnext(int x,int at)
{
int res=getval(uprbd(x,at),at);
return res==INF?INF:res;
}
}
namespace SEG
{
struct node
{
int l,r,rt;
}s[N<<2];
#define lc(at) (at<<1)
#define rc(at) (at<<1|1)
void build(int l,int r,int at)
{
s[at].l=l;s[at].r=r;
for(int i=l; i<=r; i++)
BT::insert(a[i],s[at].rt);
if(l==r)return;
int mid=(l+r)>>1;
build(l,mid,lc(at));
build(mid+1,r,rc(at));
}
void update(int pos,int k,int at)
{
BT::remove(a[pos],s[at].rt);
BT::insert(k,s[at].rt);
if(s[at].l==s[at].r)return;
int mid=(s[at].l+s[at].r)>>1;
if(pos<=mid)update(pos,k,lc(at));
else update(pos,k,rc(at));
}
int getrank(int L,int R,int k,int at)
{
int l=s[at].l,r=s[at].r;
if(l>R||r<L)return 0;
if(L<=l&&r<=R)return BT::uprbd_gt(k,s[at].rt);
return getrank(L,R,k,lc(at))+getrank(L,R,k,rc(at));
}
// a=getrank(x),b=getrank(y)
// a=b => x=y
// x=y =/> a=b
// int getkth(int L,int R,int k)
// {
// int l=0,r=1e8+5;
// while(l<r)
// {
// int mid=(l+r)>>1;
// if(getrank(L,R,mid,1)+1>=k)r=mid;
// else l=mid+1;
// }
// return l;
// }
int getkth(int L,int R,int k)
{
int l=0,r=1e8+5;
while(l<r)
{
int mid=(l+r+1)>>1;
if(getrank(L,R,mid,1)+1<=k)l=mid;
else r=mid-1;
}
return l;
}
int getpre(int L,int R,int k,int at)
{
int l=s[at].l,r=s[at].r;
if(l>R||r<L)return -INF;
if(L<=l&&r<=R)
return BT::getpre(k,s[at].rt);
return max(getpre(L,R,k,lc(at)),getpre(L,R,k,rc(at)));
}
int getnext(int L,int R,int k,int at)
{
int l=s[at].l,r=s[at].r;
if(l>R||r<L)return INF;
if(L<=l&&r<=R)
return BT::getnext(k,s[at].rt);
return min(getnext(L,R,k,lc(at)),getnext(L,R,k,rc(at)));
}
}
signed main()
{
using namespace SEG;
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
read(n);read(Q);
for(int i=1; i<=n; i++)
read(a[i]);
build(1,n,1);
int op,x,y,k;
while(Q--)
{
read(op);read(x);read(y);
if(op==3)
{
update(x,y,1);
a[x]=y;
}else
{
read(k);
if(op==1)write(getrank(x,y,k,1)+1);
else if(op==2)write(getkth(x,y,k));
else if(op==4)write(getpre(x,y,k,1));
else if(op==5)write(getnext(x,y,k,1));
pc('\n');
}
}
return 0;
}2. 树状数组套权值线段树（带修主席树）
注意维护的是权值线段树不是可持久化权值线段树，带修和不带修类似于树状数组和前缀和数组的差异。
参考 洛谷P2617 Dynamic Rankings 题解 （懒得写模板题）
时间复杂度 $\mathcal{O}(n \log^2 n)$ ，空间复杂度 $\mathcal{O}(n \log ^2 n)$
代码：（支持单点修改 + 区间第 $k$ 大值查询）
// 2024年06月12日 18:15:58
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define ls(at) tr[at].ls
#define rs(at) tr[at].rs
#define N ((int)(1e5 + 15))
int n, len, tot, a[N], o[N * 2], rt[N], tmp[2][25], cnt[2];
struct node { int ls, rs, v; } tr[N * 400];
struct qry { int op, x, y, k; } q[N];
int lowbit(int x) { return x & (-x); }
void Modify(int &at, int l, int r, int x, int v)
{
if(!at) at = ++tot;
tr[at].v += v; if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) Modify(ls(at), l, mid, x, v);
else Modify(rs(at), mid + 1, r, x, v);
}
void pre_Modify(int x, int v)
{
int p = lower_bound(o + 1, o + 1 + len, a[x]) - o;
for(int i = x; i <= n; i += lowbit(i)) Modify(rt[i], 1, len, p, v);
}
int Query(int l, int r, int k)
{
if(l == r) return l;
int mid = (l + r) >> 1, sum = 0;
for(int i = 1; i <= cnt[0]; i++) sum -= tr[ls(tmp[0][i])].v;
for(int i = 1; i <= cnt[1]; i++) sum += tr[ls(tmp[1][i])].v;
if(k <= sum)
{
for(int i = 1; i <= cnt[0]; i++) tmp[0][i] = ls(tmp[0][i]);
for(int i = 1; i <= cnt[1]; i++) tmp[1][i] = ls(tmp[1][i]);
return Query(l, mid, k);
}else
{
for(int i = 1; i <= cnt[0]; i++) tmp[0][i] = rs(tmp[0][i]);
for(int i = 1; i <= cnt[1]; i++) tmp[1][i] = rs(tmp[1][i]);
return Query(mid + 1, r, k - sum);
}
}
int pre_Query(int l, int r, int k)
{
memset(tmp, 0, sizeof(tmp)); cnt[0] = cnt[1] = 0;
for(int i = l - 1; i; i -= lowbit(i)) tmp[0][++cnt[0]] = rt[i];
for(int i = r; i; i -= lowbit(i)) tmp[1][++cnt[1]] = rt[i];
return Query(1, len, k);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int m; cin >> n >> m; char op;
for(int i = 1; i <= n; i++) { cin >> a[i]; o[++len] = a[i]; }
for(int i = 1; i <= m; i++)
{
cin >> op; q[i].op = (op == 'Q') + 1;
if(q[i].op == 2) { cin >> q[i].x >> q[i].y >> q[i].k; }
else { cin >> q[i].x >> q[i].y; o[++len] = q[i].y; }
}
sort(o + 1, o + len + 1); len = unique(o + 1, o + len + 1) - o - 1;
for(int i = 1; i <= n; i++) pre_Modify(i, 1);
for(int i = 1; i <= m; i++)
{
if(q[i].op == 1)
{
pre_Modify(q[i].x, -1);
a[q[i].x] = q[i].y; pre_Modify(q[i].x, 1);
} else { cout << o[pre_Query(q[i].x, q[i].y, q[i].k)] << '\n'; }
}
return 0;
}树状数组
树状数组的具体文章详见 浅谈树状数组 区间修改&区间查询
最新的模板：（单点修改区间查询）
// 2023年06月23日 09:22:14
#define lowbit(x) ((x) & (-(x)))
void add(int x,int v) {
for(int i = x; i && i <= tot; i += lowbit(i)) tree[i] += v;
}
int sum(int x) {
int res = 0; for(int i = x; i; i -= lowbit(i)) res += tree[i]; return res;
}线段树
线段树1 朴素写法
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(1e5+15)
int n,Q;
int a[N];
struct node
{
int sum,tag;
}t[N<<2];
#define ls(at) (at<<1)
#define rs(at) (at<<1|1)
void push_up(int at)
{
t[at].sum=t[ls(at)].sum+t[rs(at)].sum;
}
void build(int l,int r,int at)
{
if(l==r)
{
t[at].sum=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,ls(at));
build(mid+1,r,rs(at));
push_up(at);
}
void proc(int l,int r,int k,int at)
{
t[at].sum+=k*(r-l+1);
t[at].tag+=k;
}
void push_down(int l,int r,int at)
{
if(t[at].tag)
{
int mid=(l+r)>>1;
proc(l,mid,t[at].tag,ls(at));
proc(mid+1,r,t[at].tag,rs(at));
}
t[at].tag=0;
}
void update(int nl,int nr,int l,int r,int k,int at)
{
if(nl<=l&&r<=nr)
{
t[at].sum+=k*(r-l+1);
t[at].tag+=k;
return;
}
int mid=(l+r)>>1;
push_down(l,r,at);
if(nl<=mid)update(nl,nr,l,mid,k,ls(at));
if(nr>mid)update(nl,nr,mid+1,r,k,rs(at));
push_up(at);
}
int query(int nl,int nr,int l,int r,int at)
{
if(nl<=l&&r<=nr)
{return t[at].sum;}
int mid=(l+r)>>1,res=0;
push_down(l,r,at);
if(nl<=mid)res+=query(nl,nr,l,mid,ls(at));
if(nr>mid)res+=query(nl,nr,mid+1,r,rs(at));
return res;
}
signed main()
{
read(n);read(Q);
for(int i=1; i<=n; i++)
read(a[i]);
build(1,n,1);
while(Q--)
{
int op,l,r,k;
read(op);
if(op==1)
{
read(l);read(r);read(k);
update(l,r,1,n,k,1);
}else
{
read(l);read(r);
write(query(l,r,1,n,1));pc('\n');
}
}
return 0;
}还有一种比较好的query写法，如下
int query(int nl,int nr,int l,int r,int at)
{
if(nl<=l&&r<=nr)
// return ...;
if(nr<=mid)return query(nl,nr,l,mid,ls(at));
if(nl>mid)return query(nl,nr,mid+1,r,rs(at));
return query(nl,nr,l,mid,ls(at))+query(nl,nr,mid+1,r,rs(at));
}
线段树1 标记永久化+动态开点
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(1e5+15)
struct node
{
int ch[2],ans,tag;
}t[N<<2];
int rt,tot;
int n,Q,a[N];
#define ls(at) t[at].ch[0]
#define rs(at) t[at].ch[1]
void insert(int nl,int nr,int l,int r,int x,int &at)
{
if(!at)at=++tot;
t[at].ans+=x*(min(r,nr)-max(l,nl)+1);
if(nl<=l&&r<=nr)
{
t[at].tag+=x;
return;
}
int mid=(l+r)>>1;
if(nl<=mid)insert(nl,nr,l,mid,x,ls(at));
if(nr>mid)insert(nl,nr,mid+1,r,x,rs(at));
}
void pusht(int l,int r,int x,int &at)
{
if(!at)at=++tot;
t[at].ans+=(r-l+1)*x;
t[at].tag+=x;
}
int query(int nl,int nr,int l,int r,int at)
{
if(nl<=l&&r<=nr)
return t[at].ans;
int mid=(l+r)>>1;
if(t[at].tag)
{
pusht(l,mid,t[at].tag,ls(at));
pusht(mid+1,r,t[at].tag,rs(at));
t[at].tag=0;
}
int res=0;
if(nl<=mid)res+=query(nl,nr,l,mid,ls(at));
if(nr>mid)res+=query(nl,nr,mid+1,r,rs(at));
return res;
}
signed main()
{
read(n);read(Q);
for(int i=1; i<=n; i++)
{
read(a[i]);
insert(i,i,1,n,a[i],rt);
}
while(Q--)
{
int op,l,r,x;
read(op);read(l);read(r);
if(op==1){read(x);insert(l,r,1,n,x,rt);}
else write(query(l,r,1,n,rt)),pc('\n');
}
return 0;
}李超线段树
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(1e5+15)
#define M (int)(4e4+15)
#define ls(at) (at<<1)
#define rs(at) (at<<1|1)
const int mod1=39989;
const int mod2=1e9;
struct line
{
double k,b;
}li[N];
int bs[M<<2],n,lstans,cnt;
double calc(int id,int x)
{
return li[id].k*x+li[id].b;
}
void init(int x1,int y1,int x2,int y2)
{
++cnt;
if(x1==x2)
{
li[cnt].k=0;
li[cnt].b=max(y1,y2);
}else
{
li[cnt].k=1.0*(y1-y2)/(x1-x2);
li[cnt].b=y1-li[cnt].k*x1;
}
}
void update(int nl,int nr,int l,int r,int nw,int at)
{
int u=bs[at];
int mid=(l+r)>>1;
double now=calc(nw,mid),resu=calc(u,mid);
if(nl<=l&&r<=nr)
{
if(l==r)
{
if(now>resu)
bs[at]=nw;
return;
}
if(li[nw].k>li[u].k)
{
if(now>resu)
{
bs[at]=nw;
update(nl,nr,l,mid,u,ls(at));
}else update(nl,nr,mid+1,r,nw,rs(at));
}else if(li[nw].k<li[u].k)
{
if(now>resu)
{
bs[at]=nw;
update(nl,nr,mid+1,r,u,rs(at));
}else update(nl,nr,l,mid,nw,ls(at));
}else if(li[nw].b>li[u].b)bs[at]=nw;
return;
}
if(nl<=mid)update(nl,nr,l,mid,nw,ls(at));
if(nr>mid)update(nl,nr,mid+1,r,nw,rs(at));
}
struct node{double v;int x;};
node max(node a,node b)
{
if(a.v==b.v)return a.x<b.x?a:b;
return a.v>b.v?a:b;
}
node query(int l,int r,int x,int at)
{
if(r<x||l>x)return {0,0};
int mid=(l+r)>>1;
node tmp={calc(bs[at],x),bs[at]};
if(l==r)return tmp;
return max(tmp,max(query(l,mid,x,ls(at)),query(mid+1,r,x,rs(at))));
}
#define change1(x) (x=(x+lstans-1+mod1)%mod1+1)
#define change2(x) (x=(x+lstans-1+mod2)%mod2+1)
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
read(n);
int op,x1,y1,x2,y2;
for(int i=1; i<=n; i++)
{
read(op);
if(op==1)
{
read(x1);read(y1);read(x2);read(y2);
change1(x1);change1(x2);change2(y1);change2(y2);
if(x1>x2)swap(x1,x2),swap(y1,y2);
init(x1,y1,x2,y2);update(x1,x2,1,M,cnt,1);
}else
{
int x;read(x);change1(x);
write(lstans=query(1,M,x,1).x);pc('\n');
}
}
return 0;
}线段树合并
P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
未经过严格验证正确性
时间复杂度 $O(n \log n)$
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(1e5+15)
int n,m,ans[N];
struct Edge
{
int u,v,next;
}e[N<<1];
int pos=1,head[N];
int fa[N],son[N],sz[N],top[N],dep[N];
int val[N*70],ch[N*70][2],rt[N],tot,Z,typ[N*70];
#define ls(at) ch[at][0]
#define rs(at) ch[at][1]
void addEdge(int u,int v)
{
e[++pos]={u,v,head[u]};
head[u]=pos;
}
void dfs(int u,int f,int d)
{
fa[u]=f;
sz[u]=1;
dep[u]=d;
int mx=-1;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(v==f)continue;
dfs(v,u,d+1);
sz[u]+=sz[v];
if(sz[v]>mx)mx=sz[v],son[u]=v;
}
}
void dfs(int u,int ftop)
{
top[u]=ftop;
if(!son[u])return;
dfs(son[u],ftop);
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(v==fa[u]||v==son[u])continue;
dfs(v,v);
}
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void push_up(int at)
{
if(val[ls(at)]>=val[rs(at)])
val[at]=val[ls(at)],typ[at]=typ[ls(at)];
else val[at]=val[rs(at)],typ[at]=typ[rs(at)];
}
void modify(int l,int r,int pos,int v,int &at)
{
if(!at)at=++tot;
if(l==r)
{
val[at]+=v;
typ[at]=l;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)modify(l,mid,pos,v,ls(at));
else modify(mid+1,r,pos,v,rs(at));
push_up(at);
}
int merge(int x,int y,int l,int r)
{
if(!x||!y)return x|y;
if(l==r)
{
val[x]+=val[y];
typ[x]=l;
return x;
}
int mid=(l+r)>>1;
ls(x)=merge(ls(x),ls(y),l,mid);
rs(x)=merge(rs(x),rs(y),mid+1,r);
push_up(x);
return x;
}
void calc(int u)
{
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(v==fa[u])continue;
calc(v);
rt[u]=merge(rt[u],rt[v],1,Z);
}
if(val[rt[u]])ans[u]=typ[rt[u]];
}
int u[N],v[N],z[N];
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
read(n);read(m);
for(int i=1,u,v; i<n; i++)
{
read(u);read(v);
addEdge(u,v);addEdge(v,u);
}
dfs(1,0,1);dfs(1,1);
for(int i=1; i<=m; i++)
read(u[i]),read(v[i]),read(z[i]),Z=max(Z,z[i]);
for(int i=1; i<=m; i++)
{
int d=lca(u[i],v[i]);
modify(1,Z,z[i],1,rt[u[i]]);
modify(1,Z,z[i],1,rt[v[i]]);
modify(1,Z,z[i],-1,rt[d]);
modify(1,Z,z[i],-1,rt[fa[d]]);
}
calc(1);
for(int i=1; i<=n; i++)
write(ans[i]),pc('\n');
return 0;
}线段树分裂
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(2e5+15)
int n,Q,tot,rcnt,seq=1;
int bac[N*35],ch[N*35][2],rt[N],val[N*35];
int newnod(){return rcnt?bac[rcnt--]:++tot;}
#define ls(at) ch[at][0]
#define rs(at) ch[at][1]
void del(int at)
{
bac[++rcnt]=at;
ls(at)=rs(at)=val[at]=0;
}
void modify(int l,int r,int pos,int v,int &at)
{
if(!at)at=newnod();
val[at]+=v;
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)modify(l,mid,pos,v,ls(at));
else modify(mid+1,r,pos,v,rs(at));
}
int query(int nl,int nr,int l,int r,int at)
{
if(nr<l||r<nl)return 0;
if(nl<=l&&r<=nr)return val[at];
int mid=(l+r)>>1;
return query(nl,nr,l,mid,ls(at))+query(nl,nr,mid+1,r,rs(at));
}
int kth(int l,int r,int k,int at)
{
if(l==r)return l;
int mid=(l+r)>>1;
if(k<=val[ls(at)])return kth(l,mid,k,ls(at));
else return kth(mid+1,r,k-val[ls(at)],rs(at));
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
val[x]+=val[y];
ls(x)=merge(ls(x),ls(y));
rs(x)=merge(rs(x),rs(y));
del(y);
return x;
}
void split(int x,int &y,int k)
{
if(!x)return;
y=newnod();
int v=val[ls(x)];
if(k>v)split(rs(x),rs(y),k-v);
else
{
swap(rs(x),rs(y));
if(k<v)split(ls(x),ls(y),k);
}
val[y]=val[x]-k;
val[x]=k;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
read(n);read(Q);
for(int i=1,x; i<=n; i++)
{
read(x);
modify(1,n,i,x,rt[1]);
}
int op,x,y,z;
while(Q--)
{
read(op);
if(op==0)
{
read(x);read(y);read(z);
int k1=query(1,z,1,n,rt[x]);
int k2=query(y,z,1,n,rt[x]);
int tmp=0;
split(rt[x],rt[++seq],k1-k2);
split(rt[seq],tmp,k2);
rt[x]=merge(rt[x],tmp);
}else if(op==1)
{
read(x);read(y);
rt[x]=merge(rt[x],rt[y]);
}else if(op==2)
{
read(x);read(y);read(z);
modify(1,n,z,y,rt[x]);
}else if(op==3)
{
read(x);read(y);read(z);
write(query(y,z,1,n,rt[x]));pc('\n');
}else if(op==4)
{
read(x);read(y);
if(val[rt[x]]<y){puts("-1");continue;}
write(kth(1,n,y,rt[x]));pc('\n');
}
}
return 0;
}静态仙人掌
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void print(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(4e4+15)
int n,m,Q,dfncnt,ext;
int dfn[N],low[N],fa[N],ans;
int top[N],son[N],sz[N],dep[N],b[N],sum[N],dis[N];
struct Edge
{
int v,w;
};
vector<Edge> vec[N],exv[N];
int find(int u,int f)
{
int res;
while(top[u]!=top[f])
{
res=top[u];
u=fa[top[u]];
}
return u==f?res:son[f];
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void dfs(int u,int f,int d)
{
dep[u]=d+1;fa[u]=f;sz[u]=1;
int mx=-1;
for(int i=0; i<exv[u].size(); i++)
{
int v=exv[u][i].v;
if(v==f)continue;
dis[v]=dis[u]+exv[u][i].w;
dfs(v,u,d+1);
sz[u]+=sz[v];
if(sz[v]>mx)mx=sz[v],son[u]=v;
}
}
void dfs(int u,int ftop)
{
top[u]=ftop;
if(!son[u])return;
dfs(son[u],ftop);
for(int i=0; i<exv[u].size(); i++)
{
int v=exv[u][i].v;
if(v==fa[u]||v==son[u])
continue;
dfs(v,v);
}
}
void proc(int u,int v,int w)
{
++ext;
int pw,pre=w,x=v;
while(x!=fa[u])
{
sum[x]=pre;
pre+=b[x];
x=fa[x];
}
sum[ext]=sum[u];
sum[u]=0;x=v;
while(x!=fa[u])
{
pw=min(sum[x],sum[ext]-sum[x]);
exv[ext].push_back({x,pw});
exv[x].push_back({ext,pw});
x=fa[x];
}
}
void tarjan(int u,int f)
{
dfn[u]=low[u]=++dfncnt;
for(int i=0; i<vec[u].size(); i++)
{
int v=vec[u][i].v,w=vec[u][i].w;
if(v==f)continue;
if(!dfn[v])
{
fa[v]=u;b[v]=w;
tarjan(v,u);
low[u]=min(low[u],low[v]);
}else low[u]=min(low[u],dfn[v]);
if(low[v]>dfn[u])
{
exv[u].push_back({v,w});
exv[v].push_back({u,w});
}
}
for(int i=0; i<vec[u].size(); i++)
{
int v=vec[u][i].v;
if(fa[v]!=u&&dfn[v]>dfn[u])
proc(u,v,vec[u][i].w);
}
}
signed main()
{
read(n);read(m);read(Q);ext=n;
for(int i=1,u,v,w; i<=m; i++)
{
read(u);read(v);read(w);
vec[u].push_back({v,w});
vec[v].push_back({u,w});
}
tarjan(1,0);dfs(1,0,1);dfs(1,1);
while(Q--)
{
int u,v,p,A,B;read(u);read(v);
p=lca(u,v);
if(p<=n)ans=dis[u]+dis[v]-(dis[p]<<1);
else
{
A=find(u,p);B=find(v,p);
ans=dis[u]+dis[v]-dis[A]-dis[B];
int tmp=abs(sum[A]-sum[B]);
ans+=min(tmp,sum[p]-tmp);
}
print(ans);pc('\n');
}
return 0;
}可持久化数组
- 主席树实现被卡了
long long
时间复杂度 $O(n\log n)$
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+25)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(1e6+5)
int n,Q;
int a[N],T[N],tot;
struct node
{
int ch[2],num;
}t[N<<5];
#define ls(at) t[at].ch[0]
#define rs(at) t[at].ch[1]
int build(int l,int r)
{
int at=++tot,mid=(l+r)>>1;
if(l==r){t[at].num=a[l];return at;}
ls(at)=build(l,mid);
rs(at)=build(mid+1,r);
return at;
}
int update(int pre,int l,int r,int x,int v)
{
int at=++tot,mid=(l+r)>>1;
t[at]=t[pre];
if(l==r)
{
t[at].num=v;
return at;
}
if(x<=mid)ls(at)=update(ls(pre),l,mid,x,v);
else rs(at)=update(rs(pre),mid+1,r,x,v);
return at;
}
int query(int at,int l,int r,int x)
{
if(l==r)return t[at].num;
int mid=(l+r)>>1;
if(x<=mid)return query(ls(at),l,mid,x);
else return query(rs(at),mid+1,r,x);
}
signed main()
{
read(n);read(Q);
for(int i=1; i<=n; i++)
read(a[i]);
T[0]=build(1,n);
for(int i=1; i<=Q; i++)
{
int rt,op,x,y;
read(rt);read(op);read(x);
if(op==1)
{
read(y);
T[i]=update(T[rt],1,n,x,y);
}else
{
write(query(T[rt],1,n,x));
pc('\n');T[i]=T[rt];
}
}
return 0;
}Elegia神仙的神仙解法（离线解法）
根据依赖关系，且可逆操作，建关系树，然后跑dfs
时间复杂度 $O(n)$
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+25)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(1e6+5)
int n,Q;
int a[N],op[N],k[N],x[N],ans[N];
vector<int>vec[N];
void dfs(int u)
{
if(op[u]==2)
{
ans[u]=a[k[u]];
for(int v:vec[u])dfs(v);
}else
{
swap(a[k[u]],x[u]);
for(int v:vec[u])dfs(v);
swap(a[k[u]],x[u]);
}
}
signed main()
{
read(n);read(Q);
for(int i=1; i<=n; i++)
read(a[i]);
op[0]=2;
for(int i=1; i<=Q; i++)
{
int rt;
read(rt);read(op[i]);read(k[i]);
if(op[i]==1)
read(x[i]);
vec[rt].push_back(i);
}
dfs(0);
for(int i=1; i<=Q; i++)
if(op[i]==2)
write(ans[i]),pc('\n');
return 0;
}可持久化权值线段树（主席树）
区间 $k$ 小值
时间复杂度 $O(n\log n)$
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+25)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(2e5+5)
int n,m,Q;
int a[N],b[N];
int T[N],tot;
struct node
{
int ch[2],sum;
}t[N<<5];
#define ls(at) t[at].ch[0]
#define rs(at) t[at].ch[1]
int build(int l,int r)
{
int at=++tot,mid=(l+r)>>1;
if(l<r)
{
ls(at)=build(l,mid);
rs(at)=build(mid+1,r);
}
return at;
}
int update(int pre,int l,int r,int x)
{
int at=++tot,mid=(l+r)>>1;
t[at]=t[pre];++t[at].sum;
if(l<r)
{
if(x<=mid)ls(at)=update(ls(pre),l,mid,x);
else rs(at)=update(rs(pre),mid+1,r,x);
}
return at;
}
int query(int u,int v,int l,int r,int k)
{
if(l==r)return l;
int x=t[ls(v)].sum-t[ls(u)].sum;
int mid=(l+r)>>1;
if(x>=k)return query(ls(u),ls(v),l,mid,k);
else return query(rs(u),rs(v),mid+1,r,k-x);
}
void init()
{
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-b-1;
T[0]=build(1,m);
for(int i=1; i<=n; i++)
{
a[i]=lower_bound(b+1,b+1+m,a[i])-b;
T[i]=update(T[i-1],1,m,a[i]);
}
}
signed main()
{
read(n);read(Q);
for(int i=1; i<=n; i++)
read(a[i]),b[i]=a[i];
init();
while(Q--)
{
int l,r,k;read(l);read(r);read(k);
write(b[query(T[l-1],T[r],1,m,k)]);
pc('\n');
}
return 0;
}动态树（LCT）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+5)
#define gc() getchar()
#define pc(a) putchar(a)
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n,Q;
namespace LCT
{
struct node
{
int ch[2],num,fa,ans,tag;
}t[N];
#define isroot(x) ((t[t[x].fa].ch[0]!=x)&&(t[t[x].fa].ch[1]!=x))
void pushr(int x)
{
swap(t[x].ch[0],t[x].ch[1]);
t[x].tag^=1;
}
void push_up(int x)
{
t[x].ans=t[t[x].ch[0]].ans
^t[t[x].ch[1]].ans^t[x].num;
}
void push_down(int x)
{
if(t[x].tag)
{
if(t[x].ch[0])pushr(t[x].ch[0]);
if(t[x].ch[1])pushr(t[x].ch[1]);
t[x].tag=0;
}
}
void push_all(int x)
{
if(!isroot(x))push_all(t[x].fa);
push_down(x);
}
void rotate(int x)
{
int y=t[x].fa;
int z=t[y].fa;
int k=t[y].ch[1]==x;
if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;
t[x].fa=z;
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].fa=y;
t[x].ch[k^1]=y;
t[y].fa=x;
push_up(y);
push_up(x);
}
void splay(int x)
{
push_all(x);
while(!isroot(x))
{
int y=t[x].fa;
int z=t[y].fa;
if(!isroot(y))
(t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y);
rotate(x);
}
}
void access(int x)
{
for(int y=0;x;y=x,x=t[x].fa)
splay(x),t[x].ch[1]=y,push_up(x);
}
void make_root(int x)
{
access(x);splay(x);
pushr(x);
}
int find_root(int x)
{
access(x);splay(x);
while(t[x].ch[0])push_down(x),x=t[x].ch[0];
splay(x);
return x;
}
void split(int x,int y)
{
make_root(x);
access(y);splay(y);
}
void link(int x,int y)
{
make_root(x);
if(find_root(y)!=x)t[x].fa=y;
}
void cut(int x,int y)
{
make_root(x);
if(find_root(y)==x&&t[y].fa==x&&!t[y].ch[0])
{
t[x].ch[1]=t[y].fa=0;
push_up(x);
}
}
}
signed main()
{
using namespace LCT;
read(n);read(Q);
for(int i=1; i<=n; i++)
read(t[i].num);
while(Q--)
{
int op,x,y;read(op);read(x);read(y);
if(op==0){split(x,y);write(t[y].ans);pc('\n');}
if(op==1)link(x,y);
if(op==2)cut(x,y);
if(op==3)splay(x),t[x].num=y;
}
return 0;
}
