題目大意

給出n,m,k，有n個數的序列，m次詢問一段區間，問異或和等于K的子區間的個數。

題解

本題一看就是莫隊。但要解決該題需要以下性質：

定理：

$$a\oplus b=c\Leftrightarrow a\oplus c=b\Leftrightarrow b\oplus c=a$$

推論：

$$\oplus_{i=l}^r A_i= \oplus_{i=1}^r A_i \oplus \oplus_{i-1}^{l-1}A_i$$

因此，我們對每個節點維護它的前綴和。比如說，如果右方加入一個節點，因為右方r的前綴和異或左面l的前綴和的結果表示的就是[l+1,r]的異或和。此時增加的滿足條件的子區間的個數，根據定理，便是當前區間中前綴和的值異或上新加入的節點的前綴和的值等于K的點的數量。這就可以用莫隊的桶來維護了。

#define _DEBUG#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std;const int MAX_N = 100010; int K; int BASE;struct CaptainMo {int N, OpCnt, Sum;int PrefixValCnt[MAX_N];struct Data{int CurVal, Prefix;}_datas[MAX_N];struct Query{int L, R;int Ans;Query *This;Query():This(this){}bool operator < (const Query& a)const{return L / BASE == a.L / BASE ? R < a.R : L / BASE < a.L / BASE;}}_qs[MAX_N], temp[MAX_N];void InRange(Data cur){Sum += PrefixValCnt[cur.Prefix ^ K];PrefixValCnt[cur.Prefix]++;}void OutRange(Data cur){Sum -= PrefixValCnt[cur.Prefix ^ K];PrefixValCnt[cur.Prefix]--;}void Init(){for(int i = 1; i <= OpCnt; i++)_qs[i].L--;for(int i = 1; i <= N; i++)_datas[i].Prefix = _datas[i - 1].Prefix ^ _datas[i].CurVal;BASE = sqrt(N);memcpy(temp, _qs, sizeof(_qs));sort(temp + 1, temp + OpCnt + 1);}void Proceed(){int l = 0, r = 0;Sum = 0;PrefixValCnt[0] = 1;for(int i = 1; i <= OpCnt; i++){while(r > temp[i].R)OutRange(_datas[r--]);while(r < temp[i].R)InRange(_datas[++r]);while(l < temp[i].L)OutRange(_datas[l++]);while(l > temp[i].L)InRange(_datas[--l]);temp[i].This->Ans = Sum;}} }g;int main() {scanf("%d%d%d", &g.N, &g.OpCnt, &K);for(int i = 1; i <= g.N; i++)scanf("%d", &g._datas[i].CurVal);for(int i = 1; i <= g.OpCnt; i++)scanf("%d%d", &g._qs[i].L, &g._qs[i].R);g.Init();g.Proceed();for(int i = 1; i <= g.OpCnt; i++)printf("%d\n", g._qs[i].Ans);return 0; }

　　

轉載于:https://www.cnblogs.com/headboy2002/p/9219452.html

總結

以上是生活随笔為你收集整理的luogu4462 异或序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。