[Luogu 3794]签到题IV

Description

题库链接

给定长度为 (n) 的序列 (A)。求有多少子段 ([l,r]) 满足

[ left(gcd_{lleq ileq r}A_i ight) oplusleft(igcup_{lleq ileq r}A_i ight)=k ]

其中 (oplus) 表示按位异或，(cup) 表示按位或。

(1leq n,A_ileq 500000)

Solution

这道题和[JSOI 2015]最大公约数一样啊。

可知，一个确定的右端点，其左端点随便取，(gcd) 和按位或是不超过 (log) 种的。

直接存下不同的值及其对应的最左端点。总复杂度为 (O(nlog^2 A_i))。

Code

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
using namespace std;
const int N = 500000+5;

int n, K, a[N];
vector<pii > g[N], o[N];
pii tg, to;
ll ans;

int gcd(int a, int b) {return b ? gcd(b, a%b) : a; }
int main() {
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        int szg = g[i-1].size(), szo = o[i-1].size(), j = 0, k = 0, cg = 0, co = 0;
        g[i-1].pb(pii(0, i)), o[i-1].pb(pii(0, i));
        while (j < szg && k < szo) {
            tg = g[i-1][j], to = o[i-1][k];
            tg.fr = gcd(a[i], tg.fr);
            to.fr = (a[i]|to.fr);
            if ((tg.fr^to.fr) == K) ans += min(g[i-1][j+1].sc, o[i-1][k+1].sc)-max(tg.sc, to.sc);
            if (cg == 0 || tg.fr != g[i][cg-1].fr) g[i].pb(tg), ++cg;
            if (co == 0 || to.fr != o[i][co-1].fr) o[i].pb(to), ++co;
            if (g[i-1][j+1].sc == o[i-1][k+1].sc) ++j, ++k;
            else if (g[i-1][j+1].sc < o[i-1][k+1].sc) ++j;
            else ++k;
        }
        tg = pii(a[i], i), to = pii(a[i], i);
        if ((tg.fr^to.fr) == K) ans++;
        if (cg == 0 || tg.fr != g[i][cg-1].fr) g[i].pb(tg), ++cg;
        if (co == 0 || to.fr != o[i][co-1].fr) o[i].pb(to), ++co;
    }
    printf("%lld
", ans);
    return 0;
}