[洛谷P4887] 【模板】莫队二次离线（第十四分块(前体)）
前言
考试就指望离谱分块骗分了，还不赶快学！
题目
洛谷
讲解
好嘛，二离刚做完板子，还不是很懂啥时候用，不过看题解区都这么说：
- 能莫队。
- 更新不是 \(O(1)\)。
然后我们把要更新的区间存下来，在外面跑就行，大概就是这么个意思。
这道题把区间贡献拆成前缀，预处理之后可以快速求贡献。
时间复杂度 \(O(n\sqrt{n}+C_{14}^{k}n)\)，看上去比较离谱，但是能过。
代码
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 100005;
int n,m,k,B;
int a[MAXN];
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int s[MAXN],tot,t[MAXN],bl[MAXN],pre[MAXN];
LL ans[MAXN];
struct Query{
int l,r,ID;
bool operator < (const Query &px)const{
if(bl[l] ^ bl[px.l]) return bl[l] < bl[px.l];
return r < px.r;
}
}q[MAXN];
vector Q[MAXN];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); m = Read(); k = Read();
if(k > 14){while(m --> 0) Put(0,'\n');return 0;}
for(int i = 0;i < 16384;++ i) if(__builtin_popcount(i) == k) s[++tot] = i;
B = ceil(sqrt(n));
for(int i = 1;i <= n;++ i){
pre[i] = t[a[i] = Read()]; bl[i] = (i-1)/B+1;
for(int j = 1;j <= tot;++ j) ++t[a[i]^s[j]];
}
for(int i = 1;i <= m;++ i) q[i].l = Read(),q[i].r = Read(),q[i].ID = i;
sort(q+1,q+m+1);
// for(int i = 1;i <= m;++ i) printf("%d %d %d\n",q[i].l,q[i].r,q[i].ID);
for(int i = 1,L = 1,R = 0;i <= m;++ i){
if(R < q[i].r) Q[L-1].emplace_back(Query{R+1,q[i].r,-q[i].ID});
while(R < q[i].r) ans[q[i].ID] += pre[++R];
if(L > q[i].l) Q[R].emplace_back(Query{q[i].l,L-1,q[i].ID});
while(L > q[i].l) ans[q[i].ID] -= pre[--L];
if(L < q[i].l) Q[R].emplace_back(Query{L,q[i].l-1,-q[i].ID});
while(L < q[i].l) ans[q[i].ID] += pre[L++];
if(R > q[i].r) Q[L-1].emplace_back(Query{q[i].r+1,R,q[i].ID});
while(R > q[i].r) ans[q[i].ID] -= pre[R--];
}
for(int i = 0;i < 16384;++ i) t[i] = 0;
for(int i = 1;i <= n;++ i){
for(int j = 1;j <= tot;++ j) ++t[a[i]^s[j]];
for(auto &A : Q[i]){
for(int j = A.l,val;j <= A.r;++ j){
val = t[a[j]];
if(j <= i && !k) --val;
if(A.ID < 0) ans[-A.ID] -= val;
else ans[A.ID] += val;
}
}
}
for(int i = 1;i <= m;++ i) ans[q[i].ID] += ans[q[i-1].ID];
for(int i = 1;i <= m;++ i) Put(ans[i],'\n');
return 0;
}