甜甜圈(树状数组)(线段树)

题目描述

艾洛喜欢吃甜食，他有n个甜甜圈，现在叠成了两叠（如下图所示），第一叠有
$n1$个，第二叠有
$n2$个
$(n1+n2=n)$，要解决的问题如下：

• ​ 每个甜甜圈都有一个唯一的甜度值$s_i$，甜度值两两不同；
• ​ 每次艾洛可以把任意一叠位于顶端的一个甜甜圈移动到另一叠顶端，若该甜甜圈是当前所有甜甜圈中最甜的（甜度值最大），那么艾洛不会移动甜甜圈，而是直接吃掉；

请你求出艾洛吃完所有甜甜圈的最小移动步数；

输入描述:

第一行，两个正整数$n1,n2(1\le n1+n2\le 100000)$，分别表示两叠甜甜圈的个数。
第二行，$n1$个整数，按从顶到底的顺序排列，表示第一叠甜甜圈的甜度值。
第三行，$n2$个整数，按从顶到底的顺序排列，表示第二叠甜甜圈的甜度值。
保证$1\le si\le 6\ast 10^6$且两两互不相同。

输出描述:

总共一行，一个整数，表示最少步数。

输入

3 3
1 4 5
2 7 3

输出

6

1. 树状数组维护

#include <bits/stdc++.h>
using namespace std;
#define MAIN signed main()
#define int long long 
const int maxn = 1e5+5;

struct Node { 
   
	int v,pos;
}a[maxn*2];

int C[maxn*2]; //树状数组
int n;
int query(int i)
{ 
   
	int ans = 0;
	while(i > 0)
	{ 
   
		ans += C[i];
		i -= i & -i;
	}
	return ans;
}

void update(int i,int x)
{ 
   
	while(i <= n)
	{ 
   
		C[i] += x;
		i += i & -i;
	}
}

MAIN
{ 
   
	int n1,n2;
	scanf("%lld%lld",&n1,&n2);
	n = n1 + n2;
	for(int i=n1;i>=1;--i) //反向存储 
	{ 
   
		scanf("%lld",&a[i].v);
		a[i].pos = i;
		update(i,1);
	}
	for(int i=n1+1;i<=n1+n2;++i) //正向存储 Value and index 
	{ 
   
		scanf("%lld",&a[i].v);
		a[i].pos = i;
		update(i,1);
	}
	
	sort(a+1,a+n+1,[](Node a,Node b){ 
   
		return a.v > b.v;
	});
	
	int p = a[1].pos;//分界线 
	update(a[1].pos,-1);
	int res = p > n1 ? (p - n1 - 1): (n1 - p);
	for(int i=2;i<=n;++i)
	{ 
   
		update(a[i].pos,-1);//减去1 变0 
		int q = abs(query(a[i].pos) - query(p)); //query
		res += q;
		p = a[i].pos;
	}
	printf("%lld\n",res);
	return 0;
}

2.线段树维护

#include <bits/stdc++.h>
using namespace std;
#define MAIN signed main()
#define int long long 
const int maxn = 1e5+5;

int n;

struct Node { 
   
	int v,pos;
}a[maxn*2];

struct tree{ 
   
    int l ,r;
    int v;
}tr[maxn*8];

void pushup(int u)
{ 
   
    tr[u].v = tr[u<<1].v + tr[u<<1|1].v;
}

void build(int u,int l,int r)
{ 
   
    tr[u] = { 
   l,r};
    if(l == r)
    { 
   
    	tr[u] = { 
   l,r,1};
    	return;
	}
    int mid = l + r >> 1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u); 
}

void modify(int u,int x,int v)
{ 
   
    if(tr[u].l==x && tr[u].r == x){ 
   
        tr[u].v = v;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(x <= mid) modify(u<<1,x,v);
    else modify(u<<1|1,x,v);
    pushup(u);
}
///查询一个区间的属性
int query(int u,int l,int r)
{ 
   
	if(l > r) swap(l,r);
    if(l <= tr[u].l && tr[u].r <= r)
        return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int res = 0;
	if(l <= mid) res +=query(u<<1,l,r);
    if(r >  mid) res += query(u<<1|1,l,r);
    return res;
}


MAIN
{ 
   
	int n1,n2;
	scanf("%lld%lld",&n1,&n2);
	n = n1 + n2;
	build(1,1,n);
	for(int i=n1;i>=1;--i) //反向存储 
	{ 
   
		scanf("%lld",&a[i].v);
		a[i].pos = i;
		modify(1,i,1);
	}
	for(int i=n1+1;i<=n1+n2;++i) //正向存储 Value and index 
	{ 
   
		scanf("%lld",&a[i].v);
		a[i].pos = i;
		modify(1,i,1);
	}
	
	sort(a+1,a+n+1,[](Node a,Node b){ 
   
		return a.v > b.v;
	});
	
	int p = a[1].pos;//分界线 
	modify(1,a[1].pos,0);
	int res = p > n1 ? (p - n1 - 1): (n1 - p);
	for(int i=2;i<=n;++i)
	{ 
   
		modify(1,a[i].pos,0);//减去1 变0 
		int q = abs(query(1,a[i].pos,p)); //query
		res += q;
		p = a[i].pos;
	}
	printf("%lld\n",res);
	return 0;
}

今天的文章甜甜圈(树状数组)(线段树)分享到此就结束了，感谢您的阅读。