正文 

当前位置： 首页 > 开发 > java教程

树套树乱讲的代码(代码片段)

租酥雨 租酥雨     2022-10-22     346

关键词：

树套树乱讲的代码

由于部分代码的完成时间较早所以码风可能有些差异，敬请谅解。

动态区间Kth

题面
整体二分题解

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10005;
struct segment_treeint v;int ls,rs;t[N*200];
struct operationbool b;int l,r,k;int pos,t;q[N];
int n,m,a[N],o[N<<1],rt[N],len,tot,temp[2][20],cnt[2];
char opt;
void Modify(int &now,int l,int r,int pos,int val)

	if (!now) now=++tot;
	t[now].v+=val;
	if (l==r) return;
	int mid=l+r>>1;
	if (pos<=mid) Modify(t[now].ls,l,mid,pos,val);
	else Modify(t[now].rs,mid+1,r,pos,val);

void PreModify(int x,int val)

	int k=lower_bound(o+1,o+len+1,a[x])-o;
	for (int i=x;i<=n;i+=i&-i) Modify(rt[i],1,len,k,val);

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[1];i++) sum+=t[t[temp[1][i]].ls].v;
	for (int i=1;i<=cnt[0];i++) sum-=t[t[temp[0][i]].ls].v;
	if (k<=sum)
	
		for (int i=1;i<=cnt[1];i++) temp[1][i]=t[temp[1][i]].ls;
		for (int i=1;i<=cnt[0];i++) temp[0][i]=t[temp[0][i]].ls;
		return Query(l,mid,k);
	
	else
	
		for (int i=1;i<=cnt[1];i++) temp[1][i]=t[temp[1][i]].rs;
		for (int i=1;i<=cnt[0];i++) temp[0][i]=t[temp[0][i]].rs;
		return Query(mid+1,r,k-sum);
	

int PreQuery(int l,int r,int k)

	memset(temp,0,sizeof(temp));
	cnt[0]=cnt[1]=0;
	for (int i=r;i;i-=i&-i) temp[1][++cnt[1]]=rt[i];
	for (int i=l-1;i;i-=i&-i) temp[0][++cnt[0]]=rt[i];
	return Query(1,len,k);

int main()

	ios::sync_with_stdio(false);
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i],o[++len]=a[i];
	for (int i=1;i<=m;i++)
	
		cin>>opt;
		q[i].b=(opt==\'Q\');
		if (q[i].b)	cin>>q[i].l>>q[i].r>>q[i].k;
		else cin>>q[i].pos>>q[i].t,o[++len]=q[i].t;
	
	sort(o+1,o+len+1);
	len=unique(o+1,o+len+1)-o-1;
	for (int i=1;i<=n;i++) PreModify(i,1);
	for (int i=1;i<=m;i++)
	
		if (q[i].b)
			printf("%d\\n",o[PreQuery(q[i].l,q[i].r,q[i].k)]);
		else
		
			PreModify(q[i].pos,-1);
			a[q[i].pos]=q[i].t;
			PreModify(q[i].pos,1);
		
	
	return 0;

三维偏序（陌上花开）

题面

#include<cstdio>
#include<algorithm>
using namespace std;
int gi()

    int x=0,w=1;char ch=getchar();
    while ((ch<\'0\'||ch>\'9\')&&ch!=\'-\') ch=getchar();
    if (ch==\'-\') w=0,ch=getchar();
    while (ch>=\'0\'&&ch<=\'9\') x=(x<<3)+(x<<1)+ch-\'0\',ch=getchar();
    return w?x:-x;

const int N = 200005;
struct node
    int a,b,c,cnt,ans;
    bool operator < (const node &zsy) const
		
			if (a!=zsy.a) return a<zsy.a;
			if (b!=zsy.b) return b<zsy.b;
			return c<zsy.c;
		
	bool operator == (const node &zsy) const
		return a==zsy.a&&b==zsy.b&&c==zsy.c;
p[N],q[N];
struct segment_treeint ls,rs,sum;t[N*200];
int n,k,m,rt[N],cnt,tot[N];
void modify(int &x,int l,int r,int p,int v)

	if (!x) x=++cnt;t[x].sum+=v;
	if (l==r) return; int mid=l+r>>1;
	if (p<=mid) modify(t[x].ls,l,mid,p,v);
	else modify(t[x].rs,mid+1,r,p,v);

int query(int x,int l,int r,int ql,int qr)

	if (!x||(l>=ql&&r<=qr)) return t[x].sum;
	int mid=l+r>>1,s=0;
	if (ql<=mid) s+=query(t[x].ls,l,mid,ql,qr);
	if (qr>mid) s+=query(t[x].rs,mid+1,r,ql,qr);
	return s;

int main()

	n=gi();k=gi();
	for (int i=1;i<=n;++i)
		p[i]=(node)gi(),gi(),gi();
	sort(p+1,p+n+1);
	for (int i=1;i<=n;++i)
		if (p[i]==q[m]) ++q[m].cnt;
		else q[++m]=p[i],q[m].cnt=1;
	for (int i=1;i<=m;++i)
	
		for (int j=q[i].b;j;j-=j&-j)
			q[i].ans+=query(rt[j],1,k,1,q[i].c);
		tot[q[i].ans+q[i].cnt-1]+=q[i].cnt;
		for (int j=q[i].b;j<=k;j+=j&-j)
			modify(rt[j],1,k,q[i].c,q[i].cnt);
	
	for (int i=0;i<n;++i)
		printf("%d\\n",tot[i]);
	return 0;

二逼树套树

题面

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 50005;
struct treeint ls,rs,num;t[N*200];
struct queryint opt,l,r,pos,k;q[N];
int n,m,a[N],o[N<<1],len,rt[N],tot,temp[2][20],cnt[2];
int gi()

    int x=0,w=1;char ch=getchar();
    while ((ch<\'0\'||ch>\'9\')&&ch!=\'-\') ch=getchar();
    if (ch==\'-\') w=0,ch=getchar();
    while (ch>=\'0\'&&ch<=\'9\') x=(x<<3)+(x<<1)+ch-\'0\',ch=getchar();
    return w?x:-x;

void Modify(int &x,int l,int r,int pos,int v)

    if (!x) x=++tot;
    t[x].num+=v;
    if (l==r) return;
    int mid=l+r>>1;
    if (pos<=mid) Modify(t[x].ls,l,mid,pos,v);else Modify(t[x].rs,mid+1,r,pos,v);

int Query(int x,int l,int r,int ql,int qr)

    if (l>=ql&&r<=qr) return t[x].num;
    int mid=l+r>>1,s=0;
    if (ql<=mid) s+=Query(t[x].ls,l,mid,ql,qr);
    if (qr>mid) s+=Query(t[x].rs,mid+1,r,ql,qr);
    return s;

int Find(int l,int r,int k)

    if (l==r) return l;
    int mid=l+r>>1,sum=0;
    for (int i=1;i<=cnt[1];i++) sum+=t[t[temp[1][i]].ls].num;
    for (int i=1;i<=cnt[0];i++) sum-=t[t[temp[0][i]].ls].num;
    if (k<=sum)
    
        for (int i=1;i<=cnt[1];i++) temp[1][i]=t[temp[1][i]].ls;
        for (int i=1;i<=cnt[0];i++) temp[0][i]=t[temp[0][i]].ls;
        return Find(l,mid,k);
    
    else
    
        for (int i=1;i<=cnt[1];i++) temp[1][i]=t[temp[1][i]].rs;
        for (int i=1;i<=cnt[0];i++) temp[0][i]=t[temp[0][i]].rs;
        return Find(mid+1,r,k-sum);
    

void Update(int pos,int v)

    for (int i=pos;i<=n;i+=i&-i)
        Modify(rt[i],1,len,a[pos],v);

int Sum(int l,int r,int ql,int qr)

    if (ql>qr) return 0;
    int sum=0;
    for (int j=r;j;j-=j&-j) sum+=Query(rt[j],1,len,ql,qr);
    for (int j=l-1;j;j-=j&-j) sum-=Query(rt[j],1,len,ql,qr);
    return sum;

int Rank(int l,int r,int k)

    cnt[1]=cnt[0]=0;
    for (int j=r;j;j-=j&-j) temp[1][++cnt[1]]=rt[j];
    for (int j=l-1;j;j-=j&-j) temp[0][++cnt[0]]=rt[j];
    return o[Find(1,len,k)];

int main()

    n=gi();m=gi();
    for (int i=1;i<=n;i++) o[++len]=a[i]=gi();
    for (int i=1;i<=m;i++)
    
        q[i].opt=gi();
        if (q[i].opt!=3) q[i].l=gi(),q[i].r=gi();
        else q[i].pos=gi();
        q[i].k=gi();
        if (q[i].opt!=2) o[++len]=q[i].k;
    
    sort(o+1,o+len+1);
    len=unique(o+1,o+len+1)-o-1;
    for (int i=1;i<=n;i++)
    
        a[i]=lower_bound(o+1,o+len+1,a[i])-o;
        Update(i,1);
    
    for (int i=1;i<=m;i++)
    
        if (q[i].opt!=2) q[i].k=lower_bound(o+1,o+len+1,q[i].k)-o;
        if (q[i].opt==1)
            printf("%d\\n",Sum(q[i].l,q[i].r,1,q[i].k-1)+1);
        if (q[i].opt==2)
            printf("%d\\n",Rank(q[i].l,q[i].r,q[i].k));
        if (q[i].opt==3)
        
            Update(q[i].pos,-1);
            a[q[i].pos]=q[i].k;
            Update(q[i].pos,1);
        
        if (q[i].opt==4)
        
            int sum=Sum(q[i].l,q[i].r,1,q[i].k-1);
            if (!sum) printf("-2147483647\\n");
            else printf("%d\\n",Rank(q[i].l,q[i].r,sum));
        
        if (q[i].opt==5)
        
            int sum=Sum(q[i].l,q[i].r,1,q[i].k);
            if (sum==q[i].r-q[i].l+1) printf("2147483647\\n");
            else printf("%d\\n",Rank(q[i].l,q[i].r,sum+1));
        
        
    
    return 0;

[ZJOI2013]K大数查询

题面
整体二分题解

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 50005;
#define ll long long
struct segment_tree
	int ls,rs,tim;ll num;
t[N*300];
int n,m,rt[N*16],tot;
int gi()

	int x=0,w=1;char ch=getchar();
	while ((ch<\'0\'||ch>\'9\')&&ch!=\'-\') ch=getchar();
	if (ch==\'-\') w=0,ch=getchar();
	while (ch>=\'0\'&&ch<=\'9\') x=(x<<3)+(x<<1)+ch-\'0\',ch=getchar();
	return w?x:-x;

void Modify(int &x,int l,int r,int ql,int qr)

	if (!x) x=++tot;
	if (l==ql&&r==qr) t[x].tim++;return;
	t[x].num+=qr-ql+1;
	int mid=l+r>>1;
	if (qr<=mid) Modify(t[x].ls,l,mid,ql,qr);
	else if (ql>mid) Modify(t[x].rs,mid+1,r,ql,qr);
	else Modify(t[x].ls,l,mid,ql,mid),Modify(t[x].rs,mid+1,r,mid+1,qr);

ll Query(int x,int l,int r,int ql,int qr)

	ll res=1ll*t[x].tim*(qr-ql+1);
	if (l==ql&&r==qr) return res+t[x].num;
	int mid=l+r>>1;
	if (qr<=mid) return res+Query(t[x].ls,l,mid,ql,qr);
	else if (ql>mid) return res+Query(t[x].rs,mid+1,r,ql,qr);
	else return res+Query(t[x].ls,l,mid,ql,mid)+Query(t[x].rs,mid+1,r,mid+1,qr);

int main()

	n=gi();m=gi();
	while (m--)
	
		int opt=gi(),a=gi(),b=gi(),c=gi(),now=1,l=1,r=n;
		if (opt==1)
			while (233)
			
				Modify(rt[now],1,n,a,b);
				if (l==r) break;
				int mid=l+r>>1;
				if (c<=mid) now=now<<1,r=mid;
				else now=now<<1|1,l=mid+1;
			
		else
			while (l<r)
			
				ll sum=Query(rt[now<<1|1],1,n,a,b);
				int mid=l+r>>1;
				if ((ll)c<=sum)
					now=now<<1|1,l=mid+1;
				else c-=sum,now=now<<1,r=mid;
			
		if (opt==2) printf("%d\\n",l);
	
	return 0;

[CTSC2008]网络管理

题面
整体二分题解
这份代码应该是我现在的码风

#include<cstdio>
#include<algorithm>
using namespace std;
int gi()

	int x=0,w=1;char ch=getchar();
	while ((ch<\'0\'||ch>\'9\')&&ch!=\'-\') ch=getchar();
	if (ch==\'-\') w=0,ch=getchar();
	while (ch>=\'0\'&&ch<=\'9\') x=(x<<3)+(x<<1)+ch-\'0\',ch=getchar();
	return w?x:-x;

const int N = 8e4+5;
struct segment_treeint ls,rs,v;t[N*200];
struct operationint k,a,b;q[N];
int n,m,val[N],to[N<<1],nxt[N<<1],head[N],cnt,o[N<<1],len;
int fa[N],dep[N],sz[N],son[N],top[N],dfn[N];
int rt[N],tot,tmp1[N],tmp2[N],t1,t2;
void link(int u,int v)to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
void dfs1(int u,int f)

	fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
	for (int e=head[u];e;e=nxt[e])
	
		int v=to[e];if (v==f) continue;
		dfs1(v,u);
		sz[u]+=sz[v];if (sz[v]>sz[son[u]]) son[u]=v;
	

void dfs2(int u,int up)

	top[u]=up;dfn[u]=++cnt;
	if (son[u]) dfs2(son[u],up);
	for (int e=head[u];e;e=nxt[e])
		if (to[e]!=fa[u]&&to[e]!=son[u])
			dfs2(to[e],to[e]);

int getlca(int u,int v)

	while (top[u]!=top[v])
	
		if (dep[top[u]]<dep[top[v]]) swap(u,v);
		u=fa[top[u]];
	
	return dep[u]<dep[v]?u:v;

void Modify(int &x,int l,int r,int p,int v)

	if (!x) x=++tot;t[x].v+=v;
	if (l==r) return;int mid=l+r>>1;
	if (p<=mid) Modify(t[x].ls,l,mid,p,v);
	else Modify(t[x].rs,mid+1,r,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<=t1;++i) sum+=t[t[tmp1[i]].rs].v;
	for (int i=1;i<=t2;++i) sum-=t[t[tmp2[i]].rs].v;
	if (k<=sum)
	
		for (int i=1;i<=t1;++i) tmp1[i]=t[tmp1[i]].rs;
		for (int i=1;i<=t2;++i) tmp2[i]=t[tmp2[i]].rs;
		return Query(mid+1,r,k);
	
	else
	
		for (int i=1;i<=t1;++i) tmp1[i]=t[tmp1[i]].ls;
		for (int i=1;i<=t2;++i) tmp2[i]=t[tmp2[i]].ls;
		return Query(l,mid,k-sum);
	

void PreModify(int k,int p,int v)

	for (int i=k;i<=n;i+=i&-i)
		Modify(rt[i],1,len,p,v);

int PreQuery(int u,int v,int k)

	t1=t2=0;
	for (int i=dfn[u];i;i-=i&-i) tmp1[++t1]=rt[i];
	for (int i=dfn[v];i;i-=i&-i) tmp1[++t1]=rt[i];
	int lca=getlca(u,v);
	for (int i=dfn[lca];i;i-=i&-i) tmp2[++t2]=rt[i];
	for (int i=dfn[fa[lca]];i;i-=i&-i) tmp2[++t2]=rt[i];
	return Query(1,len,k);

int main()

	n=gi();m=gi();
	for (int i=1;i<=n;++i) val[i]=o[++len]=gi();
	for (int i=1;i<n;++i)
	
		int u=gi(),v=gi();
		link(u,v);link(v,u);
	
	for (int i=1;i<=m;++i)
	
		q[i]=(operation)gi(),gi(),gi();
		if (q[i].k==0) o[++len]=q[i].b;
	
	sort(o+1,o+len+1);len=unique(o+1,o+len+1)-o-1;
	for (int i=1;i<=n;++i)
		val[i]=lower_bound(o+1,o+len+1,val[i])-o;
	for (int i=1;i<=m;++i)
		if (q[i].k==0) q[i].b=lower_bound(o+1,o+len+1,q[i].b)-o;
	dfs1(1,0);cnt=0;dfs2(1,1);
	for (int i=1;i<=n;++i)
		PreModify(dfn[i],val[i],1),PreModify(dfn[i]+sz[i],val[i],-1);
	for (int i=1;i<=m;++i)
	
		if (q[i].k==0)
		
			PreModify(dfn[q[i].a],val[q[i].a],-1);
			PreModify(dfn[q[i].a]+sz[q[i].a],val[q[i].a],1);
			val[q[i].a]=q[i].b;
			PreModify(dfn[q[i].a],val[q[i].a],1);
			PreModify(dfn[q[i].a]+sz[q[i].a],val[q[i].a],-1);
		
		else
		
			int emm=dep[q[i].a]+dep[q[i].b]-2*dep[getlca(q[i].a,q[i].b)]+1;
			if (q[i].k>emm) puts("invalid request!");
			else printf("%d\\n",o[PreQuery(q[i].a,q[i].b,q[i].k)]);
		
	
	return 0;

[HNOI2016]网络

题面

#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

const int MAX=200005;

struct segment_tree

    priority_queue<int>num,del;
    void PUSH(int x,int type)
    
        if (!type) num.push(x);
        else del.push(x);
    
    int TOP()
    
        while (!del.empty()&&num.top()==del.top()) num.pop(),del.pop();
        if (!num.empty()) return num.top();
        return -1;
    
t[MAX<<2];
struct eventint u,v,val;sth[MAX];
struct edgeint to,next;a[MAX<<1];
struct intervalint l,r;qu[MAX];
int head[MAX],fa[MAX],dep[MAX],sz[MAX],son[MAX],top[MAX],dfn[MAX];
int n,m,cnt;

int gi()

    int x=0,w=1;char ch=getchar();
    while ((ch<\'0\'||ch>\'9\')&&ch!=\'-\') ch=getchar();
    if (ch==\'-\') w=-1,ch=getchar();
    while (ch>=\'0\'&&ch<=\'9\')
    
        x=(x<<3)+(x<<1)+ch-\'0\';
        ch=getchar();
    
    return x*w;


bool cmp(interval x,interval y)

    return x.l<y.l;


void Link(int u,int v)

    a[++cnt]=(edge)v,head[u];
    head[u]=cnt;


void dfs1(int u,int f)

    fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
    for (int e=head[u];e;e=a[e].next)
    
        int v=a[e].to;
        if (v==f) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if (sz[v]>sz[son[u]]) son[u]=v;
    

void dfs2(int u,int up)

    top[u]=up;dfn[u]=++cnt;
    if (son[u]) dfs2(son[u],up);
    for (int e=head[u];e;e=a[e].next)
    
        int v=a[e].to;
        if (v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    


void Modify(int now,int l,int r,int ql,int qr,int val,int type)

    if (l>=ql&&r<=qr)
    
        t[now].PUSH(val,type);
        return;
    
    int mid=l+r>>1;
    if (ql<=mid) Modify(now<<1,l,mid,ql,qr,val,type);
    if (qr>mid) Modify(now<<1|1,mid+1,r,ql,qr,val,type);


int Query(int now,int l,int r,int pos)

    if (l==r) return t[now].TOP();
    int mid=l+r>>1,res=t[now].TOP();
    if (pos<=mid) res=max(res,Query(now<<1,l,mid,pos));
    else res=max(res,Query(now<<1|1,mid+1,r,pos));
    return res;


void Work(int u,int v,int val,int type)

    cnt=0;
    while (top[u]!=top[v])
    
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        qu[++cnt]=(interval)dfn[top[u]],dfn[u];
        u=fa[top[u]];
    
    if (dep[u]>dep[v]) swap(u,v);
    qu[++cnt]=(interval)dfn[u],dfn[v];
    sort(qu+1,qu+cnt+1,cmp);
    qu[0].r=0;qu[++cnt].l=n+1;
    for (int i=1;i<=cnt;i++) if (qu[i].l-qu[i-1].r>=2) Modify(1,1,n,qu[i-1].r+1,qu[i].l-1,val,type);


int main()

    n=gi();m=gi();
    for (int i=1;i<n;i++)
    
        int u=gi(),v=gi();
        Link(u,v);Link(v,u);
    
    dfs1(1,0);cnt=0;dfs2(1,1);
    for (int i=1;i<=m;i++)
    
        int type=gi();
        if (!type)
        
            int u=gi(),v=gi(),val=gi();
            sth[i]=(event)u,v,val;
            Work(u,v,val,type); 
        
        else if (type==1)
        
            int k=gi();
            Work(sth[k].u,sth[k].v,sth[k].val,type);
        
        else
        
            int u=gi();
            printf("%d\\n",Query(1,1,n,dfn[u]));
        
    
    return 0;

树套树(代码片段)

树套树一种思想，就是一棵树的节点是另一颗树。在外面的叫外层树，在里面的叫内层树。外层树一般是，树状数组，线段树内层树一般是平衡树，STL,线段树线段树套STL/**@Author:zhl*@Date:2020-11-1612:50:32*/#include<bits/stdc++.h>#define... 查看详情

树套树初探(代码片段)

最近学了学树套树，做了几道模板题。发现好像有点水咳咳咳。树套树，顾名思义，一个树套一个树。比如树状数组套平衡树，就是把树状数组的每一个结点作为一颗平衡树，线段树套权值线段树，就是一颗线段树，每一个结点... 查看详情

树套树浅谈(代码片段)

今天来说一下线段树套Splay。顺便我也来重新敲一遍模板。首先，明确一下Splay套线段树用来处理什么问题。它可以支持：插入x，删除x，单点修改，查询x在区间[l,r]的排名，查询区间[l,r]中排名为k的数，以及一个数在区间[l,r]中... 查看详情

uvalive-6709树套树(代码片段)

...法：暴力可过，建n颗线段树暴力更新，但是正解应该是树套树，树套树需要注意的是当建树或修改时pushup操作不能直接搞，要先判断是不是外面层的叶子节点，如果是直接修改，如果不是，应该是从外面层的对应子节点更新过... 查看详情

hdu4819mosaic树套树(代码片段)

...点变成这个矩形中最大值和最小值的平均数思路很显然的树套树啊就是一开始傻逼了没想到怎么去维护这个东西其实很简单对于每个内层树，如果属于外层树的叶子节点，那么可以直接暴力更新，复杂度(O(log(n)))voidmodify_y(intt,intl... 查看详情

「题解」树套树tree(代码片段)

本文将同步发布于：洛谷博客；csdn；博客园；简书。题目题目描述给你一个\\(n\\)个点的小树（正常的树），给你一个\\(m\\)个点的大树，大树的节点是一棵小树，大树的边是跨越了两棵小树之间的边，\\(q\\)次询问，求树上距离... 查看详情

hdu6096树套树(代码片段)

思路：网上的题解有AC自动机的，有trie树的，还有（乱搞？）的 首先把输入的那n个串按照字典序排序，把n个串翻转以后再按照字典序排序这样我们发现，查的前缀在字典序排序后是一段区间，查的后缀翻转一下在翻转后的... 查看详情

主席树乱讲

主席树乱讲前置技能线段树：动态开点，标记永久化，基本操作离散化介绍主席树即可持久化线段树，也叫作函数式线段树至于为什么叫做主席树，据说是一个叫HJT的神犇在考场上现场yy出来的可持久化线段树：顾名思义就是线... 查看详情

「luogu3380」模板二逼平衡树（树套树）(代码片段)

「luogu3380」【模板】二逼平衡树（树套树）传送门我写的树套树——线段树套平衡树。线段树上的每一个节点都是一棵( extFHQTreap)，然后我们就可以根据平衡树的基本操作以及线段树上区间信息可合并的性质来实现了，具体细节... 查看详情

4889:[tjoi2017]不勤劳的图书管理员树套树(代码片段)

...惯例的题面(Bzoj没有，洛谷找的):动态加权逆序对，一眼树套树。256MB内存，5e4范围，不虚不虚。首先把交换改成两个插入和两个删除。考虑插入和删除的贡献，就是统计前面比这个值大的数的数值和，数量和，后面比这个值小的... 查看详情

97:cf983e倍增+树套树(代码片段)

$des$一棵$n$个点的树，树上有$m$条双向的公交线路，每条公交线路都在两个节点之间沿最短路径往返。$q$次询问从一个点要到达另一个点，在只坐公交的情况下，至少需要坐几辆公交车；或者判断无法只坐公交到达。$n,m,q<=2 ime... 查看详情

线段树树套树杭电ojluckandlove(代码片段)

博客主页:https://blog.csdn.net/qq_50285142欢迎点赞👍收藏✨关注❤留言📝如有错误，敬请指正🎈虽然生活很难，但我们也要一直走下去🎈题目链接思路：问题是要询问满足两个区间的最大缘分值，因为... 查看详情

树套树(代码片段)

历时三天终于打过了树套树 激动激动激动写个博客纪念一下  二逼平衡树~//luogu-judger-enable-o2#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<cmath>#include<stack>#include<queue>usingna... 查看详情

二逼平衡树（树套树）(代码片段)

第一次写树套树，在一定帮助下学习，调码3h。用线段树套平衡树，对于区间内排名的查询可以解决了；//$O(log^2n)$对于查询区间排名为k的数，二分答案再判断；//$O(log^3n)$修改数值直接修改；//$O(log^2n)$前驱后继，线段树递归区间... 查看详情

二维线段树之树套树(代码片段)

1//poj1195二维线段树之树套树2//先确定横坐标所在的区间并记录该结点的编号p，然后再确定纵坐标所在的区间并记录该结点的编号cur，则tree[cur][p]为目标区间。3#include<cstdio>4#include<cstdlib>5#include<cstring>6#include<cmath&g... 查看详情

洛谷p3380模板二逼平衡树（树套树，树状数组，线段树）(代码片段)

洛谷题目传送门emm。。。题目名写了个平衡树，但是这道题的理论复杂度最优解应该还是树状数组套值域线段树吧。就像dynamicranking那样（蒟蒻的Sol,放一个link骗访问量233）所有的值（包括初始a数组，操作1、3、4、5的k）全部先... 查看详情

模板二逼平衡树（树套树）(代码片段)

...但是码量绝对是很大的一种方法居然控制在了6KB以内线段树套红黑树（逃这是一次前所未有的尝试因为线段树套平衡树求区间第(k)小复杂度是(mathrmO(log^3n))的所以速度比不上树状数组套线段树但是应该在线段树套平衡树的代码中... 查看详情

「模板」树套树

「模板」树套树<题目链接>线段树套SBT。有生以来写过的最长代码。虽然能过，但我删除SBT点的时候没回收内存！写了就RE！先放上来吧，回收内存调出来了再修改qwq。#include<algorithm>#include<climits>#include<cstdio>usin... 查看详情