网站建设gzzctyi,徐州市云龙区建设局网站,网站底部友情链接,wordpress 免插件正题
题目链接:https://www.luogu.com.cn/problem/P4887 题目大意
给出一个长度为nnn的序列aaa。mmm次询问[l,r][l,r][l,r]求有多少个l≤ij≤rl\leq i j\leq rl≤ij≤r满足aixoraja_i\ xor\ a_jai xor aj二进制下恰好有kkk个111。 1≤n,q≤105,0≤ai,k21…正题
题目链接:https://www.luogu.com.cn/problem/P4887 题目大意
给出一个长度为nnn的序列aaa。mmm次询问[l,r][l,r][l,r]求有多少个l≤ij≤rl\leq i j\leq rl≤ij≤r满足aixoraja_i\ xor\ a_jai xor aj二进制下恰好有kkk个111。
1≤n,q≤105,0≤ai,k2141\leq n,q\leq 10^5,0\leq a_i,k2^{14}1≤n,q≤105,0≤ai,k214 解题思路
记f(x,i)f(x,i)f(x,i)表示1∼i1\sim i1∼i中有多少个aaa和axa_xax满足条件假设我们已经知道了区间[l,r][l,r][l,r]的答案以[l,r]→[l,r1][l,r]\rightarrow [l,r1][l,r]→[l,r1]为例答案会增加f(r1,r)−f(r1,l−1)f(r1,r)-f(r1,l-1)f(r1,r)−f(r1,l−1)f(r1,r)f(r1,r)f(r1,r)我们可以直接预处理出每个。
至于f(r1,l−1)f(r1,l-1)f(r1,l−1)我们发现我们的桶和f(x,i)f(x,i)f(x,i)中的iii也就是l−1l-1l−1有关在rrr移动的过程中l−1l-1l−1是不变的所以我们可以将r→rkr\rightarrow rkr→rk这个过程离线下来在指针枚举l−1l-1l−1时统一处理。
其他指针的移动一样处理即可。 code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define ll long long
using namespace std;
const ll N1e510,L114,T316;
struct node{ll l,r,id;
}q[N];
ll n,m,k,c[L],v[L],pre[N],a[N],s[N],ans[N];
vectorint b;
vectornode u[N];
bool cmp(node x,node y)
{return (x.l/Ty.l/T)?(x.ry.r):(x.l/Ty.l/T);}
signed main()
{scanf(%lld%lld%lld,n,m,k);for(ll i1;iL;i)c[i]c[i-(i-i)]1;for(ll i0;iL;i)if(c[i]k)b.push_back(i);if(k14){for(ll i1;im;i)puts(0);return 0;}for(ll i1;in;i)scanf(%lld,a[i]);for(ll i1;in;i){pre[i]v[a[i]];for(ll j0;jb.size();j)v[a[i]^b[j]];}for(ll i1,l,r;im;i){scanf(%lld%lld,q[i].l,q[i].r);q[i].idi;}sort(q1,q1m,cmp);ll l1,r0;for(ll i1;im;i){if(lq[i].l)u[r].push_back((node){l,q[i].l-1,-i});while(lq[i].l)s[i]pre[l],l;if(lq[i].l)u[r].push_back((node){q[i].l,l-1,i});while(lq[i].l)l--,s[i]-pre[l];if(rq[i].r)u[l-1].push_back((node){r1,q[i].r,-i});while(rq[i].r)r,s[i]pre[r];if(rq[i].r)u[l-1].push_back((node){q[i].r1,r,i});while(rq[i].r)s[i]-pre[r],r--;}memset(v,0,sizeof(v));for(ll i1;in;i){for(ll j0;jb.size();j)v[a[i]^b[j]];for(ll j0;ju[i].size();j){for(ll xu[i][j].l;xu[i][j].r;x){ll tmpv[a[x]];if(k0xi)tmp--;if(u[i][j].id0)s[u[i][j].id]tmp;else s[-u[i][j].id]-tmp;}}}for(ll i1;im;i)s[i]s[i-1],ans[q[i].id]s[i];for(ll i1;im;i)printf(%lld\n,ans[i]);return 0;
}
