莫队算法
标签：for minus names add sort bsp using space span
莫队算法使用分块的思想，可以解决一类离线区间询问问题。 对于序列上的区间询问问题，如果从 [l,r] 的答案能够 O(1) 扩展到 [l−1,r],[l+1,r],[l,r+1],[l,r−1] 的答案，那么可以在 O(n√?n???) 的复杂度内求出所有询问的答案。 将整个区间分为√?n个块，然后进行排序。L需要在对应的块中，而在上面的前提下R要递增。
#include using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int n, m, k, a[N], cnt[N * 11] = {0}, b;
LL nowAns = 0, ans[N];
struct query {
int l, r, id;
bool operator const query &rhs) const {
if(l/b == rhs.l/b) return r > rhs.r;
return l > rhs.l;
}
}q[N];
void add(int p) {
nowAns += cnt[a[p] ^ k];
cnt[a[p]]++;
}
void del(int p) {
cnt[a[p]]--;
nowAns -= cnt[a[p] ^ k];
}
void solve() {
b = (int)sqrt(n);
sort(q, q + m);
int l = 0, r = 0;
cnt[0] = 1;
for(int i = 0; i ) {
const query &c = q[i];
while(l > c.l) add(--l);
while(r r);
while(l );
while(r > c.r) del(r--);
ans[c.id] = nowAns;
}
for(int i = 0; i endl;
}
int main() {
cin >> n >> m >> k;
for(int i = 1; i "%d", a + i), a[i] ^= a[i - 1];
for(int i = 0; i "%d%d", &q[i].l, &q[i].r), q[i].l--, q[i].id = i;
solve();
}
莫队算法
标签：for minus names add sort bsp using space span
原文地址：https://www.cnblogs.com/hanasaki/p/11025135.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
莫队算法
文章链接：http://soscw.com/essay/24738.html
评论