1. Python技术站首页
  2. 算法与数据结构

动态开点线段树&线段树合并学习笔记

• 算法与数据结构

动态开点线段树

使用场景

  1. \(4 \times n\) 开不下。
  2. 值域需要平移（有负数）。

什么时候开点

显然，访问的节点不存在时（只会在修改递归时开点）。

trick

区间里面有负数时，\(mid = (l + R - 1) / 2\)。

防止越界。

例如区间 \([-1,0]\)。

开点上限

考虑到 update 一次最多开 \(\log V\) 个点（最多递归 \(\log V\)次）。所以总空间应当开 \(O(m \log n)\)。

代码

#include<bits/stdc++.h> 
#define int long long
using namespace std;
int tot;
int n,q;
const int maxn = 4e6+114;
struct Node{
	int val, lt, rt, tag;
}tree[maxn];
void pushup(int &x){
	tree[x].val=tree[tree[x].lt].val+tree[tree[x].rt].val;
}
void addtag(int &x,int l,int r,int v){
	if(x==0){
		x=++tot;
	}
	tree[x].val+=(r-l+1)*v;
	tree[x].tag+=v;
}
void pushdown(int &x,int l,int r){
	if(l>r) return ;
	int mid=(l+r)/2;
	addtag(tree[x].lt,l,mid,tree[x].tag);
	addtag(tree[x].rt,mid+1,r,tree[x].tag);
	tree[x].tag=0;
}
int ask(int &x,int lt,int rt,int l,int r){
	if(rt<l||r<lt){
		return 0;
	}
	if(l<=lt&&rt<=r){
		return tree[x].val;
	}
	int mid=(lt+rt)/2;
	pushdown(x,lt,rt);
	int sum=0;
	sum+=ask(tree[x].lt,lt,mid,l,r);
	sum+=ask(tree[x].rt,mid+1,rt,l,r);
	return sum;
}
void add(int &x,int lt,int rt,int l,int r,int v){
	if(rt<l||r<lt){
		return ;
	}
	if(l<=lt&&rt<=r){
		addtag(x,lt,rt,v);
		return ;
	}
	int mid=(lt+rt)/2;
	pushdown(x,lt,rt);
	add(tree[x].lt,lt,mid,l,r,v);
	add(tree[x].rt,mid+1,rt,l,r,v);
	pushup(x);
}
int root;
signed main(){
	int n,q;
	cin>>n>>q;
	root=++tot;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		add(root,1,n,i,i,x);
	}
	for(int i=1;i<=q;i++){
		int op;
		cin>>op;
		if(op==1){
			int x,y,k;
			cin>>x>>y>>k;
			add(root,1,n,x,y,k);
		}
		else{
			int x,y;
			cin>>x>>y;
			cout<<ask(root,1,n,x,y)<<'\n';
		}
	}
}

例题 1

题目传送门

化简题意得维护一个 01 区间，维护区间覆盖，取反以及查询第一个出现的 0。

显然这个很鬼畜。

首先考虑怎么回答询问。

可以维护区间和，然后在线段树上二分。

然后考虑覆盖。

这个很显然可以维护一个覆盖标记。

那取反呢？

可以当取反和覆盖标记在同一节点时强制消除一个。

显然，取反就是让覆盖标记也取反。

那么就可以写出代码了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 4e6+1140;
const int inf = 1e18;
int tot;
struct Node{
	long long lc,rc,val,tag1,tag2;
}tree[maxn];//val 表示区间中 1 的个数 
void pushup(int x){
	tree[x].val=tree[tree[x].lc].val+tree[tree[x].rc].val;
}
void addtag1(int &x,int lt,int rt,int tag)/*翻转*/{
	if(x==0) x=++tot;
	if(tag==0) return ;
	if(tree[x].tag1==1){
		tree[x].tag1=0;
		tree[x].val=(rt-lt+1)-tree[x].val;
		return ;
	}
	tree[x].tag1=1;
	if(tree[x].tag2!=0){
		tree[x].tag1=0;
		tree[x].tag2=((tree[x].tag2-1)^1)+1;
		tree[x].val=(tree[x].tag2-1)*(rt-lt+1);
		return ;
	}
	tree[x].val=(rt-lt+1)-tree[x].val;
	
	return ;
}
void addtag2(int &x,int lt,int rt,int tag){
	if(x==0) x=++tot;
	if(tag==0) return ;
	tree[x].tag1=0;
	tree[x].val=(tag-1)*(rt-lt+1);
	tree[x].tag2=tag;
	//cout<<x<<' '<<lt<<' '<<rt<<'\n';
	//cout<<lt<<' '<<rt<<' '<<tree[x].val<<'\n';
	return ;
}
void pushdown(int x,int lt,int rt){
	if(lt>=rt) return ;
	int mid = (lt+rt-1)/2;
	addtag1(tree[x].lc,lt,mid,tree[x].tag1);
	addtag1(tree[x].rc,mid+1,rt,tree[x].tag1);
	tree[x].tag1=0;
	addtag2(tree[x].lc,lt,mid,tree[x].tag2);
	addtag2(tree[x].rc,mid+1,rt,tree[x].tag2);	
	tree[x].tag2=0;
}
void reve(int &x,int l,int r,int lt,int rt){
	if(r<lt||l>rt) return ;
	if(r<=rt&&l>=lt){
		addtag1(x,l,r,1);
		return ;
	}
	int mid=(l+r-1)/2;
	pushdown(x,l,r);
	reve(tree[x].lc,l,mid,lt,rt);
	reve(tree[x].rc,mid+1,r,lt,rt);
	pushup(x);
}
void cover(int &x,int l,int r,int lt,int rt,int tag){
	if(r<lt||l>rt) return ;
	if(r<=rt&&l>=lt){
		//cout<<"c:"<<l<<' '<<r<<'\n';
		addtag2(x,l,r,tag);
		return ;
	}
	int mid=(l+r-1)/2;
	pushdown(x,l,r);
	cover(tree[x].lc,l,mid,lt,rt,tag);
	cover(tree[x].rc,mid+1,r,lt,rt,tag);
	pushup(x);
}
int query(int &x,int l,int r){
	if(l==r){
		return l;
	}
	pushdown(x,l,r);
	int mid = (l+r-1)/2;
	if(tree[tree[x].lc].val<(mid-l+1)){
		return query(tree[x].lc,l,mid);
	}
	else{
		return query(tree[x].rc,mid+1,r);
	}
}
int ask(int &x,int l,int r,int lt,int rt){
	if(r<lt||l>rt) return 0;
	if(r<=rt&&l>=lt) return tree[x].val;
	int mid=(l+r-1)/2;
	int sum=0;
	pushdown(x,l,r);
	sum+=ask(tree[x].lc,l,mid,lt,rt);
	sum+=ask(tree[x].rc,mid+1,r,lt,rt);
	return sum;
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
int n,q,root;
signed main(){
	q=read();
	n=inf;
	root=1,tot=1;
	while(q--){
		int op;
		op=read();
		if(op==1){
			int l,r;
			l=read();
			r=read();
			cover(root,1,n,l,r,2);
		}
		else if(op==2){
			int l,r;
			l=read(),r=read();
			cover(root,1,n,l,r,1);
		}
		else{
			int l,r;
			l=read(),r=read();
			reve(root,1,n,l,r);
		}
		write(query(root,1,n));
		putchar('\n');
	}
	return 0;
}

但是这样过不了，猜猜为什么？

线段树合并

在一个树形结构中每一个节点需要开一个权值线段树且区间范围完全一致）。

复杂度分析

一下分析建立在 树形结构合并 的前提下。

注意到在合并的时候需要递归 \(\log n\) 层当且仅仅当一棵线段树和另一棵线段树都有一个节点，并且合并完会变成一个节点，且把它的祖先节点也合并，也就是说每次花费 \(\log n\) 的代价合并了 \(\log n\) 个节点，由于最多有 \(n \log n\) 个节点，所以总复杂度就是 \(O(n \log n)\)。

CF600E

线段树记录最重的子树。然后合并答案。

现在就只有合并线段树的问题了。

trick

段树合并完后再还原需要额外空间，因此最好一次跑完答案，因此 线段树合并适合离线

实现（CF600E）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+114;
const int inf = 1e5;
struct Node{
	int ls,rs,val,cnt;// left son right son the anser the cnt 
}tree[maxn * 20];
vector<int> edge[maxn];
int col[maxn];
int ans[maxn];
int root[maxn];
int tot;
inline void add(int u,int v){
	edge[u].push_back(v);
	edge[v].push_back(u);	
}
void pushup(int &cur){
	//cout<<tree[tree[cur].ls].cnt<<" "<<tree[tree[cur].ls].cnt<<'\n';
	if(tree[tree[cur].ls].cnt<tree[tree[cur].rs].cnt){
		tree[cur].cnt=tree[tree[cur].rs].cnt;
		tree[cur].val=tree[tree[cur].rs].val;
	}
	else if(tree[tree[cur].rs].cnt<tree[tree[cur].ls].cnt){
		tree[cur].cnt=tree[tree[cur].ls].cnt;
		tree[cur].val=tree[tree[cur].ls].val;
	}
	else{
		tree[cur].cnt=tree[tree[cur].ls].cnt;
		tree[cur].val=tree[tree[cur].ls].val+tree[tree[cur].rs].val;
	}
}
void addtag(int &cur,int lt,int rt,int l,int r,int v){
	if(lt>r||rt<l) return ;
	if(cur==0){
		cur=++tot;
	}
	if(lt==rt){
		tree[cur].cnt+=v;
		tree[cur].val=lt;
		return ;
	}
	int mid = (lt+rt)/2;
	addtag(tree[cur].ls,lt,mid,l,r,v);
	addtag(tree[cur].rs,mid+1,rt,l,r,v);
	pushup(cur);
}
int merge(int a,int b,int l,int r){
	if(a==0||b==0) return a+b;
	if(l==r){
		tree[a].cnt+=tree[b].cnt;
		tree[a].val=l;
		return a;
	}
	int mid=(l+r)/2;
	tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);
	tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
	pushup(a);
	return a;
}
void dfs(int now,int fa){
	for(int nxt:edge[now]){
		if(nxt==fa) continue;
		dfs(nxt,now);
		root[now]=merge(root[now],root[nxt],1,inf);
	}
	pushup(root[now]);
	addtag(root[now],1,inf,col[now],col[now],1);
	ans[now]=tree[root[now]].val;
}
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>col[i];
	for(int i=2;i<=n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<' ';
	}
}

P4556

首先可以考虑树上差分。

然后显然我们只要处理桶合并的问题。

那么显然就可以线段树合并。

#include<bits/stdc++.h>
using namespace std;
const int inf = 2e5;
int n,q;
const int maxn = 2e5+114;
vector<int> Add[maxn*2],Del[maxn*2];
int ans[maxn];
int tot;
int root[maxn];
int fa[maxn][18];
int depth[maxn];
int lg[maxn];
vector<int> edge[maxn];
struct Node{
	int ls,rs,val,cnt;// left son right son the anser the cnt 
}tree[maxn * 20];
void pushup(int &cur){
	//cout<<tree[tree[cur].ls].cnt<<" "<<tree[tree[cur].ls].cnt<<'\n';
	if(tree[tree[cur].ls].cnt<tree[tree[cur].rs].cnt){
		tree[cur].cnt=tree[tree[cur].rs].cnt;
		tree[cur].val=tree[tree[cur].rs].val;
	}
	else if(tree[tree[cur].rs].cnt<tree[tree[cur].ls].cnt){
		tree[cur].cnt=tree[tree[cur].ls].cnt;
		tree[cur].val=tree[tree[cur].ls].val;
	}
	else{
		tree[cur].cnt=tree[tree[cur].ls].cnt;
		tree[cur].val=min(tree[tree[cur].ls].val,tree[tree[cur].rs].val);
	}
}
void addtag(int &cur,int lt,int rt,int l,int r,int v){
	if(lt>r||rt<l) return ;
	if(cur==0){
		cur=++tot;
	}
	if(lt==rt){
		tree[cur].cnt+=v;
		tree[cur].val=lt;
		return ;
	}
	int mid = (lt+rt)/2;
	addtag(tree[cur].ls,lt,mid,l,r,v);
	addtag(tree[cur].rs,mid+1,rt,l,r,v);
	pushup(cur);
}
int merge(int a,int b,int l,int r){
	if(a==0||b==0) return a+b;
	if(l==r){
		tree[a].cnt+=tree[b].cnt;
		tree[a].val=l;
		return a;
	}
	int mid=(l+r)/2;
	tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);
	tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
	pushup(a);
	return a;
}
inline void add(int u,int v){
	edge[u].push_back(v);
	edge[v].push_back(u);
}
inline void dfs1(int now,int fath){
	fa[now][0]=fath;
	depth[now]=depth[fath] + 1;
	for(int i=1;i<=lg[depth[now]];++i)
		fa[now][i] = fa[fa[now][i-1]][i-1];
	for(int nxt:edge[now]){
		if(nxt==fath) continue;
		dfs1(nxt,now);
	}
}
int LCA(int x,int y){
	if(depth[x] < depth[y]) 
		swap(x, y);
	while(depth[x] > depth[y])
		x=fa[x][lg[depth[x]-depth[y]]- 1];
	if(x==y) 
    	return x;
	for(int k=lg[depth[x]]-1; k>=0; --k)
		if(fa[x][k] != fa[y][k])
			x=fa[x][k],y=fa[y][k];
	return fa[x][0];
}
void change(int u,int v,int z){
	//cout<<u<<' '<<v<<' '<<z<<' '<<LCA(u,v)<<'\n';
	Add[u].push_back(z);
	Add[v].push_back(z);
	int w=LCA(u,v);
	Del[w].push_back(z);
	Del[fa[w][0]].push_back(z);
}
void dfs2(int now,int fa){
	for(int nxt:edge[now]){
		if(nxt==fa) continue;
		dfs2(nxt,now);
		root[now]=merge(root[now],root[nxt],1,inf);
	}
	pushup(root[now]);
	for(int c:Add[now]){
		addtag(root[now],1,inf,c,c,1);
	}
	for(int c:Del[now]){
		addtag(root[now],1,inf,c,c,-1);
	}
	ans[now]=tree[root[now]].val;
}
//树上差分打 add & del 标记，合并到某个节点再统一处理
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i = 1; i <= n; ++i)
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	dfs1(1,0);
	for(int i=1;i<=q;i++){
		int u,v,z;
		cin>>u>>v>>z;
		change(u,v,z);
	}
	dfs2(1,0);
	for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
}

P3521

考虑怎么求逆序对。

我们可以在合并的时候用 \(A_{1,mid} \times B_{mid+1,r}\) 来求出逆序对。

那么接下来就是一个板子了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5+114;
const int inf = 1e5;
struct Node{
    int ls,rs,val;// left son right son the anser the cnt 
}tree[maxn * 20];
int u,v,ans;
int tot;
int n;
void pushup(int &cur){
    //cout<<tree[tree[cur].ls].cnt<<" "<<tree[tree[cur].ls].cnt<<'\n';
    tree[cur].val=tree[tree[cur].ls].val+tree[tree[cur].rs].val;
}
int update(int l,int r,int val){
	int pos=++tot;
	tree[pos].val++;
	if(l==r) return pos;
	int mid=(l+r)>>1;
	if(val<=mid) tree[pos].ls=update(l,mid,val);
	else tree[pos].rs=update(mid+1,r,val);
	return pos;
}
int merge(int a,int b,int l,int r){
    if(a==0||b==0) return a+b;
    if(l==r){
        tree[a].val+=tree[b].val;
        return a;
    }
    int mid=(l+r)/2;
    u+=tree[tree[a].rs].val*tree[tree[b].ls].val;
    v+=tree[tree[a].ls].val*tree[tree[b].rs].val;
    tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);
    tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
    pushup(a);
    return a;
}
int dfs(){
	int root,U;
	cin>>U;
	if(U==0){
		int lt=dfs(),rt=dfs();
		u=0,v=0;
		root=merge(lt,rt,1,n);
		ans+=min(u,v);
		//cout<<u<<' '<<v<<'\n';
		return root;
	}
	else{
    	root=update(1,n,U);
    	return root;
	}
}
signed main(){
    cin>>n;
    dfs();
    cout<<ans;
}

P3605

只要维护子树最大值就可以了，用线段树合并即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+114;
vector<int> edge[maxn];
int val[maxn];
int ans[maxn];
int root[maxn];
const int inf = 1e9+10;
int n,tot;
struct Node{
	int ls,rs,sum;// left son right son the anser the cnt 
}tree[maxn * 20];
void pushup(int &cur){
    tree[cur].sum=tree[tree[cur].ls].sum+tree[tree[cur].rs].sum;
}
int ask(int &cur,int lt,int rt,int l,int r){
    if(rt<l||r<lt){
        return 0;
    }
    if(l<=lt&&rt<=r){
        return tree[cur].sum;
    }
    int mid=(lt+rt)/2;
    int sum=0;
    sum+=ask(tree[cur].ls,lt,mid,l,r);
    sum+=ask(tree[cur].rs,mid+1,rt,l,r);
    return sum;
}
void addtag(int &cur,int lt,int rt,int l,int r,int v){
	if(lt>r||rt<l) return ;
	if(cur==0){
		cur=++tot;
	}
	if(lt==rt){
		tree[cur].sum+=v;
		return ;
	}
	int mid = (lt+rt)/2;
	addtag(tree[cur].ls,lt,mid,l,r,v);
	addtag(tree[cur].rs,mid+1,rt,l,r,v);
	pushup(cur);
}
int merge(int a,int b,int l,int r){
	if(a==0||b==0) return a+b;
	if(l==r){
		tree[a].sum+=tree[b].sum;
		return a;
	}
	int mid=(l+r)/2;
	tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);
	tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
	pushup(a);
	return a;
}
void dfs(int u,int fa){
    for(int v:edge[u]){
        if(v==fa) continue;
        dfs(v,u);
        root[u]=merge(root[u],root[v],1,inf);
    }
    ans[u]=ask(root[u],1,inf,val[u]+1,inf);
    addtag(root[u],1,inf,val[u],val[u],1);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>val[i];
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        edge[x].push_back(i);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
}

CF208E

本质上只需要维护 \(k\) 级祖先以及子树内深度为 \(x\) 的节点数量。

前者离线 dfs，后者线段树合并（下标表示深度）即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+114;
int num,a[N];
int dep[N];
vector<int> edge[N];
int root[N];
int ans[N];
vector< pair<int,int> > ask[N];//编号 ：深度 
vector<int> wyb;
int in[N];
struct Node{
	int ls,rs;
	int val;
}tree[N * 20];
int tot;
int n,q;
void pushup(int x){
	tree[x].val=tree[tree[x].ls].val+tree[tree[x].rs].val;
}
void update(int &x,int l,int r,int pos,int v){
	if(l>pos||r<pos) return ;
	if(x==0){
		x=++tot;
	}
	if(l==r&&l==pos){
		tree[x].val+=v;
		return ;
	}
	int mid=(l+r)/2;
	update(tree[x].ls,l,mid,pos,v);
	update(tree[x].rs,mid+1,r,pos,v);
	pushup(x);
}
int query(int &x,int l,int r,int pos){
	if(l>pos||r<pos){
		return 0; 
	}
	if(l==r&&l==pos){
		return tree[x].val;
	}
	int mid=(l+r)/2,sum=0;
	sum+=query(tree[x].ls,l,mid,pos);
	sum+=query(tree[x].rs,mid+1,r,pos);
	return sum;
}
int merge(int a,int b,int l,int r){
	//cout<<a<<' '<<b<<' '<<l<<' '<<r<<'\n'; 
	if(a==0||b==0){
		//cout<<a<<' '<<b<<'\n';
		return a+b; 
	}
	if(l==r){
		tree[a].val+=tree[b].val;
		//cout<<tree[a].chifan.size()<<'\n'; 
		tree[b].val=0;
		return a;
	}
	int mid=(l+r)/2;
	//cout<<tree[a].rs<<' '<<tree[b].rs<<'\n';
	tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);
	tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
	pushup(a);
	return a; 
}
vector< pair<int,int> > ASK[N];//编号 ：深度 
void dfs(int cur,int fa){
	wyb.push_back(cur);
	dep[cur]=dep[fa]+1;
	for(int u:edge[cur]){
		if(u==fa) continue;
		dfs(u,cur);
		//cout<<cur<<' '<<root[cur]<<'\n'; 
		root[cur]=merge(root[cur],root[u],1,n);
	}
	update(root[cur],1,n,dep[cur],1);
	for(int i=0;i<ask[cur].size();i++){
		int k=ask[cur][i].second;
		if(k>=wyb.size()) continue;
		int kfa=wyb[wyb.size()-k-1];
		//cout<<cur<<' '<<k<<' '<<kfa<<' '<<dep[kfa]+k<<' '<<query(root[kfa],1,n,dep[kfa]+k)<<'\n';
		ASK[kfa].push_back(make_pair(ask[cur][i].first,dep[kfa]+k));
		/*
		if(dep[cur]+ask[cur][i].second<=n){
			//cout<<ask[cur][i].first<<' '<<query(root[cur],1,n,dep[cur]+ask[cur][i].second)<<'\n';
			ans[ask[cur][i].first]=query(root[cur],1,n,dep[cur]+ask[cur][i].second);
		}
		*/
	}
	for(int i=0;i<ASK[cur].size();i++){
		//cout<<cur<<' '<<ASK[cur][i].second<<' '<<query(root[cur],1,n,ASK[cur][i].second)<<'\n';
		ans[ASK[cur][i].first]=query(root[cur],1,n,ASK[cur][i].second)-1;
	}
	wyb.pop_back(); 
}
inline void add(int u,int v){
	edge[u].push_back(v);
	edge[v].push_back(u); 
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		if(x==0) continue;
		in[i]++;
		add(x,i);
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		int x,y;
		cin>>x>>y; 
		ask[x].push_back(make_pair(i,y)); 
	} 
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			//cout<<i<<'\n';
			dfs(i,0); 
		}
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<' ';
	}
	
}

P3224

注意到所有连通块其实是在按树形结构合并。

所以对于每个连通块开一棵线段树。

合并操作就去合并两颗线段树。

查询操作就查询第 \(k\) 大即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+114;
const int inf = 1e5;
struct Node{
    int ls,rs,val,cnt;// left son right son the anser the cnt 
}tree[maxn * 20];
vector<int> edge[maxn];
int fa[maxn];
int found(int x){
	if(fa[x]==x) return x;
	else return fa[x]=found(fa[x]);
}
int n,q;
int root[maxn];
int mp[maxn];
int tot;
void pushup(int &cur){
    //cout<<tree[tree[cur].ls].cnt<<" "<<tree[tree[cur].ls].cnt<<'\n';
    tree[cur].val=tree[tree[cur].ls].val+tree[tree[cur].rs].val;
}
int kth(int &cur,int l,int r,int k)
{
	if(l==r) return l;
    int mid=(l+r)/2;
    if(tree[tree[cur].ls].val>=k){
    	return kth(tree[cur].ls,l,mid,k);
	}
	else{
		return kth(tree[cur].rs,mid+1,r,k-tree[tree[cur].ls].val);
	}
}
void addtag(int &cur,int lt,int rt,int l,int r,int v){
    if(lt>r||rt<l) return ;
    if(cur==0){
        cur=++tot;
    }
    if(lt==rt){
        tree[cur].val+=v;
        return ;
    }
    int mid = (lt+rt)/2;
    addtag(tree[cur].ls,lt,mid,l,r,v);
    addtag(tree[cur].rs,mid+1,rt,l,r,v);
    pushup(cur);
}
int merge(int a,int b,int l,int r){
    if(a==0||b==0) return a+b;
    if(l==r){
        tree[a].val+=tree[b].val;
        return a;
    }
    int mid=(l+r)/2;
    tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);
    tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
    pushup(a);
    return a;
}
int m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	fa[i]=i;
    	root[i]=++tot;
    	int u;
    	cin>>u;
    	mp[u]=i;
    	addtag(root[i],1,n,u,u,1);
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		x=found(x),y=found(y);
		root[x]=merge(root[x],root[y],1,n);
		fa[y]=x;
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		char op;
		cin>>op;
		if(op=='B'){
			int x,y;
			cin>>x>>y;
			x=found(x),y=found(y);
			root[x]=merge(root[x],root[y],1,n);
			fa[y]=x;
		}
		else{
			int x,k;
			cin>>x>>k;
			x=found(x);
			if(k>tree[root[x]].val){
				cout<<"-1\n";
			}
			else{
				cout<<mp[kth(root[x],1,n,k)]<<'\n';
			}
		}
	}
}

P5384

本质上和 CF208E 没有区别。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+114;
int num,a[N];
int dep[N];
vector<int> edge[N];
int root[N];
int ans[N];
vector< pair<int,int> > ask[N];//编号 ：深度 
vector<int> wyb;
int in[N];
struct Node{
	int ls,rs;
	int val;
}tree[N * 4];
int tot;
int n,q;
stack<int> ioi;
void pushup(int x){
	tree[x].val=tree[tree[x].ls].val+tree[tree[x].rs].val;
}
void update(int &x,int l,int r,int pos,int v){
	if(l>pos||r<pos) return ;
	if(x==0){
        if(ioi.size()==0)
		    x=++tot;
        else{
            x=ioi.top();
            ioi.pop();
        }
	}
	if(l==r&&l==pos){
		tree[x].val+=v;
		return ;
	}
	int mid=(l+r)/2;
	update(tree[x].ls,l,mid,pos,v);
	update(tree[x].rs,mid+1,r,pos,v);
	pushup(x);
}
int query(int &x,int l,int r,int pos){
	if(l>pos||r<pos){
		return 0; 
	}
	if(l==r&&l==pos){
		return tree[x].val;
	}
	int mid=(l+r)/2,sum=0;
	sum+=query(tree[x].ls,l,mid,pos);
	sum+=query(tree[x].rs,mid+1,r,pos);
	return sum;
}
int merge(int a,int b,int l,int r){
	//cout<<a<<' '<<b<<' '<<l<<' '<<r<<'\n'; 
	if(a==0||b==0){
		//cout<<a<<' '<<b<<'\n';
		return a+b; 
	}
	if(l==r){
		tree[a].val+=tree[b].val;
		//cout<<tree[a].chifan.size()<<'\n'; 
		tree[b].val=0;
        //ioi.push(b);
		return a;
	}
	int mid=(l+r)/2;
	//cout<<tree[a].rs<<' '<<tree[b].rs<<'\n';
	tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);
	tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
	pushup(a);
    ioi.push(b);
	return a; 
}
vector< pair<int,int> > ASK[N];//编号 ：深度 
void dfs(int cur,int fa){
	wyb.push_back(cur);
	dep[cur]=dep[fa]+1;
	for(int u:edge[cur]){
		if(u==fa) continue;
		dfs(u,cur);
		//cout<<cur<<' '<<root[cur]<<'\n'; 
		root[cur]=merge(root[cur],root[u],1,n);
	}
	update(root[cur],1,n,dep[cur],1);
	for(int i=0;i<ask[cur].size();i++){
		int k=ask[cur][i].second;
		if(k>=wyb.size()) continue;
		int kfa=wyb[wyb.size()-k-1];
		//cout<<cur<<' '<<k<<' '<<kfa<<' '<<dep[kfa]+k<<' '<<query(root[kfa],1,n,dep[kfa]+k)<<'\n';
		ASK[kfa].push_back(make_pair(ask[cur][i].first,dep[kfa]+k));
		/*
		if(dep[cur]+ask[cur][i].second<=n){
			//cout<<ask[cur][i].first<<' '<<query(root[cur],1,n,dep[cur]+ask[cur][i].second)<<'\n';
			ans[ask[cur][i].first]=query(root[cur],1,n,dep[cur]+ask[cur][i].second);
		}
		*/
	}
	for(int i=0;i<ASK[cur].size();i++){
		//cout<<cur<<' '<<ASK[cur][i].second<<' '<<query(root[cur],1,n,ASK[cur][i].second)<<'\n';
		ans[ASK[cur][i].first]=query(root[cur],1,n,ASK[cur][i].second)-1;
	}
	wyb.pop_back(); 
}
inline void add(int u,int v){
	edge[u].push_back(v);
	edge[v].push_back(u); 
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=2;i<=n;i++){
		int x;
		cin>>x;
		if(x==0) continue;
		in[i]++;
		add(x,i);
	}

	for(int i=1;i<=q;i++){
		int x,y;
		cin>>x>>y; 
		ask[x].push_back(make_pair(i,y)); 
	} 
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			//cout<<i<<'\n';
			dfs(i,0); 
		}
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<' ';
	}
	
}

原文链接：https://www.cnblogs.com/chifan-duck/p/17292464.html

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：动态开点线段树&线段树合并学习笔记 - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • Python贪心算法实例小结

    Python贪心算法实例小结 贪心算法是一种常用的算法，它在每一步选择中都采取在当前状态下最好最优的选择，从而望导致结果是全局最好或最优的算法。在Python中，可以使用贪心算解决多问题，包括背包问题、活动选择问题等。本文将详细讲解Python贪心算法实例，包括算法原理、Python实现过程和示例。 算法原理 贪心算法的基本思想是：每一步都选择当前状态下最好…

    python 2023年5月13日
    00

  • Python使用sklearn库实现的各种分类算法简单应用小结

    下面是关于“Python使用sklearn库实现的各种分类算法简单应用小结”的完整攻略。 1. 分类算法简介 分类法是机器学习中的一要算法，它可以将数据集中的样本分为不同的类别。Python中常用的分类算法包括决策树、KNN、朴素贝叶斯、逻辑回归、支持向量机等。 2. Python实现分类算法 2.1 决策树 决策树是一种基于树形结构的算法它通过对数据集进行…

    python 2023年5月13日
    00

  • Python实现遗传算法(二进制编码)求函数最优值方式

    下面是详细讲解“Python实现遗传算法(二进制编码)求函数最优值方式”的完整攻略，包括算法原理、Python实现和两个示例。 算法原理 遗传算法是一种基于自然选择和遗传机制的优化算法，其主要思想是通过模拟生物进化过程，寻找最优解。在二进制编码的遗传算法中，每个个体用一个二进制串表示，通过不断交叉、变异和选择操作，寻找最优解。 二进制编码的遗传算法的实现过程…

    python 2023年5月14日
    00

  • C#数据结构与算法揭秘二 线性结构

    C#数据结构与算法揭秘二 线性结构 线性结构是指数据元素之间一对一的关系，即数据元素之间存在一个前驱和一个后继。一般有两种基本形式：线性表和栈、队列。 线性表 线性表是由同类型数据元素构成有序序列的线性结构，常被用于实现基于数组的数据结构，如向量、矩阵等。 线性表可以分为顺序表和链表两种。 顺序表（Sequence List）：是把线性表的元素按照顺序存储在…

    数据结构 2023年5月17日
    00

  • C#数据结构与算法揭秘四 双向链表

    C#数据结构与算法揭秘四 双向链表 简介 本文将讲解如何在C#中实现双向链表。双向链表是一种常用的数据结构，在许多算法中都有广泛应用，它提供了与单向链表不同的灵活性和便利性。 双向链表的实现 创建一个双向节点 双向链表由节点（Node）组成。一个节点包含两个指针：一个指向前一个节点，一个指向后一个节点。由于这两个指针都可能为null，所以我们将它们声明为可空…

    数据结构 2023年5月17日
    00

  • 浅谈Python几种常见的归一化方法

    浅谈Python几种常见的归一化方法 在机器学习中，归一化是一种常用的数据预处理技术，其目的是将不同量纲的特征值缩放到相同的范内，以便更好地进行模型训练和预测。本文将介绍Python中几种常见的归一化方法，并提供两个示例说明。 1. Min-Max归一化 Min-Max归一化是一种常用的线性归一化方法，其公式如下： $${norm} = \frac{x – …

    python 2023年5月14日
    00

  • C语言数据结构图的创建与遍历实验示例

    下面是“C语言数据结构图的创建与遍历实验示例”的完整攻略。 1. 创建数据结构图 1.1 创建图对象 首先需要创建一个图对象，可以使用邻接矩阵或邻接表来表示图。使用邻接矩阵表示时，将所有顶点的编号按照一定顺序排列在矩阵的行和列上，使用0或1表示两个顶点之间是否有边。使用邻接表表示时，需要一个array存储所有的顶点，数组中的每个元素包含一个链表，链表中存储与…

    数据结构 2023年5月17日
    00

  • python实现机械分词之逆向最大匹配算法代码示例

    以下是关于“Python实现机械分词之逆向最大匹配算法代码示例”的完整攻略： 简介 逆向最大匹配算法是一种常用的机械分词算法，它通过从后往前的方式在文本中查找词语。本教程将介绍如何使用Python实现逆向最大匹配算法，并提供两个示例。 算法实现 逆向最大匹配算法是一种常用的机械分词算法，它通过从后往前的方式在文本中查找词语。具体来说，我们将文本从后往前切割成…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部