注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

爆裂吧世界(world/1S/64M)  

2016-08-05 10:01:49|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
【题目描述】 给你一个长度为n的数列A,请你计算里面有多少个四元组(a,b,c,d)满足:  a≠b≠c≠d,1≤a<b≤n,1≤c<d≤n,Aa<Ab,Ac>Ad  
【输入格式】 输入文件第一行有一个整数N,第二行有N个整数A1,A2?An  
【输出格式】 输出文件仅一行,为一个整数,表示满足条件的四元组的数量

【数据约定】

15% n<=100   

100%n<=50000

======================================
        简洁的题目,反正yhf第一次不会做,打了个暴力15分O(n^3)。
        正解其实三步。
        第一:离散化
        第二:用树状数组以logn的速度求出第i位前面有几个小于它的数(同理求出第i位前/后面有几个大/小于它的数
        第三:运用容斥原理,克服a≠b≠c≠d大难关,求出最终答案。
======================================
        有不少蒟蒻要问了,树状数组可以干这个(需要离散化减少规模)!没错,这有点类似数组计数,把每个出现过的数+1,和数组计数一样假如你要求小于K的有几个,就把数组的1~K-1加起来就可以了,没错,加起来,就是树状数组的特长。为了求前i位,就要动态增加求和了,呃,这不是树状数组最最最擅长的吗?贴一小段代码:

for (int i=1; i<=n; i++)
{
smaller_left[i]=Sum(a[i]-1); //求1~a[i]-1的和
Add(a[i]); //+1
}

        现在,我们要考虑第三步了,在a≠b≠c≠d,1≤a<b≤n,1≤c<d≤n,Aa<Ab,Ac>Ad 中,如果没有a≠b≠c≠d,你该怎么办?也就是一个简单的乘法,把所有ab的对数乘上cd的对数。那加上a≠b≠c≠d,就是要剪去一些重复,对吧,那是哪些呢,其实也不多,四种情况(乘法原理):如图
爆裂吧世界(world/1S/64M) - 杨鸿飞 - 一个叫杨鸿飞的人的博客爆裂吧世界(world/1S/64M) - 杨鸿飞 - 一个叫杨鸿飞的人的博客
爆裂吧世界(world/1S/64M) - 杨鸿飞 - 一个叫杨鸿飞的人的博客爆裂吧世界(world/1S/64M) - 杨鸿飞 - 一个叫杨鸿飞的人的博客
        因为在之前的操作中已使(a<b)(c<d),因此a!=b,c!=d,所以减去这四种重复的情况即可。

  ======================================

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define rev(a) for (int i=1; i<=n/2; i++) swap(a[i],a[n-i+1]); //把数组反转
#define lb(x) x & -x //lowbit

using namespace std;

const int MLn=50010;

struct Tlsh { int x,p; }t[MLn]; //lsh离散化(排序实现)

bool cmp(Tlsh i,Tlsh j) { return i.x<j.x; }

int n,a[MLn];

int bi[MLn],bigl[MLn],bigr[MLn],smal[MLn],smar[MLn];

//bi(bit)、bigl(big,left)“左边(前面)有多少个比我大”、后面同理
int Sum(int p) //求1~p的和
{
int sum=0;
for ( ; p>0; p-=lb(p)) sum+=bi[p];
return sum;
}

int Add(int p) (第p位+1)
{ for ( ; p<=n; p+=lb(p)) bi[p]++; }

int main()
{
freopen("world.in","r",stdin);
freopen("world.out","w",stdout);

scanf("%d",&n);
/*=========离散化==========*/
for (int i=1; i<=n; i++)
{ scanf("%d",&t[i].x); t[i].p=i; }

sort(t+1,t+n+1,cmp);

int nowr=1;

for (int i=1; i<=n; i++)
{
if (i==1 || t[i].x==t[i-1].x) nowr--;
a[t[i].p]=++nowr;
}
/*=========================*/
for (int i=1; i<=n; i++) //前往后
{
smal[i]=Sum(a[i]-1);
bigl[i]=Sum(n)-Sum(a[i]);
Add(a[i]);
}
/*=========================*/
memset(bi,0,sizeof bi);

rev(a); //倒过来就是从后往前233

for (int i=1; i<=n; i++)
{
smar[i]=Sum(a[i]-1);
bigr[i]=Sum(n)-Sum(a[i]);
Add(a[i]);
}

rev(smar); rev(bigr); //倒回来就正常了233
/*=========================*/
//for (int i=1; i<=n; i++) cout<<smal[i]<<" "; cout<<endl;
//for (int i=1; i<=n; i++) cout<<smar[i]<<" "; cout<<endl;
//for (int i=1; i<=n; i++) cout<<bigl[i]<<" "; cout<<endl;
//for (int i=1; i<=n; i++) cout<<bigr[i]<<" "; cout<<endl;
/*=========================*/
long long sumab=0,sumcd=0,c=0;

for (int i=1; i<=n; i++) //每个的数对个数都加就是总和了
{
sumab+=smal[i]; //ab对
sumcd+=bigl[i]; //cd对
c+=bigr[i]*smar[i]+bigr[i]*bigl[i]
+smal[i]*smar[i]+bigl[i]*smal[i]; //交集
}

long long ans=sumab*sumcd-c;

cout<<ans;

return 0;
}



 

 

  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018