JZOJ 4611. 【NOI2016模拟7.11】接水问题 （贪心+A*+可持久化线段树）
Description:
//gmoj.net/senior/#main/show/4611
题解：
先把A从大到小排序，最小的由排序不等式显然。
考虑类似第k短路的A*的做法。
定义状态为一个已经确定的前缀，它自己的代价显然，它的估价函数为把剩下的数字从小到大填的代价。
以自己代价+估价函数代价放入堆里一直扩展下一个即可，队列中会有\(n^2k\)个，加上求代价的复杂度，时间复杂度：\(O(n^3k)\)。
考虑优化扩展，注意假设要在下一位放数字，肯定是从小到大放，所以优化这个无用的扩展，可以减小一个n。
再考虑，一个状态一直放最小的到长度为n为止，这中间经过了很多状态，考虑把这些也优化了，
对状态重新定义为已知道了\(p[1..n]\)的值，前\(t-1\)个固定了，第\(t\)个可以变大，第\(t\)个现在是第\(w\)大，\(bz[t+1..n-1]\)表示\(p[x]\)能不能和\(p[x+1]\)交换。
发现状态只有\(O(k)\)个了，时间复杂度：\(O(nk)\)。
用可持久化线段树维护即可做到\(O(n~log~n+k~log~n)\)
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;
const ll inf = 1e18;
const int N = 2e5 + 5;
int n, k; ll a[N];
int cmpa(int x, int y) {
return x > y;
}
ll sum;
#define i0 t[i].l
#define i1 t[i].r
#define pii pair<ll, int>
#define fs first
#define se second
struct tree {
int l, r, p;
bool ban, lz;
pii x, y;
} t[N * 100]; int tt;
void upd(int i) {
t[i].x = min(t[i0].x, t[i1].x);
t[i].y = min(t[i0].y, t[i1].y);
}
void bt(int &i, int x, int y) {
i = ++ tt;
if(x == y) {
t[i].p = x;
t[i].x = t[i].y = pii(a[x] - a[x + 1], x);
return;
}
int m = x + y >> 1;
bt(i0, x, m); bt(i1, m + 1, y);
upd(i);
}
int pl, pr, px, py, pz;
void dgp(int &i, int x, int y) {
if(x == y) { px = t[i].p; return;}
int m = x + y >> 1;
if(pl <= m) dgp(i0, x, m); else dgp(i1, m + 1, y);
}
int fp(int &i, int x) {
pl = pr = x;
dgp(i, 1, n);
return px;
}
void kq(int &i) {
if(i) {
t[++ tt] = t[i]; i = tt;
t[i].ban = 0;
t[i].lz = 1;
t[i].x = t[i].y;
}
}
void down(int &i) {
if(t[i].lz) {
kq(i0), kq(i1);
t[i].lz = 0;
}
}
void dd(int &i, int x, int y) {
if(y < pl || x > pr) return;
t[++ tt] = t[i], i = tt;
if(x == y) {
t[i].y.fs += (ll) px * (a[x] - a[x + 1]);
if(t[i].ban) t[i].x = pii(inf, x); else
t[i].x = t[i].y;
if(py) t[i].p = pz;
return;
}
int m = x + y >> 1; down(i);
dd(i0, x, m); dd(i1, m + 1, y);
upd(i);
}
void xiu(int &i, int x, int y) {
int v = fp(i, x);
if(x > 1) {
py = 0;
pl = pr = x - 1, px = y - v;
dd(i, 1, n);
}
py = 1; pz = y;
pl = pr = x, px = v - y;
// pp("xiu %d %d %d %d\n", x, y, v, px);
dd(i, 1, n);
}
void du(int &i, int x, int y) {
if(y < pl || x > pr) return;
t[++ tt] = t[i], i = tt;
if(x == y) {
t[i].ban = 1;
t[i].x = pii(inf, x);
return;
}
int m = x + y >> 1; down(i);
du(i0, x, m); du(i1, m + 1, y);
upd(i);
}
void jz(int &i, int x) {
pl = pr = x;
du(i, 1, n);
}
void ddq(int &i, int x, int y) {
if(y < pl || x > pr) return;
if(x == y) {
px = t[i].ban; return;
}
int m = x + y >> 1; down(i);
ddq(i0, x, m); ddq(i1, m + 1, y);
}
int qry_ban(int &i, int x) {
pl = pr = x;
ddq(i, 1, n);
return px;
}
pii pu;
void ft(int &i, int x, int y) {
if(y < pl || x > pr) return;
if(x >= pl && y <= pr) {
pu = min(pu, t[i].x);
return;
}
int m = x + y >> 1; down(i);
ft(i0, x, m); ft(i1, m + 1, y);
}
pii qry(int &i, int t) {
pl = t + 1, pr = n - 1;
pu = pii(inf, 0);
ft(i, 1, n);
return pu;
}
int rt;
struct nod {
int g, t, w;
pii c;
ll s;
};
bool operator < (nod a, nod b) {
return a.s > b.s;
}
priority_queue<nod> q;
void build() {
bt(rt, 1, n);
nod b;
b.g = rt; b.t = 1; b.w = 2;
b.c = pii(a[1] - a[2], 1);
b.c = min(b.c, qry(b.g, b.t));
b.s = sum;
b.s += b.c.fs;
q.push(b);
}
void swap(nod &b, int x, int y) {
int v1 = fp(b.g, x), v2 = fp(b.g, y);
// pp(" swap %d %d %d %d\n", x, y, v1, v2);
// pp("%lld\n", qry(b.g, 1).fs);
xiu(b.g, x, v2); xiu(b.g, y, v1);
// pp("%lld\n", qry(b.g, 1).fs);
}
int mak(nod &b) {
if(b.w > n) {
b.t ++; b.w = b.t + 1;
if(b.t >= n) return 0;
}
b.c = pii(inf, 0);
if(!qry_ban(b.g, b.t)) {
b.c = pii((a[b.t] - a[b.w]) * (fp(b.g, b.w) - fp(b.g, b.t)), b.t);
}
b.c = min(b.c, qry(b.g, b.t));
if(b.c.fs == inf) return 0;
b.s += b.c.fs;
return 1;
}
void work(nod b) {
int x = b.c.se, y = x == b.t ? b.w : x + 1;
if(x == b.t) {
nod c = b;
swap(c, x, y);
c.w ++; kq(c.g);
if(mak(c)) q.push(c);
b.s -= b.c.fs;
jz(b.g, x);
if(mak(b)) q.push(b);
} else {
nod c = b;
swap(c, x, y);
c.t = x, c.w = x + 2;
kq(c.g);
if(mak(c)) q.push(c);
b.s -= b.c.fs;
jz(b.g, x);
if(mak(b)) q.push(b);
}
}
int main() {
freopen("water.in", "r", stdin);
freopen("water.out", "w", stdout);
scanf("%d %d", &n, &k);
fo(i, 1, n) scanf("%lld", &a[i]);
sort(a + 1, a + n + 1, cmpa);
fo(i, 1, n) sum += a[i] * i;
build();
pp("%lld\n", sum);
fo(ii, 1, k - 1) {
nod b = q.top(); q.pop();
pp("%lld\n", b.s);
work(b);
// pp("fs = %lld\n", qry(b.g, b.t).fs);
// pp("%d %d %lld %d\n", b.t, b.w, b.c.fs, b.c.se);
// fo(i, 1, n) {
// int x = b.c.se, y = x == b.t ? b.w : x + 1;
// int t = i == x ? y : (i == y ? x : i);
// pp("%d ", fp(b.g, t));
// }
// hh;
}
}
