[HG]腿部挂件题解

前言

暴力跑的比正解快。

以下暴力(循环展开+fread读入输出优化)

#include<cstdio>

#pragma GCC optimize(3, "Ofast")

int a[200010];

namespace fast_IO{

    const int IN_LEN = 10000000, OUT_LEN = 10000000;

    char ibuf[IN_LEN], obuf[OUT_LEN], *ih = ibuf + IN_LEN, *oh = obuf, *lastin = ibuf + IN_LEN, *lastout = obuf + OUT_LEN - 1;

    inline char getchar_(){return (ih == lastin) && (lastin = (ih = ibuf) + fread(ibuf, 1, IN_LEN, stdin), ih == lastin) ? EOF : *ih++;}

    inline void putchar_(const char x){if(oh == lastout) fwrite(obuf, 1, oh - obuf, stdout), oh = obuf; *oh ++= x;}

    inline void flush(){fwrite(obuf, 1, oh - obuf, stdout);}

    inline int read(){

        int x = 0; char ch = ' ';

        while (ch < '0' || ch > '9') ch = getchar_();

        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar_(); return x;

    }

    inline void write(int x){

        if (x < 0) putchar_('-'), x = -x;

        if (x > 9) write(x / 10);

        putchar_(x % 10 + 48);

    }

}

using namespace fast_IO;

#define max(a,b) (a>(b)?a:(b))

int main(){

    const int n = read(); int q = read();

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

		a[i] = read();

	while (q--){

		const int x = read(), l = read(), rr = read();

		register int ans = 0;

		const int lft = ((rr - l) >> 2 << 2) + l;

		for (register int j = l; j <= lft - 4; j += 4){

			(ans < (x ^ a[j + 1])) && (ans = x ^ a[j + 1]);

			(ans < (x ^ a[j + 2])) && (ans = x ^ a[j + 2]);

			(ans < (x ^ a[j + 3])) && (ans = x ^ a[j + 3]);

			(ans < (x ^ a[j + 4])) && (ans = x ^ a[j + 4]);

		}

		for (register int j = lft; j <= rr; ++j)

			ans = max(ans, x ^ a[j + 1]);

		write(ans), putchar_('\n');

	}

	flush(); return 0;

}

题目

给定一个长度为 \(n(1 \leq n \leq 2 \times 10^5)\) 的数列，

给定 \(q(1 \leq q \leq 2 \times 10^5)\) 个询问，

每个询问给定三个整数 \(x, l, r\) 。

在区间 \([l,r]\) 中选定一个数，使它与 \(x\) 的异或值最大。

查询

题解

如果是查询区间是一个固定区间，很容易想到，使用trie树。

那么如果查询不是固定区间，那么显然珂以使用可持久化trie树切掉此题，

预计时间复杂度\(\Theta(n\ logn)\)

但是博主才学疏浅，不会这个算法。

就这么结束了吗？

并没有，显然我们可以用类线段树结构维护trie树，复杂度\(\Theta(n\ log^2n)\)

考场上常数过大一不小心 TLE了

后来一边query一边建树，就AC了。

代码

#pragma GCC optimize(3, "Ofast")

#include <cstdio>

namespace fast_IO{

    const int IN_LEN = 10000000, OUT_LEN = 10000000;

    char ibuf[IN_LEN], obuf[OUT_LEN], *ih = ibuf + IN_LEN, *oh = obuf, *lastin = ibuf + IN_LEN, *lastout = obuf + OUT_LEN - 1;

    inline char getchar_(){return (ih == lastin) && (lastin = (ih = ibuf) + fread(ibuf, 1, IN_LEN, stdin), ih == lastin) ? EOF : *ih++;}

    inline void putchar_(const char x){if(oh == lastout) fwrite(obuf, 1, oh - obuf, stdout), oh = obuf; *oh ++= x;}

    inline void flush(){fwrite(obuf, 1, oh - obuf, stdout);}

    int read(){

        int x = 0; char ch = ' ';

        while (ch < '0' || ch > '9') ch = getchar_();

        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar_(); return x;

    }

    void write(int x){

        if (x < 0) putchar_('-'), x = -x;

        if (x > 9) write(x / 10);

        putchar_(x % 10 + '0');

    }

}

using namespace fast_IO;

struct Trie{

    int c[2];

} trie[57108864];

int cnt = 0;

void insert(int x, int rt){

    for (register int i = 1 << 29; i; i >>= 1){

        bool to = x & i;

        if (trie[rt].c[to] == -1){

            trie[rt].c[to] = ++cnt;

            trie[cnt].c[0] = trie[cnt].c[1] = -1;

        }

        rt = trie[rt].c[to];

    }

}

int query(int x, int rt){

    int res = 0;

    for (register int i = 1 << 29; i; i >>= 1){

        bool to = (x ^ i) & i;

        if (~trie[rt].c[to]){

            res += i;

            rt = trie[rt].c[to];

        }

        else rt = trie[rt].c[to ^ 1];

    }

    return res;

}

int a[200005];

struct Seg{

    int root;

    int lc, rc;

} seg[800005];

inline int max(int a, int b){

    return ((a > b) ? a : b);

}

int querySeg(int pos, int l, int r, int x, int y, int v){

    if (x <= l && r <= y){

        if (!seg[pos].root){

            seg[pos].root = ++cnt;

            trie[cnt].c[0] = trie[cnt].c[1] = -1;

            for (register int i = l; i <= r; ++i)

                insert(a[i], seg[pos].root);

        }

        return query(v, seg[pos].root);

    }

    int mid = l + r >> 1, res = 0;

    if (x <= mid)

        res = querySeg(pos << 1, l, mid, x, y, v);

    if (y > mid)

        res = max(res, querySeg(pos << 1 | 1, mid + 1, r, x, y, v));

    return res;

}

int main(){

    int n = read(), q = read();

    trie[0].c[0] = trie[0].c[1] = -1;

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

        a[i] = read();

    while (q--){

        int x = read(), l = read() + 1, r = read() + 1;

        write(querySeg(1, 1, n, l, r, x)), putchar_('\n');

    }

    flush(); return 0;

}

巴特西

[HG]腿部挂件题解

前言

题目

题解

代码

最新文章

热门文章

巴特西

[HG]腿部挂件 题解

前言

题目

题解

代码

最新文章

热门文章

[HG]腿部挂件题解