最慢 1.17s 求卡常 /fn

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second 
#define deb(var) cerr << #var << '=' << var << "; "
#define int unsigned
namespace input {
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    bool IOerror = 0;
    inline char nc() {
        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
        if (p1 == pend) {
            p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
            if (pend == p1) {
				IOerror = 1;
				return -1;
			}
        }
        return *p1++;
    }
    inline void read(char &ch) {
        ch = nc();
        while(ch==' '||ch=='\n'||ch=='\r'||ch=='\t') ch = nc();
    }
    inline void read(int &x) {
        char ch = nc();
		x = 0;
		int f = 1;
        for (;ch==' '||ch=='\n'||ch=='\r'||ch=='\t'; ch = nc());
        if (IOerror) return;
        if(ch == '-') f = -1, ch = nc();
        for (; ch >= '0' && ch <= '9'; ch = nc()) {
			x = x * 10 + ch - '0';
		}
		x*=f;
    }
    #undef OUT_SIZE
    #undef BUF_SIZE
};
namespace output {
	#define OutputBufferSize 1000000
    char buffer[OutputBufferSize];
    char *s = buffer;
    inline void flush() {
        assert(stdout != NULL);
        fwrite(buffer, 1, s - buffer, stdout);
        s = buffer;
        fflush(stdout);
    }
    inline void print(char* str) {
    	if(s-buffer>OutputBufferSize-2-strlen(str)) flush();
        while (*str != 0) *s++=(char(*str++));
    }
    inline void print(int x) {
        char buf[25] = {0}, *p = buf;
        if(s-buffer>OutputBufferSize-12) flush();
        if(x<0){
        	x=-x;
        	*s++=('-');
		}
        if(!x) *s++=('0');
        while(x){
			*(++p)=x%10;
			x/=10;
		}
        while(p != buf) *s++=char(*(p--)+'0');
        *s++='\n';
    }
	#undef OutputBufferSize
} // from sunset1028
using namespace input;
using namespace output;
#define s sum
int n, m, a[1000010], b[1000010], c[1000010], s[1000010], now, tim[1000010], lst[1000010], ans[5000010], tmp;
inline int get(const int &p) {
	return s[p] + (now - tim[p]) * lst[p];
}
int head[1000010];
pii val[5000010]; int tot, nxt[5000010];
int gcd(int x, int y) {
    while (y) {
        int t = y; y = x % y; x = t;
    }
    return x;
}
signed main() {
	read(n), read(m);
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 1; i <= n; i++) read(b[i]);
	for (int i = 1; i <= n; i++) read(c[i]);
	for (int i = 1; i <= m; i++) {
		int l = 0, r = 0;
		read(l), read(r);
		++tot;
		val[tot] = mp(l, i);
		nxt[tot] = head[r]; head[r] = tot; 
	}
	for (int i = 1; i <= n; i++) {
		s[i] = get(i - 1);
		now = i;
		int t = i - 1, ad = a[i], od = b[i], gc = c[i];
		while (t) {
			ad &= a[t];
			od |= b[t];
			gc = gcd(gc, c[t]);
			if (ad == a[t] && od == b[t] && gc == c[t]) break;
			a[t] = ad, b[t] = od, c[t] = gc; t--;
		}
		for (int k = t + 1; k <= i; k++) {
			s[k] = get(k) - lst[k];
			lst[k] = a[k] * b[k] * c[k] + lst[k - 1]; tim[k] = i - 1;
		}
		for (int j = head[i]; j; j = nxt[j]) ans[val[j].se] = get(i) - get(val[j].fi - 1);
	}
	for (int i = 1; i <= m; i++) print(ans[i]); flush();
	return 0;
}