暑假的时候就听zhx讲过这题，不过好像当时讲复杂了。
很容易知道答案就是每次减去被出列的人里面没有出过列的人在原序列里右边的比她矮的人的个数。
所以每个人只会被算一次，均摊下来是O(n)的。然后就是怎么很快地找到这些人。我觉得用线段树比较方便，时间可以做到log。不知道是不是能用并查集。
好写好调。
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <memory.h>
#include <algorithm>
using namespace std;
#define readInt(_s_) {\
int _d_;\
while (!isdigit(_d_ = getchar()));\
_s_ = 0;\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
typedef long long qw;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
struct seg {
int l, r, v, p;
seg *ls, *rs;
};
const int maxn = 500009;
const int inf = 0x3f3f3f3f;
int n, m, h, a[maxn], s[maxn], *r[maxn], t[maxn];
qw ans;
seg *rt, *sp;
inline bool cmpP(const int* a, const int* b) {
return *a < *b;
}
int btQry(int* t, int p) {
int s = 0;
while (p)
s += t[p], p -= (p & -p);
return s;
}
void btChg(int* t, int p, int v) {
while (p < maxn)
t[p] += v, p += (p & -p);
}
#define mid(p) ((p->l+p->r)>>1)
seg* sgtBuild(int l, int r) {
seg* p = sp ++;
p-> l = l;
p-> r = r;
p-> v = inf;
if (l + 1 < r) {
p-> ls = sgtBuild(l, mid(p));
p-> rs = sgtBuild(mid(p), r);
}
else
p-> p = l;
return p;
}
void sgtChg(seg* p, int p0, int v0) {
if (p-> l + 1 == p-> r)
p-> v = v0;
else {
if (p0 < mid(p))
sgtChg(p-> ls, p0, v0);
else
sgtChg(p-> rs, p0, v0);
if (p-> rs-> v <= p-> ls-> v) {
p-> v = p-> rs-> v;
p-> p = p-> rs-> p;
}
else {
p-> v = p-> ls-> v;
p-> p = p-> ls-> p;
}
}
}
int sgtLower(seg* p, int l, int v) {
if (l == p-> l)
return (p-> v <= v) ? p-> p : inf;
else if (l >= mid(p))
return sgtLower(p-> rs, l, v);
else {
int x = sgtLower(p-> ls, l, v);
if (x < inf)
return x;
else
return (p-> rs-> v <= v) ? p-> rs-> p : inf;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
sp = new seg[maxn * 3];
readInt(n);
readInt(m);
rt = sgtBuild(1, n + 1);
for (int i = 1; i <= n; ++ i) {
readInt(a[i]);
r[i - 1] = a + i;
}
sort(r, r + n, cmpP);
for (int i = 0, l = *r[0] - 1, v = 0; i < n; ++ i)
if (*r[i] == l)
*r[i] = v;
else
l = *r[i], *r[i] = ++ v;
ans = 0;
for (int i = n; i; -- i) {
sgtChg(rt, i, a[i]);
s[i] = btQry(t, a[i] - 1);
ans += s[i];
btChg(t, a[i], 1);
}
printf(lld "\n", ans);
while (m --) {
int l, p;
readInt(l);
int h = a[l];
if (h < inf)
while ((p = sgtLower(rt, l, h)) < inf) {
ans -= s[p];
a[p] = inf;
sgtChg(rt, p, a[p]);
}
printf(lld "\n", ans);
}
}
Historical Comments
Unknown friend at 2014-11-14T19:14:19
OTL
Unknown friend at 2014-11-14T21:09:07
居然有人回复，好感动～
Unknown friend at 2014-11-14T22:33:39
专门注册了才好评论……不然你不知道我看过
Unknown friend at 2014-11-15T08:47:35
tan…