laekov

BZOJ1112 [POI2008]砖块

水一发。


本来可以直接拿主席树找中位数的,但是因为main上只有32MB,所以只好写了个splay。感觉现在是爱上指针了。然后kth的时候少打个等号又wa又re好爽。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


typedef long long dint;


#ifdef WIN32

#define lld "%I64d"

#else

#define lld "%lld"

#endif

#define _l (long long int)


const int maxn = 100009;


#define nsz(p) ((p)?(p->sz):0)

#define sof(p) ((p)?(p->s):0)


struct splay_node {

   int v, sz;

   dint s;

   splay_node *ls, *rs, *pt;

   inline void init(int v0) {

   v = v0;

   sz = 1;

   s = v0;

   pt = ls = rs = 0;

   }

   inline void update() {

   s = v;

   sz = 1;

   if (ls) {

   s += ls-> s;

   sz += ls-> sz;

   }

   if (rs) {

   s += rs-> s;

   sz += rs-> sz;

   }

   }

};

struct splay_tree {

splay_node *cr, *sp, slst[maxn];

inline splay_tree() {

cr = 0;

sp = slst;

}

inline void rot(splay_node* q) {

splay_node *p = q-> pt;

if (p-> pt) {

if (p-> pt-> ls == p)

p-> pt-> ls = q;

else

p-> pt-> rs = q;

}

q-> pt = p-> pt;

p-> pt = q;

if (q == p-> ls) {

if (q-> rs)

q-> rs-> pt = p;

p-> ls = q-> rs;

q-> rs = p;

}

else {

if (q-> ls)

q-> ls-> pt = p;

p-> rs = q-> ls;

q-> ls = p;

}

p-> update();

q-> update();

}

void splay(splay_node* q) {

while (q-> pt) {

splay_node *p = q-> pt;

if (!p-> pt)

rot(q);

else if ((p == p-> pt-> ls) == (q == p-> ls))

rot(p), rot(q);

else

rot(q), rot(q);

}

cr = q;

}

splay_node* kth(splay_node* p, int k) {

while (p)

if (nsz(p-> ls) + 1 == k)

break;

else if (nsz(p-> ls) >= k)

p = p-> ls;

else

k -= nsz(p-> ls) + 1, p = p-> rs;

return p;

}

void ins(int v) {

splay_node *x = sp ++;

x-> init(v);

if (!cr)

cr = x;

else {

splay_node *p = cr;

while (p)

if (v < p-> v) {

if (!p-> ls) {

p-> ls = x;

x-> pt = p;

break;

}

else

p = p-> ls;

}

else {

if (!p-> rs) {

p-> rs = x;

x-> pt = p;

break;

}

else

p = p-> rs;

}

splay(x);

}

}

void ers(int v) {

splay_node *p = cr;

while (p)

if (p-> v == v)

break;

else if (v < p-> v)

p = p-> ls;

else

p = p-> rs;

splay(p);

if (!p-> rs) {

if (p-> ls)

p-> ls-> pt = 0;

cr = p-> ls;

}

else {

p-> rs-> pt = 0;

splay_node* q = kth(p-> rs, 1);

splay(q);

q-> ls = p-> ls;

if (p-> ls)

p-> ls-> pt = q;

q-> update();

cr = q;

}

}

dint ans(int k) {

splay_node *p = kth(cr, (k + 1) >> 1);

splay(p);

if (k & 1)

return sof(p-> rs) - sof(p-> ls);

else

return sof(p-> rs) - p-> v - sof(p-> ls);

}

inline int midv() {

return cr-> v;

}

};


int n, k, a[maxn];

int p0, v0;

dint ans;

splay_tree t;


int main() {

#ifndef ONLINE_JUDGE

//freopen("in.txt", "r", stdin);

#endif


scanf("%d%d", &n, &k);

for (int i = 0; i < n; ++ i)

scanf("%d", a + i);

for (int i = 0; i < k; ++ i)

t. ins(a[i]);

ans = t. ans(k);

p0 = 0;

v0 = t. midv();

for (int i = k; i < n; ++ i) {

t. ers(a[i - k]);

t. ins(a[i]);

dint vn = t. ans(k);

if (vn < ans) {

ans = vn;

p0 = i - k + 1;

v0 = t. midv();

}

}

printf(lld "\n", ans);

/*for (int i = p0; i < p0 + k; ++ i)

a[i] = v0;

for (int i = 0; i < n; ++ i)

printf("%d\n", a[i]);*/

}


评论

© laekov | Powered by LOFTER