前置知识点
1.树状数组
2.离散化
(!撒花!)
题目来源
·https://www.luogu.com.cn/problem/P3608
题目大意
给你一个长度为 (n) 的序列,(L_i)(R_i)分别表示i这个位置左右比ta大的数的个数,试求出满足一下条件的位置个数
[max(L_i,R_i)>2*min(L_i,R_i)
]
解题思路
因为是一个所有数不相同的序列,所以我们只需要把每个数大于等于ta的数个数开一个数组b[]离散化一下,再用树状数组去找左边比ta大的数个数
那右边呢?
用b[]减去左边在减自己不就行了(滑稽)
关于求b[],其实就是把这个元素以前的位置记下,在记下现在这个元素在降序列中的位置就行了
最后贴上代码:
#include<bits/stdc++.h>
using namespace std;
struct node
{
int val,opt;
}num[100010];
int n,ans;
int b[100010],sum[100010];
int lowbit(int x){return x & -x;}
bool Cmp(node x, node y)
{
return x.val > y.val;
}
void add(int x,int val)
{
while(x<=n)
{
sum[x] += val;
x += lowbit(x);
}
}
int query(int x)
{
int l = 0;
while(x)
{
l += sum[x];
x -= lowbit(x);
}
return l;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &num[i].val), num[i].opt = i;
sort( num + 1, num + n + 1, Cmp);
for(int i = 1; i <= n; i++)
b[num[i].opt]=i;
for(int i = 1; i <= n; i++)
{
int l=query(b[i]),r=b[i] - l - 1;
if( l * 2 < r|| r * 2< l)ans++;
add(b[i],1);
}
printf("%d
",ans);
return 0;
}