sto orz

考虑莫队，每次移动端点，我们都要询问区间内和当前数字异或有 \(k\) 个 \(1\) 的数字个数

询问 \([l,r]\) 可以再次离线，拆成询问 \([1,l-1]\) 和 \([l,r]\)

然后考虑莫队要移动 \([l,r]\) 的 \(l\) 到 \(p\)

假设 \(p>l\)

那么相当于每次询问 \(a[l]\) 和 \([l+1,r]\)，然后 \(++l\) 直到 \(l=p\)

即每次询问 \(a[l]\) 和 \([1,l]\) ，\(a[l]\) 和 \([1,r]\)

对于前面的部分，它每次都是前缀区间的最后一个数字询问前缀区间，可以预处理

对于后面的部分，它每次都是一个数字询问一个固定的区间，直接在 \(r\) 处打上一个询问 \(l,p\) 的标记，之后离线暴力询问 \(l,p\)，这一部分复杂度和莫队一样

然后其它移动端点的方法类似

大力讨论一下即可

# include 
    
     using namespace std;typedef long long ll;namespace IO {    const int maxn(1 << 21 | 1);    char ibuf[maxn], *iS, *iT, c;    int f;    inline char Getc() {        return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++;    }        template 
     
       inline void In(Int &x) {        for (f = 1, c = Getc(); c < '0' || c > '9'; c = Getc()) f = c == '-' ? -1 : 1;        for (x = 0; c >= '0' && c <= '9'; c = Getc()) x = x * 10 + (c ^ 48);        x *= f;    }}using IO :: In;const int maxn(2e5 + 5);int cnt, v[maxn], n, m, k, a[maxn], sum[maxn], blo;ll cur, ret[maxn], ans[maxn], pre1[maxn], pre2[maxn];struct Qry {    int l, r, id;    inline bool operator < (Qry b) const {        return l / blo != b.l / blo ? l < b.l : r < b.r;    }} qry[maxn];vector 
      
        q[maxn];# define pk push_backint main() {    In(n), In(m), In(k), blo = sqrt(n);    for (int i = 0; i < 16384; ++i) {        int x = i, c = 0;        for (; x; x ^= x & -x) ++c;        if (c == k) v[++cnt] = i;    }    for (int i = 1; i <= n; ++i) In(a[i]);    for (int i = 1; i <= m; ++i) In(qry[i].l), In(qry[i].r), qry[i].id = i;    sort(qry + 1, qry + m + 1);    for (int i = 1, l = qry[1].r + 1, r = qry[1].r; i <= m; ++i) {        if (l < qry[i].l) q[r].pk((Qry){l, qry[i].l - 1, qry[i].id << 1});        else if (l > qry[i].l) q[r].pk((Qry){qry[i].l, l - 1, qry[i].id << 1});        l = qry[i].l;        if (r < qry[i].r) q[l - 1].pk((Qry){r + 1, qry[i].r, qry[i].id << 1 | 1});        else if (r > qry[i].r) q[l - 1].pk((Qry){qry[i].r + 1, r, qry[i].id << 1 | 1});        r = qry[i].r;    }    for (int i = 1; i <= n; ++i) {        pre1[i] = pre1[i - 1] + sum[a[i]];        for (int j = 1; j <= cnt; ++j) ++sum[a[i] ^ v[j]];        pre2[i] = pre2[i - 1] + sum[a[i]];        for (auto t : q[i]) for (int j = t.l; j <= t.r; ++j) ret[t.id] += sum[a[j]];    }    for (int i = 1, l = qry[1].r + 1, r = qry[1].r; i <= m; ++i) {        if (l < qry[i].l) cur += pre2[qry[i].l - 1] - pre2[l - 1] - ret[qry[i].id << 1];        else if (l > qry[i].l) cur += ret[qry[i].id << 1] - pre2[l - 1] + pre2[qry[i].l - 1];        l = qry[i].l;        if (r < qry[i].r) cur += pre1[qry[i].r] - pre1[r] - ret[qry[i].id << 1 | 1];        else if (r > qry[i].r) cur += ret[qry[i].id << 1 | 1] - pre1[r] + pre1[qry[i].r];        ans[qry[i].id] = cur, r = qry[i].r;    }    for (int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);    return 0;}