莫队新科技——二次离线莫队入门

分析

珂朵莉给了你一个序列a，每次查询给一个区间 [l,r]

5 5 2
3 4 8 0 2
4 5
3 5
1 4
2 5
1 5

0
1
2
3
4

1≤n,m≤1e5,0≤ai,k<16384

一个序列a，m次询问，每次询问a[l,...,r]中有多少对(x,y)(l<=x<y<=r)满足某条件

1. 可以用莫队切
3. 第2条中的一个点对答案的影响可用前缀写成差分的形式.

add(i) 是加入一个点i 之后对res的影响, 而i假设当前区间是 [l, r], 则加入i = r + 1(即右端点右移动) 或者 加入i = r-1（即左端点左移动）, 则导致对res的影响是

//#include "stdafx.h"
//#define LOCAL
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
#define int long long
#define re register int
#define FE(cur) for(re h = head[cur], to; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define SQUARE(x) ((x) * (x))
namespace fastio
{
const int BUF = 1 << 21;
char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), pr1 == pr2) ? EOF : *pr1++; }
ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
{
x = 0; int f = 1; char c = gc();
while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f;
}
ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
ilv writeln(int x) { write(x);pc(10); }
{
char c = gc();
while(!isalpha(c)) c = gc();
while (isalpha(c)) *x++ = c, c = gc();
*x = 0;
}
ilv write(char *x) { while(*x) pc(*x++); }
ilv writeln(char *x) { write(x); pc(10); }
} using namespace fastio;
const int maxn = 1e5+5, FULL = (1 << 14);
int n, m, k, a[maxn], bel[maxn], B, ans[maxn], l = 1, r, num[FULL], kbit[3500], tot, res;
struct Q
{
int l, r, id;
bool operator <(const Q &rhs) const
{
return bel[l] == bel[rhs.l] ? r < rhs.r : bel[l] < bel[rhs.l];
}
} qs[maxn];

ili popcnt(int i)
{
int ans = 0;
while(i)
{
ans += i & 1;
i >>= 1;
}
return ans;
}

{
for (re j = 1; j <= tot; j++)
{
res += num[a[i] ^ kbit[j]];
}
++num[a[i]];
}

ilv sub(int i)
{
--num[a[i]];
for (re j = 1; j <= tot; j++)
{
res -= num[a[i] ^ kbit[j]];
}
}

signed main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
//freopen("d:\\my.out", "w", stdout);
#endif
for (re i = 0; i < FULL; i++)
{
if (popcnt(i) == k)
{
kbit[++tot] = i;
}
}
for (re i = 1; i <= n; i++)
{
bel[i] = (i - 1) / B + 1;
}
for (re i = 1; i <= m; i++)
{
}
sort(qs + 1, qs + m + 1);
for (re i = 1; i <= m; i++)
{
while(qs[i].l < l)
{
}
while(qs[i].l > l)
{
sub(l++);
}
while(qs[i].r < r)
{
sub(r--);
}
while(qs[i].r > r)
{
}
ans[qs[i].id] = res;
}
for (re i = 1; i <= m; i++)
{
writeln(ans[i]);
}
flush();
return 0;
}

ac情况（应该不会wa，仅仅是慢~）

• {a[l-1]，r， i}
• {a[l-1]，l-2， -i}
• {a[l]，r， -i}
• {a[l]，l-1， i}
• {a[r]，r-1， -i}
• {a[r]，l-1， i}
• {a[r+1]，r， i}
• {a[r+1]，l-1， -i}

emmm... 应该可以过了~

//#include "stdafx.h"
//#define LOCAL
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
#define int long long
#define re register int
#define FE(cur) for(re h = head[cur], to; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define SQUARE(x) ((x) * (x))
typedef pair<int, int> P;
namespace fastio
{
const int BUF = 1 << 21;
char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), pr1 == pr2) ? EOF : *pr1++; }
ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
{
x = 0; int f = 1; char c = gc();
while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f;
}
ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
ilv writeln(int x) { write(x);pc(10); }
{
char c = gc();
while(!isalpha(c)) c = gc();
while (isalpha(c)) *x++ = c, c = gc();
*x = 0;
}
ilv write(char *x) { while(*x) pc(*x++); }
ilv writeln(char *x) { write(x); pc(10); }
} using namespace fastio;
const int maxn = 1e5+5, FULL = 1 << 14;
int n, m, k, ans[maxn], B, bel[maxn], a[maxn], l = 1, r, kbit[3500], tot, t[FULL]; // t[z] 是当前前缀中和z异或恰好有k个比特位1的元素的个数
struct Q
{
int l, r, id, ans;
bool operator <(const Q &rhs) const
{
return bel[l] == bel[rhs.l] ? r < rhs.r : bel[l] < bel[rhs.l];
}
} qs[maxn];
vector<P> ts[maxn];

ili popcnt(int i)
{
int ans = 0;
while(i)
{
ans += i & 1;
i >>= 1;
}
return ans;
}

ilv init()
{
for (re i = 0; i < FULL; i++)
{
if (popcnt(i) == k)
{
kbit[++tot] = i;
}
}
}

ilv kk(int x)
{
for (re i = 1; i <= tot; i++)
{
++t[x ^ kbit[i]];
}
}

signed main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
//freopen("d:\\my.out", "w", stdout);
#endif
init();
for (re i = 1; i <= n; i++)
{
read(a[i]), bel[i] = (i - 1) / B + 1;
}
for (re i = 1; i <= m; i++)
{
}
sort(qs + 1, qs + m + 1);
for (re i = 1; i <= m; i++) // 模拟跑莫队, 离线所有贡献
{
while(qs[i].l < l)
{
if (r > 0)
{
ts[r].push_back(P(l - 1, i));
}
if (l > 2)
{
ts[l - 2].push_back(P(l - 1, -i));
}
--l;
}
while(qs[i].l > l)
{
if (r > 0)
{
ts[r].push_back(P(l, -i));
}
if (l > 1)
{
ts[l - 1].push_back(P(l, i));
}
++l;
}
while(qs[i].r < r)
{
if (r > 1)
{
ts[r - 1].push_back(P(r, -i));
}
if (l > 1)
{
ts[l - 1].push_back(P(r, i));
}
--r;
}
while(qs[i].r > r)
{
if (r > 0)
{
ts[r].push_back(P(r + 1, i));
}
if (l > 1)
{
ts[l - 1].push_back(P(r + 1, -i));
}
++r;
}
}
for (re i = 1; i <= n; i++)
{
kk(a[i]); // O(3432) 维护t
for (re j = 0, len = ts[i].size(), x, y, gx; j < len; j++) // O(sqrt{n})计算贡献
{
x = ts[i][j].first, y = ts[i][j].second; // 第|y|个询问, a[x]对当前前缀的贡献
gx = t[a[x]];  // a[x]对第|y|个询问作用在当前前缀上的贡献值
if (!k && x <= i) // 如果题目中k=0, 且x <= i, 则因为一个数和自己异或得到的也是0, 但是题目要求不能将自己和自己的异或计入答案, 所以要去掉这种情况(因为x<=i, 所以x被计入答案了)
{
--gx;
}
if (y < 0)
{
qs[-y].ans -= gx;
}
else
{
qs[y].ans += gx;
}
}
} // 离线计算所有贡献
for (re i = 1; i <= m; i++) // 差分还原
{
qs[i].ans += qs[i - 1].ans;
}
for (re i = 1; i <= m; i++)
{
ans[qs[i].id] = qs[i].ans;
}
for (re i = 1; i <= m; i++)
{
writeln(ans[i]);
}
flush();
return 0;
}

ac情况

• 第一类 a[x+1] 对 前缀a[1,..,x]的贡献,其中 x 会变化
• 第二类 a[l,..,r] 中所有数对 前缀a[1,..,x] 的贡献, 其中在一次端点的移动中,x是不会变化的.

(l, x, i或者-i);
(l + 1, x, i或者-i);
...
...
(r - 1, x, i或者-i);
(r, x, i或者-i);

//#include "stdafx.h"
//#define LOCAL
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
#define int long long
#define re register int
#define FE(cur) for(re h = head[cur], to; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define SQUARE(x) ((x) * (x))
typedef pair<int, int> P;
namespace fastio
{
const int BUF = 1 << 21;
char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), pr1 == pr2) ? EOF : *pr1++; }
ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
{
x = 0; int f = 1; char c = gc();
while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f;
}
ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
ilv writeln(int x) { write(x);pc(10); }
{
char c = gc();
while(!isalpha(c)) c = gc();
while (isalpha(c)) *x++ = c, c = gc();
*x = 0;
}
ilv write(char *x) { while(*x) pc(*x++); }
ilv writeln(char *x) { write(x); pc(10); }
} using namespace fastio;
const int maxn = 1e5+5, FULL = 1 << 14;
int n, m, k, ans[maxn], B, bel[maxn], a[maxn], l = 1, r, kbit[3500], tot, t[FULL], pref[maxn]; // pref[i] 是 a[i] 对前缀a[1,..,i-1] 的贡献
struct Q
{
int l, r, id, ans;
bool operator <(const Q &rhs) const
{
return bel[l] == bel[rhs.l] ? r < rhs.r : bel[l] < bel[rhs.l];
}
} qs[maxn];
struct T
{
int l, r, i; // 意义是a[l,...,r] 对 某前缀(到底是哪个前缀要看它在哪个vector中)做贡献, 而且这部分贡献是要加在(i>0)(或减去i<0)贡献 |i| 上的.
T(int l, int r, int i):l(l), r(r), i(i){}
};
vector<T> ts[maxn];

ili popcnt(int i)
{
int ans = 0;
while(i)
{
ans += i & 1;
i >>= 1;
}
return ans;
}

ilv init()
{
for (re i = 0; i < FULL; i++)
{
if (popcnt(i) == k)
{
kbit[++tot] = i;
}
}
}

ilv kk(int x)
{
for (re i = 1; i <= tot; i++)
{
++t[x ^ kbit[i]];
}
}

signed main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
//freopen("d:\\my.out", "w", stdout);
#endif
init();
for (re i = 1; i <= n; i++)
{
read(a[i]), bel[i] = (i - 1) / B + 1;
}
for (re i = 1; i <= m; i++)
{
}
sort(qs + 1, qs + m + 1);
for (re i = 1; i < n; i++)
{
kk(a[i]);
pref[i + 1] = t[a[i + 1]];
}
for (re i = 1; i <= m; i++) // 累加第一类贡献并离线第二类贡献
{
// 左端点左移
if (qs[i].l < l) // 打标记第二类贡献(即离线第二类贡献)
{
if (r > 0)
{
ts[r].push_back(T(qs[i].l, l - 1, i));
}
for (re j = l - 1; j >= qs[i].l; j--)  // 累加第一类贡献
{
qs[i].ans -= pref[j];
}
l = qs[i].l;
}

// 左端点右移
if (qs[i].l > l)
{
if (r > 0)
{
ts[r].push_back(T(l, qs[i].l - 1, -i));
}
for (re j = l; j <= qs[i].l - 1; j++)
{
qs[i].ans += pref[j];
}
l = qs[i].l;
}

// 右端点左移
if (qs[i].r < r)
{
if (l > 1)
{
ts[l - 1].push_back(T(qs[i].r + 1, r, i));
}
for (re j = r; j >= qs[i].r + 1; j--)
{
qs[i].ans -= pref[j];
}
r = qs[i].r;
}

// 右端点右移
if (qs[i].r > r)
{
if (l > 1)
{
ts[l - 1].push_back(T(r + 1, qs[i].r, -i));
}
for (re j = r + 1; j <= qs[i].r; j++)
{
qs[i].ans += pref[j];
}
r = qs[i].r;
}

}
memset(t, 0, sizeof(t)); // 因为要重新走一遍前缀
for (re i = 1; i <= n; i++)
{
kk(a[i]);
for (re j = 0, len = ts[i].size(), x, y, z, gx; j < len; j++)
{
x = ts[i][j].l, y = ts[i][j].r, z = ts[i][j].i; // a[x, y] 对 第|z| 个询问的第二类贡献(z >0 则就是加, z <0 就是减)
for (re p = x; p <= y; p++)
{
gx = t[a[p]];
if (!k && p <= i)
{
--gx;
}
if (z < 0)
{
qs[-z].ans -= gx;
}
else
{
qs[z].ans += gx;
}
}
}
}
for (re i = 1; i <= m; i++)
{
qs[i].ans += qs[i - 1].ans;
}
for (re i = 1; i <= m; i++)
{
ans[qs[i].id] = qs[i].ans;
}
for (re i = 1; i <= m; i++)
{
writeln(ans[i]);
}
flush();
return 0;
}

ac情况

所属题目
P4887 【模板】莫队二次离线（第十四分块(前体)）

Accepted

100

C++

4.24KB

949ms

19.34MB

[1]《优雅的暴力——莫队算法》

0 条评论

• leetcode 周赛155 | 项目管理之拓扑排序算法

今天看了下leetcode周赛的题目，没怎么做，第四题是一道Hard题目，看了下题意感觉要用拓扑排序，但是这道题除了依赖关系，还有一个分组的变量，导致这道题处理...

• Codeforces Round #549（div1）简析

正解貌似有分四种情况什么的，我做时是发现各个起点其实都等价的，所以随便选一个起点，再暴举终点以暴举答案，更新即可。

• 搜索专题3 | 八数码 HDU - 1043

本搜索专题会参考vjudge上的《kuangbin带你飞》系列题目，前面2篇是基础题，后面会慢慢复杂起来！加油！

• 算法训练 Hanoi问题

如果将课本上的Hanoi塔问题稍做修改：仍然是给定N只盘子，3根柱子，但是允许每次最多移动相邻的M只盘子（当然移动盘子的数目也可以小于M）,最少需要多少次？...

• 【Windows Of CCPC HDU - 6708】【打表，找规律】

题意：给出一个整数k，要求你输出一个长和宽均为2^k^ 的符合要求的矩阵。比如k等于1时输出 \[ \begin{matrix} C & C \\ ...

• 第3天：最近笔试编程题汇总

首先跟大家说声抱歉，由于最近有面试和笔试，所以一直刷题就没时间更新博客了。随着秋招进入了一个白热化阶段，我们所投的岗位也已经进入了面试和笔试阶段。最近的笔试...

• CodeForces #549 Div.2 ELynyrd Skynyrd

对于每个区间，我们从右边边界，往左边走，如果能走n-1次，那说明以右边边界为起点存在一个题目中说的子链。

• LWC 55：714. Best Time to Buy and Sell Stock with Transaction Fee

LWC 55：714. Best Time to Buy and Sell Stock with Transaction Fee 传送门：714. Best T...

• 基于daemon模式的rsync同步服务

1.配置rsync服务器(文件提供者) #yum install rsync -y  #vim /etc/xinetd.d/rsync      disable...