数据结构划一下水
Description
N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.
Input
第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000
Output
最小的动作次数
题目大意
有一个非负的数列，可以±1修改高度，求最小代价使得连续k个高度相同
题目分析
对于一个区间的答案，就相当于把所有数都放在数轴上，再求一个数使得它到所有数的总和最小。那么最优就等于是求一个区间的中位数。
于是问题相当于一个支持 求中位数；求比中位数小/大的数个数；求比中位数小/大的数总和 的数据结构。这个问题可以用主席树在$logn$内完成。
注意 printf(calc(),a,b) ，如果在calc()中改变了a,b，输出的a,b将会是改变之前的值。
#include<bits/stdc++.h>
typedef long long ll;
const int maxn = ;
const int maxNode = ; struct node
{
int val,l,r;
ll sum;
}a[maxNode];
ll ans,lsum,rsum,lcnt,rcnt;
int n,k;
int rt[maxn],w[maxn],cnt[maxn],tot; int read()
{
char ch = getchar();
int num = , fl = ;
for (; !isdigit(ch); ch=getchar())
if (ch=='-') fl = -;
for (; isdigit(ch); ch=getchar())
num = (num<<)+(num<<)+ch-;
return num*fl;
}
void build(int &rt, int l, int r)
{
rt = ++tot;
if (l==r) return;
int mid = (l+r)>>;
build(a[rt].l, l, mid);
build(a[rt].r, mid+, r);
}
void update(int pre, int &rt, int l, int r, int c)
{
rt = ++tot, a[rt] = a[pre], ++a[rt].val, a[rt].sum += cnt[c];
if (l==r) return;
int mid = (l+r)>>;
if (c <= mid) update(a[pre].l, a[rt].l, l, mid, c);
else update(a[pre].r, a[rt].r, mid+, r, c);
}
int query(int pre, int rt, int l, int r, int k)
{
if (l==r) return l;
int val = a[a[rt].l].val-a[a[pre].l].val, mid = (l+r)>>;
if (val >= k){
lcnt -= a[a[rt].r].val-a[a[pre].r].val;
lsum -= a[a[rt].r].sum-a[a[pre].r].sum;
return query(a[pre].l, a[rt].l, l, mid, k);
}
rcnt -= a[a[rt].l].val-a[a[pre].l].val;
rsum -= a[a[rt].l].sum-a[a[pre].l].sum;
return query(a[pre].r, a[rt].r, mid+, r, k-val);
}
int main()
{
n = read(), k = read(), ans = 1ll<<;
for (int i=; i<=n; i++) w[i] = cnt[i] = read();
std::sort(cnt+, cnt+n+);
cnt[] = std::unique(cnt+, cnt+n+)-cnt-;
build(rt[], , cnt[]);
for (int i=; i<=n; i++)
{
w[i] = std::lower_bound(cnt+, cnt+cnt[]+, w[i])-cnt;
update(rt[i-], rt[i], , cnt[], w[i]);
}
for (int r=k; r<=n; r++)
{
int l = r-k;
lcnt = rcnt = a[rt[r]].val-a[rt[l]].val, lsum = rsum = a[rt[r]].sum-a[rt[l]].sum;
int tmp = cnt[query(rt[l], rt[r], , cnt[], (k+)>>)];
ans = std::min(ans, 1ll*tmp*(lcnt-rcnt)-lsum+rsum);
}
printf("%lld\n",ans);
return ;
}
END