laekov

BZOJ3333 排队计划

暑假的时候就听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);

}

}


评论(4)

© laekov | Powered by LOFTER