三元上升子序列

树状数组求法

在做这道前,你需要了解树状数组求逆序对。

首先看这一道题,三元!在二元时,不是跟逆序对一样吗? 求逆序对可以用树状数组或归并,那么在三元时,是否也可以呢? 考虑 ,把它拆成两个二元 ,两个二元组都与有关,那么就考虑中间j,假设第一个不等式有 p 个 a 满足$ < a_ja >a_j$,那么以下标为j的答案就为p*q。那不就是算一下每个下标前面比它小的值,后面比它大的值。

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
#include<bits/stdc++.h>
using namespace std;
int n,tree[33333];
struct dd{
int v,pos;
}a[33333];
long long ans=0;
int ans1[33333];
#define lowbit(x) ((x)&(-x))
inline bool cmp(dd x, dd y){
return x.v==y.v?x.pos>y.pos:x.v<y.v;
//若相同,将下标值大的放在前面。
}
void update(int t,int x){
while(t<=n){
tree[t]+=x;
t+=lowbit(t);
}
}
int sum(int t){
int tot=0;
while(t){
tot+=tree[t];
t-=lowbit(t);
}
return tot;
}
inline int read(){
int x=0;
char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9'){
x=x*10+(ch^48);
ch=getchar();
}
return x;
}
int main(){
n=read();
for(int i=1;i<=n;++i){
a[i].v=read();
a[i].pos=i;
}
sort(a+1,a+1+n,cmp);//从小到大排序
for(int i=1;i<=n;++i){
ans1[i]=sum(a[i].pos-1);
//下标大的先计算,不会影响下标比它小相同数的统计
update(a[i].pos,1);
}
memset(tree,0,sizeof(tree));
for(int i=n;i>=1;--i){
//倒序枚举,此时是下标小先计算,不会影响下标比它大相同数的统计
ans+=(long long)ans1[i]*(sum(n-a[i].pos));
update(n-a[i].pos+1,1);
}
printf("%lld",ans);
}

此题可以拓展到k元上升序列,推荐个大佬博客

发布于

2019-10-28

更新于

2021-09-26

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...