acw.241楼兰图腾（模板）

本文主要是介绍acw.241楼兰图腾（模板），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

树状模板：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<cstdlib>

using namespace std;
typedef long long ll;
const int N=2e5+10;
int n，a[N],great[N],low[N]；
int tr[N];

//树状数组 ：好调，好写 
//差分，公式 
//1)快速求前缀和logn
//2)修改某一个数logn

int lowbit(int x){  
	return x&-x;
} 
void add(int x,int c){
	for(int i=x;i<=n;i+=lowbit(i))tr[i]+=c;
} 
int sum(int x){
	int res=0;
	for(int i=x;i;i-=lowbit(i))res+=tr[i];
	return res;
}

题目：https://www.acwing.com/problem/content/243/

西部 314314 打算研究这幅壁画中包含着多少个图腾。

如果三个点 (i,yi),(j,yj),(k,yk)(i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n1≤i<j<k≤n 且 yi>yj,yj<ykyi>yj,yj<yk，则称这三个点构成 V 图腾;

如果三个点 (i,yi),(j,yj),(k,yk)(i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n1≤i<j<k≤n 且 yi<yj,yj>ykyi<yj,yj>yk，则称这三个点构成 ∧ 图腾;

西部 314314 想知道，这 nn 个点中两个部落图腾的数目。

因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。

输入格式

第一行一个数 nn。

第二行是 nn 个数，分别代表 y1，y2,…,yny1，y2,…,yn。

输出格式

两个数，中间用空格隔开，依次为 V 的个数和 ∧ 的个数。

笔记：树状数组模板+基本用法（快速求前缀和！）

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	
	for(int i=1;i<=n;i++){
		int y=a[i];//左边，比y大的和比y小的 
		great[i]=sum(n)-sum(y);
		low[i]=sum(y-1);
		add(y,1);
	}
	memset(tr,0,sizeof tr);
	ll res1,res2;
	res1=res2=0;
	for(int i=n;i;i--){
		int y=a[i];
		res1+=great[i]*(ll)(sum(n)-sum(y));
		res2+=low[i]*(ll)(sum(y-1));
		add(y,1);
	}
	cout<<res1<<" "<<res2; 
	return 0;
}

这篇关于acw.241楼兰图腾（模板）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！