武装捍卫 dp
20111019Yu
·
·
题解
事先声明，本题解为诡异做法，运用了大量 dp 以及数据结构优化。
题解
首先连通这个条件不好刻画，考虑他的冲要条件，手磨一下能发现即为
\nexists\space i\in[1,n),s.t.\space \max\limits_{x=1}^i p_x=i
然后不管贪心了，直接对着这个东西设 dp_{i,j} 表示考虑前 i 个数，在相对排名下满足上面式子的最小位置是 j 的最大价值。
考虑加入 i 时的转移，第一种是 i 对前面 j 个没有影响，即对于前面产生的逆序对数 \leq i-j-1
dp_{i,j}=dp_{i-1,j} (a_i\leq 0)
第二种是插入后的相对排名 \leq j，那么此时只有 i 符合上面式子条件，那么对于前面产生的逆序对数 \geq i-j。
dp_{i,i}=dp_{i-1,j}+a_i(i-j)(a_i\leq0)
注意到第二维变化时一定变成 i 所以删掉第二维，令 dp_i 表示前 i 个连通且前面不存在满足上面条件的最大价值。
令 s_i=\sum\limits_{x=1}^i a_x,si_i=\sum\limits_{x=1}^i a_xx，则有
dp_i=dp_j+si_{i-1}-si_j-(s_{i-1}-s_j)(j+1)+a_i(i-1)(a_i>0)
最后的构造是简单的，可以根据最优决策跳回去，中间的数对前面产生的逆序对个数已知。
好的，现在你学会暴力数据结构通过这道构造题了，赶快去应用吧。
### code
::::success[$\mathcal{O}(n\log V)$]
```cpp
#include <bits/stdc++.h>
#define int long long
const int M = 1e14;
using namespace std;
int t, n, a[200005], f[200005], g[200005], s[200005], si[200005], cnt, h[200005], p[200005];
struct line{
__int128 k, b;
} l[200005];
struct linetree{
int bel[200005], ls[200005], rs[200005], point, rt;
__int128 calc(int c, __int128 x){
return l[c].k * x + l[c].b;
}
bool cmp(int x, int a, int b){
return calc(a, x) > calc(b, x);
}
void update(int l, int r, int &rt, int c){
if(!rt) rt = ++point;
if(!bel[rt]){
bel[rt] = c;
return;
}
int mid = l + r >> 1;
if(cmp(mid, c, bel[rt])) swap(bel[rt], c);
if(l == r) return;
if(cmp(l, c, bel[rt])) update(l, mid, ls[rt], c);
if(cmp(r, c, bel[rt])) update(mid + 1, r, rs[rt], c);
}
pair<int, __int128> query(int l, int r, int rt, int x){
if(!rt) return {0, 0};
pair<int, __int128> ans = {bel[rt], calc(bel[rt], x)};
int mid = l + r >> 1;
if(mid >= x){
pair<int, __int128> val = query(l, mid, ls[rt], x);
if(!ans.first || val.second > ans.second) ans = val;
}
else{
pair<int, __int128> val = query(mid + 1, r, rs[rt], x);
if(!ans.first || val.second > ans.second) ans = val;
}
return ans;
}
} li;
struct segtree{
int s[800005];
void built(int l, int r, int rt){
s[rt] = r - l + 1;
if(l == r) return;
int mid = l + r >> 1;
built(l, mid, rt << 1);
built(mid + 1, r, rt << 1 | 1);
}
int query(int l, int r, int rt, int c){
s[rt]--;
if(l == r) return l;
int mid = l + r >> 1;
if(s[rt << 1 | 1] > c) return query(mid + 1, r, rt << 1 | 1, c);
return query(l, mid, rt << 1, c - s[rt << 1 | 1]);
}
} tr;
template<typename type>
inline void read(type &x){
x=0;bool flag(0);char ch=getchar();
while(!isdigit(ch)) flag=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
flag?x=-x:0;
}
template<typename type>
inline void write(type x){
x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
do Stack[++top]=x%10,x/=10; while(x);
while(top) putchar(Stack[top--]|48);
putchar(' ');
}
signed main(){
read(t);
while(t--){
read(n);
for( int i = 1; i <= n; i++ ) read(a[i]);
for( int i = 1; i <= n; i++ ){
s[i] = s[i - 1], si[i] = si[i - 1];
if(a[i] > 0) s[i] += a[i], si[i] += a[i] * i;
}
f[1] = 0;
for( int i = 2; i <= n; i++ ){
l[i - 1] = {-(i - 1), f[i - 1] - si[i - 1] + i * s[i - 1]};
li.update(-M, M, li.rt, i - 1);
if(a[i] > 0){
pair<int, __int128> val = li.query(-M, M, li.rt, s[i - 1]);
g[i] = val.first;
f[i] = val.second + si[i - 1] - s[i - 1] + a[i] * (i - 1);
}
else{
pair<int, __int128> val = li.query(-M, M, li.rt, s[i - 1] + a[i]);
g[i] = val.first;
f[i] = val.second + si[i - 1] - s[i - 1] + a[i] * i;
}
}
int pos = n;
while(pos > 1){
if(a[pos] > 0) h[pos] = pos - 1;
else h[pos] = pos - g[pos];
for( int i = pos - 1; i > g[pos]; i-- ){
if(a[i] > 0) h[i] = i - g[pos] - 1;
else h[i] = 0;
}
pos = g[pos];
}
tr.built(1, n, 1);
for( int i = n; i >= 1; i-- ) p[i] = tr.query(1, n, 1, h[i]);
write(f[n]), putchar('\n');
for( int i = 1; i <= n; i++ ) write(p[i]);
putchar('\n');
memset(li.bel, 0, sizeof(int) * (n + 2));
memset(li.rs, 0, sizeof(int) * (n + 2));
memset(li.ls, 0, sizeof(int) * (n + 2));
li.rt = li.point = 0;
}
return 0;
}
```
::::