问题：
定义一个非负整数序列是好的，当且仅当将序列中所有元素依次按位与之后的结果 为完全平方数。 给定一个非负整数序列 a1,a2,...,an ，q 次询问，每次询问给出 L,R ，对于子序列 aL,...,aR ，求有多少个非空连续子序列是好的。
解：
首先对于每一个询问按照右端点排序 固定右端点 对询问进行离线操作 和老板说这是常规操作
注意到 对于一段区间 如果受到改变受到改变 那么就是 某一位最近的上有0 所以这是log级别 超级快 真是没有想到还有这种操作
所以我们想到了开一个NEXT数组 记录 当前i位置 j位上 最近为0 的位置
如果i位置是完全平方 那么i到nex-1 是完全平方 那么就可以在[R,NEX+1]的位置+1
否则就跳过这个区间
不是完全平方同理 查询完全平方的方法 看开方的^2是否等于原数
对于询问 就是查询[ L,R ]区间覆盖次数
本来想用树状数组的 想想还是线段树好些 还是gugugugu
注意用fread
#include<stdio.h>
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define maxnn 5000005
#define maxn 8000005
#define lowbit(i) (i&(-i))
#define ll long long
ll n,m;
ll T;
ll a[maxnn];
ll pre[maxnn][35];
ll c[maxnn];
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
inline int R()
{
char t=GC;
int x=0;
while(!isdigit(t)) t=GC;
while(isdigit(t)) x=x*10+t-48,t=GC;
return x;
}
struct node
{
ll x,y,val,laz;
} tr[maxn];
inline void pushdown(int p)
{
tr[p<<1].val+=(tr[p<<1].y-tr[p<<1].x+1)*tr[p].laz;
tr[p<<1|1].val+=(tr[p<<1|1].y-tr[p<<1|1].x+1)*tr[p].laz;
tr[p<<1].laz+=tr[p].laz;
tr[p<<1|1].laz+=tr[p].laz;
tr[p].laz=0;
}
void build(int p,ll a,ll b)
{
tr[p].x=a;
tr[p].y=b;
tr[p].val=0;
tr[p].laz=0;
if(a<b)
{
ll mid=(a+b)>>1;
build(p<<1,a,mid);
build(p<<1|1,mid+1,b);
tr[p].val+=tr[p<<1].val+tr[p<<1|1].val;
}
}
void add(int p,int a,int b)
{
if(tr[p].x>=a&&tr[p].y<=b)
{
tr[p].val+=(tr[p].y-tr[p].x+1);
tr[p].laz+=1;
}
else
{
if(tr[p].laz)
{
pushdown(p);
}
ll mid=(tr[p].x+tr[p].y)>>1;
if(a<=mid)
{
add(p<<1,a,b);
}
if(b>mid)
{
add(p<<1|1,a,b);
}
tr[p].val=tr[p<<1].val+tr[p<<1|1].val;
}
}
ll get(int p,int a,int b)
{
if(tr[p].x>=a&&tr[p].y<=b)
{
return tr[p].val;
}
else
{ if(tr[p].laz)
{
pushdown(p);
}
ll l=0,r=0;
ll mid=(tr[p].x+tr[p].y)>>1;
if(a<=mid)
{
l=get(p<<1,a,b);
}
if(b>mid)
{
r=get(p<<1|1,a,b);
}
return l+r;
}
}
struct nodde
{
ll l,r,id;
}q[maxnn];
bool cmp(nodde a,nodde b)
{
if(a.r==b.r)
return a.l<b.l;
return a.r<b.r;
}
ll ans[maxnn];
inline ll chkmax(ll a,ll b) { return a<b?b:a; }
int main()
{
// freopen("c3.in","r",stdin);
// freopen("o","w",stdout);
T=R();
while(T--)
{
n=R();m=R();
build(1,1,n);
for(int i=1;i<=n;i++)
{
a[i]=R();
}
for(int i=1;i<=m;i++)
{
q[i].l=R();
q[i].r=R();
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=32;j++)
{
if(a[i]&(1<<j)) pre[i][j]=pre[i-1][j];
else pre[i][j]=i;
}
}
int pos=1;
for(int i=1;i<=m;i++)
{
while(pos<=q[i].r)
{
ll val=a[pos];
ll tmp=pos;
while(tmp>=1)
{
ll d=sqrt(val);
ll nt=0;
for(int j=1;j<=32;j++)
{
if(pre[tmp][j]!=tmp&&(val&(1<<j)))nt=chkmax(nt,pre[tmp][j]);
}
if(d*d==val) {add(1,nt+1,tmp);}
tmp=nt;
val=val&a[nt];
}
pos++;
}
ans[q[i].id]=get(1,q[i].l,q[i].r);
}
for(int i=1;i<=m;i++)
printf("%lld
",ans[i]);
}
}