题意：定义一个序列是好的当且仅当它所有的元素按位与的值是完全平方数。给出一个长度为$n$的序列，多组询问区间$[l,r]$中有多少个连续的子序列是好的序列
------------
首先，对一个元素进行按位与操作，这个值一定是单调不增的
所以按位与之后的值最多有$log_2n$个
对于这个序列来说，按位与之后的值最多有$nlog_2n$个
设$nxt[i][j]$表示第$i$个数之后，第一个二进制第$j$位为$0$的数的位置
将询问离线，按照左端点第一关键字，右端点第二关键字从大到小排序
记录从$l$到当前$pos$的按位与结果$now$，找到下一个会对$now$产生影响的位置$nxtp$
如果$now$是完全平方数，就将区间$[pos,nxtp-1]$加上$1$
这个询问的答案就是$[l,r]$的区间和
```
#include<cstdio>
#include<cstring>
#include<cctype>
#include<map>
#include<algorithm>
#define reg register
#define reset(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int N=5e5+5;
struct node
{
int l,r,id;
inline friend bool operator < (node a,node b) {return a.l==b.l?a.r>b.r:a.l>b.l;}
}q[N<<1];
int n,m,a[N],nxt[N][31];
ll c1[N],c2[N],ans[N<<1];
map<int,bool>issqr;
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int k){for (reg int i=x;i<=n;i+=lowbit(i)) c1[i]+=k,c2[i]+=(ll)x*k;}
inline ll query(int x,ll res=0){for (reg int i=x;i;i-=lowbit(i)) res+=(ll)(x+1)*c1[i]-c2[i]; return res;}
inline void work()
{
n=read(),m=read();
for (reg int i=1;i<=n;a[i++]=read());
for (reg int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+m+1); reset(c1); reset(c2);
for (reg int i=0;i<=30;i++) nxt[n][i]=n+1;
for (reg int i=n-1;i;i--)
for (reg int j=0;j<=30;j++)
nxt[i][j]=(a[i+1]&(1<<j)?nxt[i+1][j]:i+1);
for (reg int i=1,pos=n;i<=m;i++)
{
while (q[i].l<=pos)
{
int r=pos,now=a[pos];
while (r<=n)
{
int nxtp=n+1;
for (reg int j=0;j<=30;j++)
if (now&(1<<j)) nxtp=min(nxtp,nxt[pos][j]);
if (issqr[now]) add(r,1),add(nxtp,-1);
now&=a[nxtp]; r=nxtp;
}
--pos;
}
ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
}
for (reg int i=1;i<=m;i++) printf("%lld\n",ans[i]);
}
int main()
{
//freopen("c2.in","r",stdin);
//freopen("c.out","w",stdout);
for (reg int i=0;1ll*i*i<=(1ll<<31)-1;i++) issqr[i*i]=1;
for (reg int T=read();T;T--) work();
return 0;
}
```