「NOIP2017」列队

传送门

Luogu

解题思路

一眼平衡树，应该没问题吧？

但我们一定要反应过来，单点的维护是非常之困难的，因为这是一个网格图而不仅仅是一条序列。

我们要考虑把修改操作全都放在序列上进行。

其实题面里是给了提示的，找一找在哪里。

于是我们可以考虑维护一些区间：

对于每一行，将前 \(m-1\) 个数的区间作为一个节点；将最后一列的 \(n\) 个数的的区间作为一个节点。

但是我们会遇到这样一个问题：当前的区间需要被切开，也就是要把一个节点分裂成两个节点。

其实这个和普通的序列操作是没什么区别的，具体实现看看代码就很显然了。

细节注意事项

节点空间开两倍
开long long

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < class T > inline void read(T& s) {

    s = 0; int f = 0; char c = getchar();

    while (!isdigit(c)) f |= c == '-', c = getchar();

    while (isdigit(c)) s = s * 10 + c - 48, c = getchar();

    s = f ? -s : s;

}

typedef long long LL;

const int _ = 3000002 * 2;

int n, m, q, rt[_];

int tot, siz[_], pri[_], lc[_], rc[_];

LL r[_], l[_];

inline int newnode(LL L, LL R)

{ return siz[++tot] = R - L + 1, r[tot] = R, l[tot] = L, pri[tot] = rand(), tot; }

inline void pushup(int p) { siz[p] = siz[lc[p]] + siz[rc[p]] + r[p] - l[p] + 1; }

inline int merge(int x, int y) {

    if (!x || !y) return x + y;

    if (pri[x] > pri[y])

		return rc[x] = merge(rc[x], y), pushup(x), x;

    else

		return lc[y] = merge(x, lc[y]), pushup(y), y;

}

inline void _split(int p, int k) {

    if (k >= r[p] - l[p] + 1) return ;

    LL pos = l[p] + k - 1;

    int New = newnode(pos + 1, r[p]);

    return r[p] = pos, rc[p] = merge(New, rc[p]), pushup(p);

}

inline void split(int p, int k, int& x, int& y) {

    if (!p) { x = y = 0; return ; }

    if (siz[lc[p]] >= k)

		return y = p, split(lc[p], k, x, lc[y]), pushup(p);

    else { _split(p, k - siz[lc[p]]);

		return x = p, split(rc[p], k - siz[lc[p]] - (r[p] - l[p] + 1), rc[x], y), pushup(p);

    }

}

int main() {

#ifndef ONLINE_JUDGE

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

    freopen("out.out", "w", stdout);

#endif

    srand(time(0));

    read(n), read(m), read(q);

    for (rg int i = 1; i <= n; ++i)

		rt[i] = newnode((LL) (i - 1) * m + 1, (LL) i * m - 1);

    for (rg int i = 1; i <= n; ++i)

		rt[n + 1] = merge(rt[n + 1], newnode((LL) i * m, (LL) i * m));

    for (rg int x, y; q--; ) {

		read(x), read(y);

		if (y == m) {

			int a, b, c;

			split(rt[n + 1], x, a, c);

			split(a, x - 1, a, b);

			printf("%lld\n", l[b]);

			rt[n + 1] = merge(a, merge(c, b));

		} else {

			int a, b, c, aa, bb, cc;

			split(rt[x], y, a, c);

			split(a, y - 1, a, b);

			printf("%lld\n", l[b]);

			split(rt[n + 1], x, aa, cc);

			split(aa, x - 1, aa, bb);

			rt[x] = merge(a, merge(c, bb));

			rt[n + 1] = merge(aa, merge(cc, b));

		}

    }

    return 0;

}

完结撒花 \(qwq\)

巴特西

「NOIP2017」列队

解题思路

细节注意事项

参考代码

最新文章

热门文章