莫对和分块模板

分块和莫队都是xjb搞的东西，但是分块是用来解决在线的问题的，莫队是用来解决离线的问题的。

当你发现一个算法没法可做并且可以离线的话，你就可以尝试使用莫队算法。当然，如果存在乱七八糟的更新的东西的话，你就可以用分块去做

分块的学习的链接：戳这里

分块的精髓就是如何分块，其他的查询和询问操作的话每道题都不一样。所以这里就只给出如何建块即可。

///block表示块的大小，num表示一共分成多少个块

///belong表示这个数在哪个块里面，l和r表示左右边界

再讲讲分块的查询操作：

查询操作的话，如果x和y是在同一个块里面，就暴力。
如果不是在一个块里面的话，先暴力[x, r[belong[x]]]，然后再暴力块
然后再暴力[l[belong[y]], y]

void build(){
    block = sqrt(n); num = n / block;
    if (n % block) num++;
    for (int i = 1; i <= num; i++)
        l[i] = (i - 1) * block + 1, r[i] = i * block;
    r[num] = n;
    for (int i = 1; i <= n; i++){
        belong[i] = (i - 1) / block + 1;
    }
}

莫队算法学习的链接：戳这里

http://www.cnblogs.com/qscqesze/category/782588.html莫队算法的题目可以从这里找

这里仅仅给出最简单的一个

①只有查询操作而没有修改操作

在条件中，我们对于所有的数据的位置进行分块，所以postion[i]就表示i所在的块是什么

莫队算法的适用条件为：只有查询操作，而没有修改操作，

http://codeforces.com/contest/617/problem/E是这道题的代码这道题具体看这里吧：链接

//看看会不会爆int! 或者绝对值问题。
#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define ALL(a) a.begin(), a.end()
#define haha printf("haha
")
const int MAXN = 5e6 ;
int pos[MAXN], a[MAXN];
int n, m, k;
struct Query{
    int l, r, id;
}Q[MAXN];
bool cmp(Query a, Query b){
    if (pos[a.l] == pos[b.l]) return a.r < b.r;
    return a.l < b.l;
}

LL ans[MAXN], cnt[MAXN], res;

void del(int x){
    cnt[a[x]]--;
    res -= cnt[a[x] ^ k];
}

void add(int x){
    res += cnt[a[x] ^ k];
    cnt[a[x]]++;
}

int main(){
    std::cin >> n >> m >> k;
    int sz = sqrt(n * 1.0);
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / sz;
    for (int i = 1; i <= n; i++){
        scanf("%d", a + i);
        a[i] ^= a[i - 1];
    }
    for (int i = 1; i <= m; i++){
        scanf("%d%d", &Q[i].l, &Q[i].r); Q[i].id = i;
    }
    std::sort(Q + 1, Q + 1 + m, cmp);
    int L = 1, R = 0;//因为要把第一个位置给放进来
    for (int i = 1; i <= m; i++){
        while (R < Q[i].r) add(++R);
        while (R > Q[i].r) del(R--);
        while (L > Q[i].l - 1) add(--L);
        while (L < Q[i].l - 1) del(L++);
        ans[Q[i].id] = res;
    }
    for (int i = 1; i <= m; i++)
        std::cout << ans[i] << std::endl;
    return 0;
}

莫对 和分块 模板

莫对和分块模板