记录编号	588877	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	水母序列	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	4.865 s
提交时间	2024-07-01 19:28:45	内存使用	21.51 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
const int N=1e5+5;
const int M=1e6+5;
const int V=(1<<20)+5;
bool v[V];int pri[N],cnt=0;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c <= '9' && c >= '0';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}

void prework(){
	v[0] = v[1] = 1;
	for (int i = 2;i <= V-5;i++){
		if (!v[i])pri[++cnt]=i;
		for (int j = 1;j <= cnt && i*pri[j] <= V-5;j++){
			v[i * pri[j]]=1;
			if (!(i % pri[j]))break;
		}
	}return ;
}
int n,m;
int a[N];
struct node{
    int l,id;
};vector<node>q[N];
ll ans[M];
struct BIT{
    ll c[N];
    int lowbit(int x){return x & (-x);}
    void add(int x,int w){
        for(;x <= n;x += lowbit(x))c[x] += w;
        return ;
    }
    void change(int l,int r,int w){
        add(l,w),add(r+1,-w);return ;
    }
    ll ask(int x){
        ll ans = 0;for(;x > 0;x -= lowbit(x))ans += c[x];
        return ans;
    }
    
}t1,t2,t3;
node st[N];int top=0;
node tmp[N];
void solve(){
	prework();
    n = read(),m = read();
	for(int i = 1;i <= n;i++)a[i] = read();
	for(int i = 1;i <= m;i++){
	    int l = read(),r = read();
	    q[r].push_back({l,i});
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= top;j++)st[j].l |= a[i];
        st[++top] = {a[i],i};int cnt = 0;
        for(int j = 1;j <= top;j++)if(j == top || st[j].l != st[j+1].l)tmp[++cnt] = st[j];
        for(int j = 1;j <= cnt;j++)st[j] = tmp[j];
        top = cnt;
        
        for(int j = 1;j <= top;j++){
            if(v[st[j].l])continue;
            int l = st[j-1].id+1,r = st[j].id;
            if(l > 1)t1.change(1,l-1,r-l+1);
            t2.change(l,r,r+1);
            t3.change(l,r,1);
        }
        for(auto u:q[i]){
            ans[u.id] += t2.ask(u.l) + t1.ask(u.l) - t3.ask(u.l) * u.l;
        }
    }
}
int main(){
	freopen ("Jelly.in","r",stdin);
	freopen ("Jelly.out","w",stdout);
    solve();
    for (int i = 1;i <= m;i++)printf("%lld\n",ans[i]);
    return 0;
}