题目描述
在完成了分配任务之后,西部 314 来到了楼兰古城的西部。
相传很久以前这片土地上(比楼兰古城还早)生活着两个部落,一个部落崇拜尖刀(V),一个部落崇拜铁锹(∧),他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。
西部 314 在楼兰古城的下面发现了一幅巨大的壁画,壁画上被标记出了 n 个点,经测量发现这 n 个点的水平位置和竖直位置是两两不同的。
西部 314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关,因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn),其中 y1∼yn 是 1 到 n 的一个排列。
西部 314 打算研究这幅壁画中包含着多少个图腾。
如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i[HTML_REMOVED]yj,yj<yk,则称这三个点构成 V 图腾;
如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i[HTML_REMOVED]yk,则称这三个点构成 ∧ 图腾;
西部 314 想知道,这 n 个点中两个部落图腾的数目。
因此,你需要编写一个程序来求出 V 的个数和 ∧ 的个数。
输入格式
第一行一个数 n。
第二行是 n 个数,分别代表 y1,y2,…,yn。
输出格式
两个数,中间用空格隔开,依次为 V 的个数和 ∧ 的个数。
数据范围
对于所有数据,n≤200000,且输出答案不会超过 int64。
y1 ∼ yn 是 1 到 n 的一个排列。
输入样例
5
1 5 3 2 4
输出样例:
3 4
朴素算法
(暴力枚举) $O(n^2 )$
时间复杂度
C++ 代码
//懂的都懂,找到第i个点左边比i小的数的个数再找到第i个点右边比i小的数的个数乘起来就好了
//下面是复制的一个大佬的朴素代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2000010;
typedef long long LL;
int a[N];
//ll[i]表示i的左边比第i个数小的数的个数
//rl[i]表示i的右边比第i个数小的数的个数
//lg[i]表示i的左边比第i个数大的数的个数
//rg[i]表示i的右边比第i个数大的数的个数
int ll[N], rl[N], lg[N], rg[N];
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j < i; j++)
{
//a[]保存的是1 ~ n的一个排列,不可能相等
if(a[j] < a[i]) ll[i] ++;
else lg[i] ++;
}
}
for(int i = 1; i <= n; i++)
{
for(int j = n; j > i; j--)
{
if(a[j] < a[i]) rl[i] ++;
else rg[i] ++;
}
}
LL resV = 0, resA = 0;
for(int i = 1; i <= n; i++)
{
resV += (LL)lg[i] * rg[i];
resA += (LL)ll[i] * rl[i];
}
printf("%lld %lld\n", resV, resA);
return 0;
}
//作者:qiaoxinwei
//链接:https://www.acwing.com/solution/content/13818/
//来源:AcWing
//著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
真正的算法
(树状数组优化) $O(nlogn)$
不难发现朴素算法的时间复杂度主要来自于找i的两侧比a[i]高/低的点的个数
因而我们可以把tr数组的原始数组为记录a[i]是否出现的哈希表b[i],再用树状数组t[i]来求b数组中i前后的1的个数(核心优化),即比i小的数和比i大的数的个数,即b[a[i]] = 1
好,激动人心的时候到了,我们该怎么理解树状数组呢?
树状数组的基本优化思路是分治,具体分法如下:
快速求前缀和的思路
定义数组c[x] = 原数组中长度为lowbit(x),右端点为x对应区间的区间和
假设x二进制表示为11100100
我们的思路是以它的每一位1为分界线,分成四部分(注意是左开右闭区间):
11100100
~ 11100000
-> length = 100
11100000
~ 11000000
-> length = 100000
11000000
~ 10000000
-> length = 1000000
10000000
~ 00000000
-> length = 10000000
那么怎么表示这四部分呢?很简单我们直接定义就好了,因为我们观察发现每一个区间的右端点的最低的一位1所代表的值就是区间长度(我们本来就是这么分的),
也就是说t[11100100
]表示的就是下标11100100
~ 11100000
中的数的和
这个时候显然 s[11100100
] = t[11100100
] + t[11100000
] + t[11000000
] + t[10000000
]
时间复杂度:x 二进制中 1 的数量 显然 <= log x,固时间复杂度为O(log n)
即我们可以在O(log n)的时间内求区间[1, n]的前缀和,再通过sum[r] - sum[l - 1]以相同时间复杂度求得区间[l, r]的区间和
建树思路(怎么维护 t 数组)
好的,接下来我们怎么求t[i]呢?我们肯定不能暴力区间求和(当然可以用前缀和根据定义做,即b[i] - b[i - lowbit(i)],但是那就和树状数组的‘树’没关系了)
这里再分治处理,把每一个节点等价成其子节点和其下标对应的原数组的节点的和(这里是原数组和树状数组唯一连接的地方)
再以11100100
为例,即把11100100
~ 11100000
【根据定义确定的t[x]的范围】分成三部分:
11100100
(节点本身对应的原数组的点) -即a[x]
11100011
~ 11100010
(t[11100011
]) -即t[x - 1]
11100010
~ 11100000
(t[11100010
]) -即t[x - 1 - lowbit(x - 1)]
这里和求前缀和思路几乎一样,区别是前缀和求的区间是11100100
~ 00000000
,
而t[11100100
] 求的是11100011
~ 11100000
再加上x在原数组对应的点11100100
显然这里11100011
和11100010
就是11100100
的子节点
不难看出子节点右侧一定都是111...100...000
这样的格式(都是由111...11
(x 最低位1处是100...0
,x-1 右侧就是011...1
)逐渐分治(减去lowbit(1)得到的))
看到这里你就可以轻松地画出那张经典的树形图了(建议画一下看看理解了没有)
// 通过父节点计算出对应的子节点的过程(注意父子节点只是维护数组时用的概念,实际计算前缀和的时候不会使用,所以下述代码实际上不用写出来,只需要理解子节点是怎么来的就行了)
// 假设j为奇数不能这么算,因为lowbit(奇数)=1,区间长度为1,即只有a[i],没有其他节点,也就是j不存在
int[] children;// 子节点集合
int j = parent - 1;
while(true) {
j = j - lowbit(j);
if(j == 0 || lowbit(j) >= lowbit(i)) break;
else children[cnt ++] = j;// 这里j遍历到的值就是所有i的子节点的编号
}
假设parent=10010000
则j变化的过程为:
10001111
=10010000
-1, lowbit(j)=1
10001110
=10010000
-1-1, lowbit(j)=2
10001100
=10010000
-1-1-2, lowbit(j)=4
10001000
=10010000
-1-1-2-4, lowbit(j)=8
假设某一个child对应的lowbit(child)=2^k
则从parent一路减到child的过程就是parent - 1 - 2^0 - 2^1 - 2^2 - … - 2^(k-1) = i - 2^k
即 parent - child = 1 + 2^0 + 2^1 + 2^2 + … + 2^(k-1)
等比数列求和显然 2^k = 1 + 2^0 + 2^1 + 2^2 + … + 2^(k-1)
即 parent - child = 2^k = lowbit(child);
显然这个推论对任意child都满足
child + lowbit(child) == parent//现在我们可以心安无愧地写出这个公式了
显然修改叶节点只需要一路往上找父节点再对应处理就好了(因为子节点只有一个父节点,父节点记录的是子节点的和,所以也只能直接影响到它的唯一的父节点,接下来就是相当于递归了,一直递归到根)
时间复杂度$O(nlogn)$
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 200010;
long long n,a[N],lower[N],higher[N];
int t[N];//这一步是哈希,t[i]表示高度为i的节点对应的区间[i - lowbit(i) + 1, i]中的数的个数
long long A,V;//存储结果,数据会爆int所以用long long
int lowbit(int x){//取x的最低位
return x & -x;
}
void add(int x, int k){//将下标为x的数增加k
for(int i = x; i <= n; i += lowbit(i)) t[i] += k;
}
int ask(int x){//求s[x],即下标从1到x的前缀和
int sum = 0;
for(int i = x; i; i -= lowbit(i)) sum += t[i];
return sum;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++){//因为从左往右遍历并插值,所以在调用ask函数时t中存的都是第i个节点左边的值
int y = a[i];//当前节点的高度
lower[i] = ask(y - 1);//找到当前节点左边的比高度比y小的数的个数
higher[i] = ask(n) - ask(y);//找到当前节点左边的比高度比y大的数的个数
add(y, 1);//把y插入到t数组中,相当于建树
}
memset(t, 0, sizeof t);//准备从右往左读,再建一遍树
for(int i = n; i >= 1; i --){//同理
int y = a[i];
lower[i] *= ask(y - 1); A += lower[i];//以y为最高点的总方案数为 (y左边比y低的点数) * (y右边比y低的点数)
higher[i] *= ask(n) - ask(y); V += higher[i];////以y为最低点的总方案数为 (y左边比y高的点数) * (y右边比y高的点数)
add(y, 1);
}
cout << V << " " << A;
return 0;
}
兄弟的代码注释写的很清楚,自己想明白了哈哈哈,牛的牛的!!主要是想明白了为什么还要建立一棵树!谢谢谢谢!!!很感谢哈哈哈哈
确实,我想了好久
不是点进来自动学会吗?要看完?溜了溜了
牛的哈哈哈哈
higher[i] = ask(n) - ask(y);//找到当前节点左边的比高度比y小的数的个数
这里应该是找到当前节点左边的高度比 y 高 的数的个数
看y总的讲解一直在搞特殊情况,比如说一串数里面只有一个1,-1完了后面全是1,我就理解不了当x = 10时怎么变换;看了大佬的分析后豁然开朗,全明白了,大佬太强了,orz
为什么
ask(n) - ask(y)
就是左边比它大的数据最大就是n
orz
y总讲的没听懂,看你的题解直接懂了 ,感谢
朴素做法的时间复杂度应该为O(n2)啊
改了改了
HTML废了