[2016模拟] 序列 sequence[二分+树状数组+dp]

[Description]

有一天 OJ 给 Jiangzh 了一个序列,但是 OJ 给的任务没有省选 operation 那么变态, OJ 只需
要 Jiangzh 做两件事:
① 求出这个序列的最长上升子序列长度
② 这个序列中满足 i < j < k Ai < Aj > Ak 关系的序列个数

[Input]

第一行一个整数 N,表示这个序列有 N 个整数
第二行 N 个整数 Ai

[Output]

两行,每行一个整数分别为两个问题的答案

[Sample 1]

sequence.in sequence.out
5 1
2 3 4 5 5 0
样例解释:最长上升子序列长度为 5,满足条件②的序列有 0 个

[Sample 2]

sequence.in sequence.out
5 1
5 3 4 8 4 2
样例解释:最长上升子序列长度为 4,满足条件②的序列有 2 个 —— (1,5,3)和 (1,5,4)

[Hit]

对于 30%的数据: N<=200
对于 50%的数据: N<=5000
对于 100%的数据: N<=100000, 0<=Ai<=200000

题解

第一问用二分优化就行,也可以用lower_bound。因为我不太会用于是就用的二分。
第二问,设s[i]为前面比它小的数的个数*后面比它小的数的个数,结果就是s[2]+s[3]+……+s[n-1];
树状数组线段树之类的都可以?我用的树状数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/*
ID: ylx14274
PROG: sequence
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
#define INF 2^63-1
using namespace std;
long long a[1000100];
long long c[1000100];
long long f[1000100];
long long s[1000100];
long long n,i,j;
long long sum,len;
void dp(int x)//二分,其实可以用stl中的lower_bound,然而我不太会用
{
int l,r,mid;
l=0;r=len+1;mid=(l+r)/2;
while (l!=r)
{
if (f[mid]>=a[x])
{
r=mid;
mid=(l+r)/2;
}
if (f[mid]<a[x])
{
l=mid+1;
mid=(l+r)/2;
}
}
if (l==len+1) len++;
f[l]=a[x];
}
void xiugai(long long k,int num)//修改k点num个数
{
while(k<=1000000)
{
c[k]+=num;
k+=(-k)&k;//向上修改
}
}

long long qiuhe(long long k) //向下求和
{
long long sum=0;
while(k)//k为真,即不为0;
{
sum+=c[k];//求和
k-=k&(-k);
}//k为真,即不为0;
return sum;
}

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

scanf("%d",&n);
for (i=1;i<=n;i++)///读入
{
scanf("%d",&a[i]);
a[i]++;//0的情况
}
//第一问
f[1]=a[1];//初始化
len=1;
for (i=2;i<=n;i++) dp(i);//求最长上升子序列
printf("%I64d\n",len);
//第二问
for (i=1;i<=n;i++)
{
s[i]+=qiuhe(a[i]-1);//统计
xiugai(a[i],1); //修改
}
for (i=1;i<=1000000;i++) c[i]=0;//清空c数组 for (i=n;i>=1;i--)
{
s[i]*=qiuhe(a[i]-1);
xiugai(a[i],1);
}
for (i=2;i<=n-1;i++) sum+=s[i];
printf("%I64d",sum);//输出
return 0;
}