区间更新+线段树
题目当中说的区间更新比较有歧义，其实一共有2种区间更新，一种是内区间更新，还有一种是外区间更新。啥意思？比如说，我们现在说[a,b][a,b][a,b]的所有小孩身高都是165cm165cm165cm，这种就是内区间更新。外区间更新就是：端点aaa和端点bbb满足条件，那么如果有k≤a,m≥bk\leq a,m\geq bk≤a,m≥b，则在[k,m][k,m][k,m]中都满足这个条件。
那么对于内区间更新一定是用线段树，那么外区间更新怎么做？
首先先看实际应用场景：
给一个序列[a1,a2,a3,...,an][a_{1},a_{2},a_{3},...,a{n}][a1,a2,a3,...,an]，问一个闭区间[l,r][l,r][l,r]是否存在两个数异或和为xxx。
这个题拿过来想都不用想，直接线性基 ，就应该知道先看都有哪些数异或和为xxx，但是显然不能O(n2)O(n^{2})O(n2)判断。我们知道一个定理为
a⊕b=c,则a⊕c=ba\oplus b=c,则a\oplus c=ba⊕b=c,则a⊕c=b
所以直接线性扫一遍，然后记录各个数的位置，用这种方法去重：
for (int i = 1; i <= n; i++){int a;scanf_s("%d", &a);cnt[a]++;edge[a].push_back(i);max_a = max(max_a, a);}vector kl;for (int i = 0; i <= max_a; i++){if (cnt[i])kl.push_back(i);//这块去重left1[i] = n + 1;}
然后对klklkl这个数组扫一遍，∀i,kl[i]\forall i,kl[i]∀i,kl[i]的异或kl[i]⊕xkl[i]\oplus xkl[i]⊕x在edgeedgeedge数组当中我们都已经记录下来了，所以只需要连边即可。这两个数可以称作一个对，对于每一个左边界，我们只需要知道他的右边界最近是哪，将这个信息存在leftleftleft数组当中。那么在判断[l,r][l,r][l,r]时，我们自然就可以用线段树来判断这个区间内的leftleftleft的最小值就可以了。如果这个最小值小于rrr，则yesyesyes否则nonono.
AC代码:
//区间+并查集才是正解
#include
#include
#include
#include
using namespace std;
const int length = 2e6 + 5;
int cnt[length];
int f[length];
vector> edge(length);
int vis[length];
int tree[length];
int left1[length];
void update(int L, int R, int l, int r, int cnt, int v)
{if (l >= L && r <= R){tree[cnt]=v;return;}if (l > R || r < L)return ;int mid = (l + r) / 2;update(L, R, l, mid, cnt*2,v);update(L, R, mid + 1, r, cnt*2+1,v);tree[cnt] = min(tree[cnt * 2], tree[cnt * 2 + 1]);
}
int query(int L, int R, int l, int r, int cnt)
{if (l >= L && r <= R)return tree[cnt];if (l > R || r < L)return INT_MAX;int mid = (l + r) / 2;int a = query(L, R, l, mid, cnt*2);int b = query(L, R, mid + 1, r, cnt*2+1);return min(a, b);
}
int find1(int x)
{return f[x]=(x == f[x]) ? x : find1(f[x]);
}
int main(void)
{int n, m, x;scanf_s("%d%d%d", &n, &m, &x);int max_a = -1;for (int i = 1; i <= n; i++){int a;scanf_s("%d", &a);cnt[a]++;edge[a].push_back(i);max_a = max(max_a, a);}vector kl;for (int i = 0; i <= max_a; i++){if (cnt[i])kl.push_back(i);//这块去重left1[i] = n + 1;}for (int i = 0; i < kl.size(); i++){int s = kl[i];int t = kl[i] ^ x;if (cnt[t] != 0&&!vis[s]&&!vis[t]){vis[s] = 1;vis[t] = 1;for (int m : edge[s]){for (int j : edge[t]){if (m == j)continue;int a = m;int b = j;if (m > j){a = j;b = m;}left1[a] = min(left1[a], b);}}}}for (int i = 1; i <= n; i++){update(i, i, 1, n, 1, left1[i]);}for (int i = 0; i < m; i++){int a, b;scanf_s("%d%d", &a, &b);int a1 = query(a, b-1, 1, n, 1);if (a1<=b)printf("yes\n");elseprintf("no\n");}
}
沙雕线段树代码：
//可以用线段树维护一个线性基
//然后每次查询就看相应的子树有没有就可以了
#include
#include
int x;
struct s
{int o[25];void ist(int v){for (int i = 24; i >= 0; i--){if (v == 0)return;if (v&(1 << i)){if (o[i] == 0){o[i] = v;return;}v = v ^ o[i];}}}void clc(){memset(o, 0, sizeof(o));}
};
const int length = 1e5 + 5;
struct s tree[length<<1];
struct s mrg(struct s &a, struct s &b)
{struct s tmp = a;for (int i = 24; i >= 0; i--){tmp.ist(b.o[i]);}return tmp;
}
void update(int L, int R, int l, int r, int cnt, int v)
{if (l >= L && r <= R){tree[cnt].ist(v);return;}if (l > R || r < L)return;int mid = (l + r) / 2;update(L, R, l, mid, cnt * 2, v);update(L, R, mid + 1, r, cnt * 2 + 1, v);tree[cnt] = mrg(tree[cnt * 2], tree[cnt * 2 + 1]);
}
struct s query(int L, int R, int l, int r, int cnt)
{if (l >= L && r <= R){return tree[cnt];}if (l > R || r < L){struct s tmp;tmp.clc();return tmp;}int mid = (l + r) / 2;struct s a=query(L, R, l, mid, cnt * 2);struct s b=query(L, R, mid + 1, r, cnt * 2 + 1);return mrg(a, b);
}
bool solve(int L, int R, int l, int r, int cnt)
{struct s pl= query(L, R, l, r, cnt);for (int i = 0; i < 25; i++){if (x&(1 << i)){if (pl.o[i] != 0){continue;}elsereturn false;}}return true;
}
int main(void)
{int n, m;scanf_s("%d%d%d", &n, &m, &x);for (int i = 1; i <= n; i++){int a;scanf_s("%d", &a);update(i, i, 1, n, 1,a);}for (int i = 0; i < m; i++){int l, r;scanf_s("%d%d", &l, &r);bool a=solve(l, r, 1, n, 1);//可以经过查询返回一个线性基//然后用solve判断x在不在里头if (a)printf("yes\n");elseprintf("no\n");}
}
文末彩蛋：我还想到另一种做法，就是用并查集+线段树。将任意一个满足要求的对