Tyvj Jan楼兰图腾


题意就是求出一个数左边比他大/小的数和右边比他大/小的数,用乘法原理计算出结果即可,可以类比树状数组解决逆序对的问题,对值域建立一个树状数组,倒序查询加入来得到右边,正序查询插入得到左边

#include<bits/stdc++.h>
using namespace std;
const int maxn=200500;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int n,c[maxn],a[maxn],l[maxn],r[maxn];
long long ans=0;
inline int lowbit(int x){return x&-x;}
inline void add(int x,int p)
{
    while(x<=200000)
    {
        c[x]+=p;
        x+=lowbit(x);
    }
}
inline int query(int x)
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=n;i>=1;i--)
    {
        r[i]=query(200000)-query(a[i]);
        add(a[i],1);
    }
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)
    {
        l[i]=query(200000)-query(a[i]);
        add(a[i],1);
    }
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++) ans+=l[i]*r[i];
    printf("%lld ",ans);
    ans=0;
    memset(l,0,sizeof(l));memset(r,0,sizeof(r));
    for(int i=n;i>=1;i--)
    {
        r[i]=query(a[i]-1);
        add(a[i],1);
    }
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)
    {
        l[i]=query(a[i]-1);
        add(a[i],1);
    }
    for(int i=1;i<=n;i++) ans+=l[i]*r[i];
    printf("%lld\n",ans);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
P1991无线通讯 P1991无线通讯
个人认为这道题还稍微有点难想,首先我们把每个点之间的距离都处理一下方便以后使用(记住要用double!!!)然后我们要都能覆盖的最小值,其实可以用二分处理,但我们可以跑个kruskal,然后从最大边开始往前加S个,即为最小 #includ
2019-07-05
下一篇 
CF888E Maximum Subsequence CF888E Maximum Subsequence
首先我们看到数据范围$n\leq 35$加上每个数都可能取或不取,这样$2^{35}$的状态量自然是太大了,但对于这种取或不取实现一系列要求有个很常见的作法就是Meet-in-the-middle,也可以当成折半搜索,对于前一半选一些数,再
2019-07-05
  目录