记录编号	616224	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3986.水母序列	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	7.270 s
提交时间	2026-06-02 19:31:15	内存使用	37.30 MiB

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>
 
using namespace std;
 
const int N = 100010;
const int M = 1000010;
const int Bit = 20;
const int Maxn = (1 << 20) + 10;
 
class fastIn {
	private:
	
	char buf [1 << 20];
	char *p1 = buf;
	char *p2 = buf;
	
	inline char getch ();
	
	public:
	
	template <typename NumT>
	void read (NumT &num);
	
	template <typename NumT>
	fastIn& operator >> (NumT &num);
};
 
inline char fastIn::getch () {
	if (p1 == p2) {
		p1 = buf;
		p2 = buf + fread (buf, 1, 1 << 20, stdin);
		if (p1 == p2) {
			return EOF;
		}
	}
	return *p1++;
}
 
template <typename NumT>
void fastIn::read (NumT &num) {
	char ch = getch ();
	NumT op = 1;
	num = 0;
	
	while (ch < '0' || '9' < ch) {
		op = ((ch == '-') ? -1 : 1);
		ch = getch ();
	}
	while ('0' <= ch && ch <= '9') {
		num *= 10;
		num += (ch - '0');
		ch = getch ();
	}
	
	num *= op;
}
 
template <typename NumT>
fastIn& fastIn::operator >> (NumT &num) {
	read (num);
	return *this;
}
 
fastIn fin;

namespace Fenwick_Tree {
	inline int lowbit (int id) {
		return (id) & (-id);
	}
	
	void update (int id, long long num, long long tree[N]) {
		for (; id < N; id += lowbit (id)) {
			tree[id] += num;
		}
	}
	
	long long query (int id, long long tree[N]) {
		long long res = 0;
		for (; id > 0; id -= lowbit (id)) {
			res += tree[id];
		}
		return res;
	}
}

namespace Segment_Tree_Based_On_Fenwick_Tree {
	long long diff[N];
	long long multi_diff[N];
	
	void range_update (int l, int r, long long num) {
		using Fenwick_Tree::update;
		
		update (l, num, diff);
		update (r + 1, -num, diff);
		update (l, num * (l - 1), multi_diff);
		update (r + 1, -num * r, multi_diff);
	}
	
	long long single_query (int id) {
		using Fenwick_Tree::query;
		
		long long res1 = query (id, diff) * id;
		long long res2 = query (id, multi_diff);
		return res1 - res2;
	}
	
	long long range_query (int l, int r) {
		return single_query (r) - single_query (l - 1);
	}
}
 
bool flag[Maxn];
 
int n;
int m;
int nums[N];
pair<int, int> appear[N][Bit + 10];
pair<pair<int, int>, int> ques[M];
long long ress[M];
 
bool cmp (pair<pair<int, int>, int> one, pair<pair<int, int>, int> two) {
	return one.first.first < two.first.first;
}
 
int main () {
    
    freopen ("Jelly.in", "r", stdin);
    freopen ("Jelly.out", "w", stdout);
    
    flag[0] = flag[1] = true;
    for (int i = 2; i < Maxn; i++) {
        if (!flag[i]) {
            for (int j = i + i; j < Maxn; j += i) {
                flag[j] = true;
            }
        }
    }
    
	fin >> n >> m;
    for (int i = 1; i <= n; i++) {
		fin >> nums[i];
    }
 
    for (int i = 0; i < Bit; i++) {
        appear[n + 1][i] = {n + 1, i};
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < Bit; j++) {
            if ((1 << j) & nums[i]) {
                appear[i][j] = {i, j};
            }
            else {
                appear[i][j] = appear[i + 1][j];
            }
        }
    }
 
    for (int i = 1; i <= m; i++) {
        int l, r;
		fin >> ques[i].first.first >> ques[i].first.second;
		ques[i].second = i;
    }
    sort (ques + 1, ques + 1 + m, cmp);
 
    int lastl = n + 1;
    using namespace Segment_Tree_Based_On_Fenwick_Tree;
    for (int index = m; index >= 1; index--) {
        auto [l, r] = ques[index].first;
        auto id = ques[index].second;
 
        for (int i = lastl - 1; i >= l; i--) {
            sort (appear[i], appear[i] + Bit);
            int now = 0;
            appear[i][Bit].first = n + 1;
            for (int j = 0; j < Bit; j++) {
                if (appear[i][j].first == n + 1) {
                    break;
                }
                now |= (1 << appear[i][j].second);
                if (appear[i][j].first != appear[i][j + 1].first) {
                    range_update(appear[i][j].first, appear[i][j + 1].first - 1, !flag[now]);
                }
            }
        }
 
        long long res = range_query(l, r);
        ress[id] = res;
        lastl = l;
    }
 
    for (int i = 1; i <= m; i++) {
        printf ("%lld\n", ress[i]);
    }
 
    return 0;
}