[bzoj 4103] [Thu Summer Camp 2015]异或运算

长度分别为n,m的两数列x,y, 令 A[i][j] = x[i] xor y[j]. p个询问, 求A某矩形区域中第k大的值. (0≤xi,yj<2^31, 1≤n≤10^3, 1≤m≤3*10^5, 1≤p≤500, 保证k合法) 观察数据范围, 发现n和p都比较小.

是不是可以对每行暴力一下呢? 对y建可持久化Trie. 整体的第k大似乎不好考虑, 所以二分答案, 枚举x[i], 查询x[i]异或y[l,r]得到多少大于ans的数.

想到这个很开心......不过复杂度到了10^9这个级别, 跑得过去吗?

然后TLE......

极限数据5s+, 试着循环展开等wys优化, 结果反而变慢了 QAQ

看了下题解, 我还是太naive......

不用二分, 直接从高往低按位确定答案. 所有x[i]同时在Trie树上跑, 这样就能获知每个x[i]与y[l,r]异或出来的以 S+'1' 为前缀的0-1串的数量, 把它们加起来, 记为cnt. 如果cnt大于等于k, 则答案的这一位为1; 否则, 答案这一位为0, k -= cnt.

类似于带修改的区间第k小.

每次查询的时间复杂度减少一个log, 总共, 这里w=31.

const int N = 1000, M = 3e5;

struct Node {
	Node* ch[2];
	int v;
	Node();
} node[M*32 + 1], * nil = node, * root[M+1] = {nil}, * ptr = node + 1;

pair<Node*, Node*> p[N+1];
int a[N+1];

Node::Node(): v(0)
{
	ch[0] = ch[1] = nil;
}

void add(Node* p, Node* &o, int x, int k)
{
	o = ptr++;
	*o = *p;
	++o->v;

	if (k < 0) return;

	int b = (x >> k) & 1;
	add(p->ch[b], o->ch[b], x, k-1);
}

int query(int u, int d, int l, int r, int k)
{
	int ans = 0;
	rep (i, u, d+1) p[i] = make_pair(root[l-1], root[r]);
	per (i, 30, 0) {
		int cnt = 0;
		rep (j, u, d+1) {
			Node* x = p[j].first, * y = p[j].second;
			int t = ((a[j]>>i) & 1) ^ 1;
			cnt += y->ch[t]->v - x->ch[t]->v;
		}
		int b = cnt >= k;
		rep (j, u, d+1) {
			Node* &x = p[j].first, * &y = p[j].second;
			int t = ((a[j]>>i) & 1) ^ b;
			x = x->ch[t];
			y = y->ch[t];
		}
		ans |= b<<i;
		k -= b ? 0 : cnt;
	}
	return ans;
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	rep (i, 1, n+1)
		scanf("%d", a+i);
	rep (i, 1, m+1) {
		int b;
		scanf("%d", &b);
		add(root[i-1], root[i], b, 30);
	}
	int p;
	scanf("%d", &p);
	while (p--) {
		int u, d, l, r, k;
		scanf("%d%d%d%d%d", &u, &d, &l, &r, &k);
		printf("%d\n", query(u, d, l, r, k));
	}
	return 0;
}