题意
一个长度为 $n$ 的序列，对于每个前缀，求最多 $5$ 个互不相交的不下降子序列的元素和的最大值。
$n\leq 10^5,a_i\in[1,10^9]$
题解
$5$ 这个东西很有用，最终的复杂度很可能就是跟 $2^5$ 之类的相关。
把 $a_i$ 拆成 $a_i$ 个 $a_i$，那么答案转变成统计元素数量的最大值。
发现这个东西就是杨氏图表前 $5$ 层的长度之和。
杨表的插入过程如下：
1，若当前层没有元素比 $x$ 大，则把 $x$ 插在末尾。
2，否则用比 $x$ 大的最小的数 $y$ 代替 $x$，然后将 $y$ 插入下一层中。
那么用 $\mbox{map}$ 处理杨表，每次插入 $a_i$ 个 $a_i$，每层最多会使 $2$ 个数字拆开，因此时间复杂度 $O(2^5n\log n)$。
代码
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
| #include <cstdio>
#include <iostream>
#include <map>
#include <cstring>
using namespace std;
#define ll long long
#define S 5
inline int read()
{
int x=0; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x;
}
map<int,ll> a[S];
ll ans;
void add(int k,ll num,int u)
{
if(k>=S) return;
a[k][u]+=num; ans+=num;
for(map<int,ll>::iterator it;num;)
{
it=a[k].lower_bound(u+1);
if(it==a[k].end()) break;
ll d=min((*it).second,num);
num-=d; ans-=d;
add(k+1,d,(*it).first);
if((*it).second==d) a[k].erase(it); else a[k][(*it).first]-=d;
}
}
int main()
{
for(int T=read();T;T--,ans=0)
{
for(int i=0;i<S;i++) a[i].clear();
for(int i=read(),x,n=i;i;i--) x=read(),add(0,x,x),printf((i==1)?"%lld\n":"%lld ",ans);
}
return 0;
}
|