[ASDFZ]异或

给定一长度为 latex n 的序列 latex a_ilatex q 次询问 latex a[l,r] 中选若干个数(可以不选)与 latex d 异或的最大值。

线性基的基础用法,区间直接用线段树维护线性基,时间复杂度 latex O(nlog^3n)

但是这题 latex n\le 10^6

考虑如果一个端点 latex r 固定,而 latex l 变化,那么只需要从 latex r 往左依次插入线性基,顺带记录线性基每一位插入的时间就可以解决。

如果右端点也变化,可以发现并不一定需要暴力重构线性基。

假设现在已经维护好了一个 latex [1,r-1] 的从右往左依次插入的线性基,需要插入 latex r,而且要在当前线性基所有元素之前插入。

实际上 latex [1,r-1] 的线性基和 latex [1,r] 区别仅仅是有若干位上移填补 latex r 的位置,模拟一下很好理解。

那么插入 latex a_r 时只需要把这几位依次下移即可。

时间复杂度:latex nlog(\max(a_i))

实现上线性基可以记录在原数组的编号,修改直接在原数组操作。

此题输入输出量极大,普通的快读读入时就会TLE。因此出题人提供了一个fread,fwrite模板。

#include <bits/stdc++.h>
using namespace std;
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	// input a integer
	template <class I>
	inline void gi (I &x) {
		for (c = gc(); c < '0' || c > '9'; c = gc());
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
	}
	// print a integer
	template <class I>
	inline void print (I &x) {
		if (!x) putc ('0');
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
}
using io :: gi;
using io :: putc;
using io :: print;

const int Max = 1000033;
int n, m, cnt, a[Max], b[40], fir[Max], ans[Max];
struct List {
    int l, d, id, nxt;
    List() {}
    List(int a, int b, int c, int e) {
        l = a, d = b, id = c, nxt = e;
    }
} q[Max];
void add(int l, int r, int id, int d) {
    q[++cnt] = List(l, d, id, fir[r]);
    fir[r] = cnt;
}

int main() {
    gi(n);
    for (int i = 1; i <= n; i++)
        gi(a[i]);
    gi(m);
    for (int i = 1; i <= m; i++) {
        int l, r, d;
        gi(l), gi(r), gi(d);
        add(l, r, i, d);
    }
    for (int i = 1; i <= n; i++) {
        int id = i;
        for (int j = 30; j >= 0; j--) {
            if (a[id] & (1 << j)) {
                if (!b[j]) { b[j] = id; break; }
                else {
                    if (b[j] < id) swap(id, b[j]);
                    a[id] ^= a[b[j]];
                }
            }
        }
        for (int j = fir[i]; j; j = q[j].nxt) {
            for (int k = 30; k >= 0; k--) {
                if (q[j].l <= b[k]) {
                    if ((q[j].d ^ a[b[k]]) > q[j].d)
                        q[j].d ^= a[b[k]];
                }
            }
            ans[q[j].id] = q[j].d;
        }
    }
    for (int i = 1; i <= m; i++)
        print(ans[i]), putc('\n');
    io::flush();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注