不强制在线的动态快速排序题解

算法一

按照题意模拟

维护一个数组，每次直接往数组后面依次添加\([l, r]\)

每次查询时，暴力地\(sort\)查询即可

复杂度\(O(10^9 * q)\)，期望得分\(0\)分

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n, opt;

int q[.........], to;

int main() {

	cin >> n;

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

		cin >> opt;

		if(opt == 1) {

			int l, r;

			cin >> l >> r;

			for(int j = l; j <= r; j ++) q[++ to] = j;

			sort(q + 1, q + to + 1);

			to = unique(q + 1, q + to + 1) - q - 1;

		}

		else {

			long long ans = 0;

			for(int i = 2; i <= to; i ++)

				ans ^= (1ll * q[i] * q[i] - 1ll * q[i - 1] * q[i - 1]);

			printf("%lld\n", ans);

		}

	}

	return 0;

}

算法二

\(\bigoplus \limits_{i = 2}^n (a_i^2 - a_{i - 1}^2) = \bigoplus \limits_{i = 2}^n (a_i + a_{i - 1})(a_i - a_{i - 1})\)

当\(a_i = a_{i - 1}\)时，可以发现\((a_i, a_{i - 1})\)是对\(V(S)\)没有贡献的，也就是说，重复的数等价于一个

那么，我们不用数组了

我们用自带去重的\(set\)来模拟插入

查询时暴力即可

期望得分\(0\)分

算法三

插入单点看起来很可做

用一个\(set\)来维护

每次插入时，对前驱后继来讨论即可

插入复杂度\(O(\log n)\)，询问复杂度\(O(1)\)

期望得分\(0 \sim 20\)分

算法四

插入的是一段值域区间

因此不妨以区间为单位来考虑

区间\([l, r]\)形成的贡献为\(\bigoplus \limits_{i = 2}^n (a_i - a_{i - 1})* (a_i + a_{i - 1})\)，由于\(a_i = a_{i - 1} + 1\)

因此，区间\([l, r]\)形成的贡献为\(\bigoplus \limits_{i = 1}^{n - 1} 2 a_i + 1 = \bigoplus \limits_{i = l}^{r -1} 2i + 1 = \bigoplus \limits_{i = 1}^{r - 1} 2i + 1 \oplus \bigoplus \limits_{i = 1}^{l - 1} 2i + 1\)

考虑怎么求\(\bigoplus \limits_{i = 1}^n 2i + 1\)

这个问题等价于问\([1, 2n + 1]\)中的所有奇数的异或和

按位分解之后，只要支持区间\([1, n]\)中有多少个\(2^i\)即可

再来个大力数位\(dp\)

复杂度\(O(\log^2 n)\)
询问区间\([1, n]\)中有多少个\(2^i\)可以\(O(1)\)回答

对于每一段\(2^{i + 1}\)而言，前\(2^i\)的第\(i\)位为\(0\)，后\(2^i\)的第\(i\)位为\(1\)

复杂度\(O(\log n)\)
打表，可以发现\(O(1)\)的规律

设\(n = 4m + k\)

当\(k = \{0, 1, 2, 3\}\)时，前缀异或和依次为\(2n, 3, 2n + 2, 1\)

可以考虑用归纳法证明

复杂度\(O(1)\)

在下文中，我们取\(f(n)\)表示计算异或前缀和的复杂度

可以考虑每次暴力的维护区间的并（用\(sort\)来维护...）

期望得分\(30 \sim 40\)分

算法五

考虑用\(set\)来维护区间

像珂朵莉树那样去维护大概就行了

复杂度\(O(n \log n + n * f(n))\)

期望得分\(50 \sim 100\)分

算法六

考虑用值域线段树来维护

在线段树上的每个节点维护\(min, max, sum\)即可更新

需要动态开点

每次插入对应着给一些区间打标记

每次查询可以直接取\(sum[root]\)即可

注意一个区间被打了标记之后，它的所有子区间都不需要打标记了

复杂度\(O(n f(n) \log 10^9)\)

期望得分\(50 \sim 100\)分

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ll long long

#define ri register int

#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)

#define drep(io, ed, st) for(ri io = ed; io >= st; io --)

#define gc getchar

inline int read() {

    int p = 0, w = 1; char c = gc();

    while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }

    while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();

    return p * w;

}

const int sid = 1e7 + 5;

ll sum[sid];

bool tag[sid];

int m, rt, id;

int mi[sid], mx[sid], ls[sid], rs[sid];

inline void upd(int o) {

    int lc = ls[o], rc = rs[o];

    mi[o] = mi[lc] ? mi[lc] : mi[rc];

    mx[o] = mx[rc] ? mx[rc] : mx[lc];

    sum[o] = sum[lc] ^ sum[rc];

    if(mx[lc] && mi[rc]) sum[o] ^= 1ll * (mi[rc] + mx[lc]) * (mi[rc] - mx[lc]);

    if(tag[lc] && tag[rc]) tag[o] = 1;

}

inline int pre(int x) {

    int o = x & 3;

    if(o == 0) return (x << 1);

    if(o == 1) return 3;

    if(o == 2) return (x << 1) + 2;

    if(o == 3) return 1;

}

void mdf(int &o, int l, int r, int ml, int mr) {

    if(ml > r || mr < l || tag[o]) return;

    if(!o) o = ++ id;

    if(ml <= l && mr >= r) {

        mi[o] = l; mx[o] = r;

        sum[o] = pre(r - 1) ^ pre(l - 1);

        tag[o] = 1;

        return;

    }

    int mid = (l + r) >> 1;

    mdf(ls[o], l, mid, ml, mr);

    mdf(rs[o], mid + 1, r, ml, mr);

    upd(o);

}

int main() {

    m = read();

    rep(i, 1, m) {

        int opt = read();

        if(opt == 1) {

            int l = read(), r = read();

            mdf(rt, 1, 1e9, l, r);

        }

        else if(opt == 2)

            printf("%lld\n", sum[1]);

    }

    return 0;

}

这是一道我也不知道区分了什么反正挺水的题

好像忘了给不会算区间异或和的分了

不管了，反正大家都能A嘛

一些诡异的东西

\(\oplus 2i + 1\)，其实等价于\((\oplus i) * 2 + (i \;\&\;1)\)

然后只要考虑\((\oplus i)\)即可

这个就好考虑多了

巴特西

luoguP5105 不强制在线的动态快速排序 [官方？]题解线段树 / set

不强制在线的动态快速排序题解

算法一

算法二

算法三

算法四

算法五

算法六

最新文章

热门文章

巴特西

luoguP5105 不强制在线的动态快速排序 [官方？]题解 线段树 / set

不强制在线的动态快速排序 题解

算法一

算法二

算法三

算法四

算法五

算法六

最新文章

热门文章

luoguP5105 不强制在线的动态快速排序 [官方？]题解线段树 / set

不强制在线的动态快速排序题解