听课笔记
AC代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 500010, M = 5000007, INF = 0x3f3f3f3f;
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
int n, m;
int block, k;
int w[N];
ll ans[N];
struct Query
{
int id, l, r;
ll res;
}q[N];
struct Range
{
int id, l, r, t;//t表示的是类型+/-
};
vector<Range>range[N];
int f[N], g[N];
//得到x的二进制下有多少个1
inline int get_count(int x)
{
int res = 0;
while(x)res += x & 1, x >>= 1;
return res;
}
inline int get_block(int x)
{
return x / block;
}
bool cmp(const Query& a, const Query& b)
{
int x = get_block(a.l);
int y = get_block(b.l);
if(x != y)return x < y;
return a.r < b.r;
}
int main()
{
n = read(), m = read(), k = read();
for(int i = 1; i <= n; ++ i)
w[i] = read();
vector<int> nums;
//预处理出给定范围内所有二进制数为k的数
for(int i = 0; i < (1 << 14); ++ i){
if(get_count(i) == k)
nums.push_back(i);
}
for(int i = 1; i <= n; ++ i){
//g[i]是一个桶表示前i个数中有多少个数与x配对
for(auto it : nums) ++ g[w[i] ^ it];
//f[i]表示w1 ~ wi中有多少个数与wi+1配对
f[i] = g[w[i + 1]];
}
for(int i = 0; i < m; ++ i){
int l = read(), r = read();
q[i] = {i, l, r};
}
block = sqrt(n);
sort(q, q + m, cmp);
for(int i = 0, L = 1, R = 0; i < m; ++ i){
int l = q[i].l, r = q[i].r, id = q[i].id;
if(R < r) range[L - 1].push_back({i, R + 1, r, -1});
while(R < r) q[i].res += f[R ++ ];
if(R > r) range[L - 1].push_back({i, r + 1, R, 1});
while(R > r) q[i].res -= f[ -- R];//S(R) = f(R - 1)
if(L < l) range[R].push_back({i, L, l - 1, -1});
while(L < l) q[i].res += f[L - 1] + (k == 0), L ++ ;
if(L > l) range[R].push_back({i, l, L - 1, 1});
while(L > l) q[i].res -= f[L - 2] + (k == 0), L -- ;
}
memset(g, 0, sizeof g);
for(int i = 1; i <= n; ++ i){
for(auto it : nums) ++ g[w[i] ^it];
for(auto it : range[i]){
int id = it.id, l = it.l, r = it.r, t = it.t;
for(int x = l; x <= r; ++ x)
q[id].res += g[w[x]] * t;
}
}
for(int i = 1; i < m; ++ i) q[i].res += q[i - 1].res;
for(int i = 0; i < m; ++ i) ans[q[i].id] = q[i].res;
for(int i = 0; i < m; ++ i) printf("%lld\n", ans[i]);
return 0;
}
图片怎么显示不了了,大佬有无传送门orz
第一次见这么认真的!!!
是的
+1
最后的三个for第一个前缀和咋理解哇呜呜呜