bzoj 1831

思路:随便猜一猜填的数字是不下降的,反证很好证明,然后就没了。。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
#define PLI pair<LL, int>
#define ull unsigned long long
using namespace std; const int N = 1e4 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ; int n, k, a[N];
struct Bit {
int a[];
void modify(int x, int val) {
for(int i = x; i <= ; i += i & -i)
a[i] += val;
}
int sum(int x) {
int ans = ;
for(int i = x; i; i -= i & -i)
ans += a[i];
return ans;
}
int query(int l, int r) {
if(l > r) return ;
return sum(r) - sum(l-);
}
} b1, b2; int main() {
scanf("%d%d", &n, &k);
for(int i = ; i <= n; i++)
scanf("%d", &a[i]);
for(int i = n; i >= ; i--)
if(~a[i]) b2.modify(a[i], ); LL ans = ;
for(int i = ; i <= n; i++) {
if(~a[i]) {
b2.modify(a[i], -);
b1.modify(a[i], );
ans += b1.query(a[i]+, );
} else {
int ret = inf;
for(int j = ; j <= ; j++) {
ret = min(ret, b1.query(j+, ) + b2.query(, j-));
}
ans += ret;
}
}
printf("%lld\n", ans);
return ;
} /*
*/
上一篇:ERwin入门


下一篇:css的一些小技巧!页面视觉差!