首页 > 其他分享 >树状数组

树状数组

时间:2022-08-29 21:58:02浏览次数:50  
标签:200005 树状 int res sum 数组 ans include

241. 楼兰图腾

 分别统计i位置左边比a[i]小的数的个数m、右边比a[i]小的数的个数n,运用乘法原理:
1. 第一步从左边m个数中任选一个,有m种选法
2. 第二步从右边n个数中任选一个,有n种选法

权值树状数组,统计比自己大的和。

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int c[200005], a[200005], n, h[200005], l[200005];
ll res, ans;
int lowbit(int x){
	return x & (-x);
}
void add(int i, int x){
	for(; i <= n; i += lowbit(i))
		c[i] += x;	 
}
int sum(int i){
	int sm = 0;
	for(; i; i -= lowbit(i))
		sm += c[i];
	return sm;
}
int main(){
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
		scanf("%d",&a[i]);
	for(int i = 1; i <= n; i++){
		h[i] = sum(n) - sum(a[i]);
		l[i] = sum(a[i]-1);
		add(a[i], 1);
	}
	memset(c, 0, sizeof c);
	for(int i = n; i >= 1; i--){
		ans += 1ll * h[i] * (sum(n) - sum(a[i]));
		res += 1ll * l[i] * sum(a[i]-1);
		add(a[i], 1);
	}
	printf("%lld %lld",ans, res);
	return 0;
} 

 

标签:200005,树状,int,res,sum,数组,ans,include
From: https://www.cnblogs.com/caterpillor/p/16637518.html

相关文章

  • Gym 101775J Straight Master(差分数组)
    题意:给你n个高度,再给你1n每种高度的数量,已知高度连续的35个能消去,问你所给的情况能否全部消去;例:n=4,给出序列1221表示高度1的1个,高度2的2个,高度3的2个,高度4的1个。那......
  • 稀疏数组
    1.当一个数组中大部分元素为0,或者为同一值的数组时,可以使用稀疏数组来保存该数组。2.处理方式为记录数组共几行几列把具有不同值的元素和行列及值记录在一个小规模数组......
  • numpy 数组 浅拷贝 地址
    对于numpy数组:importnumpyasnpa=np.array([1,2,3,4])b=a[0:2]b[0]=np.sum(a[:])/4修改b[0]的值会改变a的值,原因:https://blog.csdn.net/AManFromEarth/arti......
  • 数组
    1.长度是固定的,一旦被创建,大小就不能改变。2.元素类型必须相同。3.数据元素可以是任何数据类型,包括基本类型和引用类型。4..数组变量本身属于引用类型,也可以看出是对象,......
  • leetcode 每日一题 1470. 重新排列数组
    leetcode 每日一题 1470.重新排列数组classSolution{publicint[]shuffle(int[]nums,intn){int[]arr=newint[nums.length];for(......
  • 【leetcode】81. 搜索旋转排序数组 II
    原题地址:https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/用循环遍历数组肯定能轻松找到target但要尽可能减少操作步骤,一般跟顺序有关的都是用二分,关键......
  • maybe_serialize() | WordPress序列化数据/数组/对象
    函数maybe_serialize(string|array|object$data)描述该WordPress函数可将数组/对象/字符串序列化。参数$data,(string|array|object)需要序列化的数据。返回值(m......
  • C++ 多维数组的访问
    1.可以把一维数组想象成一排士兵,把二维数组想象成一个士兵方阵,把三维数组想象成多个士兵方阵。这样,当你要找其中的一个士兵时,你只要知道他在哪个方阵(从0、1、2中选择),在哪......
  • 数组方法中 push() 和 unshift() 的区别
    数组方法有很多,而且用到的频率也是很高,特别是push()方法,而与之对应的另一个方法就是unshift(),那么这两个方法有什么区别呢??......
  • 刷题篇。树、图、数组等相关常见处理操作
    一、树 序号做什么方法伪码 1前、中、后遍历    2以任意节点为根重构树    ......