好题，吹爆 JRKSJ！
考虑朴素的 \(O(n \log V)\) 做法。枚举第 \(i\) 位，需要计算所有极长连续的全 \(0\) 区间长度，答案为 \(\sum\limits_{i=0}^{63} 2^i \times (\frac{n(n+1)}{2} - \sum\frac{len(len+1)}{2})\)。
然而这样不能通过。考虑分块，每 \(B\) 个元素为一块。
- 块内的子区间暴力枚举即可。这部分复杂度是 \(O(nB)\)。
- 算块间的贡献，考虑算出当前块第 \(i\) 位第一次出现的位置 \(f_i\) 和最后一次出现的位置 \(g_i\)。再维护一个 \(lst_i\) 表示前面的块第 \(i\) 位最后一次出现的位置。考虑计算块内的前缀或序列 \(s_i\)，那么 \(s_i \oplus s_{i-1}\) 就是 \(a_i\) 在块中第一次出现的位。这部分的时间复杂度为 \(O(\frac{2n \log V}{B})\)。
- 算出来 \(f_i\) 和 \(g_i\)，考虑计算块间的贡献。枚举第 \(i\) 位，沿用暴力方法，右端点在当前块的全 \(0\) 区间数量为 \((f_i - l) \times (l - lst_i - 1)\)。若当前块的所有元素的第 \(i\) 位都是 \(0\)，数量就是 \((r - l + 1) \times (l - lst_i - 1)\)。每次用 \(g_i\) 更新 \(lst_i\) 即可。这部分的时间复杂度为 \(O(\frac{n \log V}{B})\)
总时间复杂度为 \(O(nB + \frac{3n \log V}{B})\)，实测 \(B = 17\) 最优。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
namespace READ
{
ull Read()
{
char ch=getchar();
ull s=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s;
}
ull tp[10005];
int l,r;
ull g1,g2;
void init(int &n)
{
int i,k;
n=Read(),k=Read(),l=1;
for(i=1;i<=k;i++)
tp[i]=Read();
}
ull read()
{
if(l>r)
l=Read(),r=Read(),g1=Read(),g2=Read();
return tp[l++]*g1+g2;
}
}
const int B = 17;
int n, f[64], g[64], lst[64];
ull a[64], b[64], c[64], ans, sum;
void solve() {
READ::init(n);
for (int l = 1; l <= n; l += B) {
int r = min(l + B - 1, n), len = r - l + 1;
sum += 1ULL * len * (len + 1) / 2;
for (int i = l; i <= r; ++i) {
a[i - l + 1] = READ::read();
}
for (int i = 1; i <= len; ++i) {
ull s = 0;
for (int j = i; j <= len; ++j) {
s |= a[j];
ans += s;
}
}
mems(f, 0);
mems(g, 0);
b[0] = 0;
for (int i = 1; i <= len; ++i) {
b[i] = (b[i - 1] | a[i]);
}
for (int i = 1; i <= len; ++i) {
ull val = (b[i] ^ b[i - 1]);
while (val) {
f[__builtin_ctzll(val)] = i + l - 1;
val ^= (val & (-val));
}
}
b[len + 1] = 0;
for (int i = len; i; --i) {
b[i] = (b[i + 1] | a[i]);
}
for (int i = 1; i <= len; ++i) {
ull val = (b[i] ^ b[i + 1]);
while (val) {
g[__builtin_ctzll(val)] = i + l - 1;
val ^= (val & (-val));
}
}
for (int i = 0; i < 64; ++i) {
if (f[i]) {
c[i] += 1ULL * (f[i] - l) * (l - lst[i] - 1);
lst[i] = g[i];
} else {
c[i] += 1ULL * (r - l + 1) * (l - lst[i] - 1);
}
}
}
for (int i = 0; i < 64; ++i) {
ans += (1ULL << i) * (1ULL * n * (n + 1) / 2 - sum - c[i]);
}
printf("%llu", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}