HOJ2275 Number sequence
Number sequence
My Tags | tag=&type=or" style="margin:0px; padding:0px; color:rgb(27,87,177); text-decoration:none"> (Edit) |
---|
Source : id=SCU%20Programming%20Contest%202006%20Final" style="margin:0px; padding:0px; color:rgb(27,87,177); text-decoration:none">SCU Programming |
|||
Time limit : 1 sec | Memory limit : 64 M |
Submitted : 1632, Accepted : 440
Given a number sequence which has N element(s), please calculate the number of different collocation for three number Ai, Aj, Ak, which satisfy that Ai < Aj > Ak and i < j < k.
Input
The first line is an integer N (N <= 50000). The second line contains N integer(s): A1, A2, ..., An(0 <= Ai <= 32768).
Output
There is only one number, which is the the number of different collocation.
Sample Input
5
1 2 3 4 1
Sample Output
6
这题能够用树状数组做,开两个一维的树状数组分别记录当前点前面的比这点小的个数和后面比这点大的个数。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
#define maxn 50005
#define ll long long
int b1[maxn],b2[maxn],a[maxn];
int lowbit(int x){
return x&(-x);
}
void update1(int pos,int num)
{
while(pos<=maxn){
b1[pos]+=num;pos+=lowbit(pos);
}
}
int getsum1(int pos)
{
int num=0;
while(pos>0){
num+=b1[pos];pos-=lowbit(pos);
}
return num;
} void update2(int pos,int num)
{
while(pos<=maxn){
b2[pos]+=num;pos+=lowbit(pos);
}
}
int getsum2(int pos)
{
int num=0;
while(pos>0){
num+=b2[pos];pos-=lowbit(pos);
}
return num;
} int main()
{
int n,m,i,j;
ll num=0;
while(scanf("%d",&n)!=EOF)
{
memset(b1,0,sizeof(b1));
memset(b2,0,sizeof(b2));
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]++;
if(i==1){
update1(a[i],1);continue;
}
update2(a[i],1);
}
num=0;
for(i=2;i<=n-1;i++){
num+=getsum1(a[i]-1)*getsum2(a[i]-1);
update1(a[i],1);
update2(a[i],-1);
}
printf("%lld\n",num);
}
return 0;
}
最新文章
- mongoDB 使用手册
- img 在层内 居中显示
- LTIB常用命令3
- MySql数据库1【概念】
- 谈谈android 布局 的优化
- you can Solve a Geometry Problem too(hdoj1086)
- python导入模块的方法
- IOS基础开发二(iphone计算器)
- 利用StringBuffer向字符串特定的重复子字符串插入数据
- Linux内存布局
- AmpLab Tachyon and Shark update
- PL/SQL 三个小例子
- UITableViewBase&;nbsp;UI_09
- XML配置spring session jdbc实现session共享
- 往服务器部署thinkphp5代码时要注意 pathinfo的问题
- SSH总结
- MYSQL 常用函数大全
- HTTP中的Get与Post
- 克隆后没有IP
- SharePoint 2013 Step by Step—— 为终端用户提供故障恢复的解决方案 Part I
热门文章
- poj 3623 Best Cow Line, Gold
- Swift - 按钮(UIButton)的用法
- MySQL 关闭FOREIGN_KEY_CHECKS检查
- C#写的客户端连接 php的服务器端的小例子
- SilkTest Q&;A 3
- Android资源管理框架(Asset Manager)简介和学习计划
- codeforces 598B Queries on a String
- win7下怎样设置putty免用户名密码登陆
- Android 异步链式调用设计
- ACM-计算几何之Quoit Design——hdu1007 zoj2107