dede5.7模板 新闻文章网站源码,什么网站都有漏洞,wordpress图书页面,营销型网站建设宣传语题目大意 给出n,m,k#xff0c;有n个数的序列#xff0c;m次询问一段区间#xff0c;问异或和等于K的子区间的个数。 题解 本题一看就是莫队。但要解决该题需要以下性质#xff1a; 定理#xff1a; $$a\oplus bc\Leftrightarrow a\oplus cb\Leftrightarrow b\oplus ca$$ …题目大意 给出n,m,k有n个数的序列m次询问一段区间问异或和等于K的子区间的个数。 题解 本题一看就是莫队。但要解决该题需要以下性质 定理 $$a\oplus bc\Leftrightarrow a\oplus cb\Leftrightarrow b\oplus ca$$ 推论 $$\oplus_{il}^r A_i \oplus_{i1}^r A_i \oplus \oplus_{i-1}^{l-1}A_i$$ 因此我们对每个节点维护它的前缀和。比如说如果右方加入一个节点因为右方r的前缀和异或左面l的前缀和的结果表示的就是[l1,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