[题解] P3794 签到题IV

· · 题解

\color{red}博客内食用效果更佳（点我）

思路：二分+ST 表

复杂度：O(n\log^3{n})

主体思路

首先考虑暴力做法，枚举左右端点，暴力算区间 \gcd，区间或，复杂度感人。区间 \gcd 与区间或显著可以用线段树或者 ST 表维护，因为本题无修改，我们可以采用 ST 表进行更优的处理，复杂度来到 O(n^2\log(n))。

注意到一个常见的性质，连续段的 \gcd 和或运算的种类在 \log 级别上。换句话说，对于一个点，向左或向右扩展 \gcd 和或运算最多会有 \log 级别个不同结果。考虑枚举右端点，每次用二分向左扩展左端点，尝试找到第一个与当前段结果（或运算和 \gcd 运算均要做一遍）不同的位置，然后我们得到了 \log 级别个的左端点，遍历一遍累加答案即可。

因为 \gcd 运算是 \log 级别的，所以总复杂度为 O(n\log^3{n})。

代码实现需要注意的地方：

参考代码：

代码中以字母 g 结尾的变量、函数为 \gcd 运算相关，以 o 结尾的为或运算相关。
详见注释。

#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
//IO
inline int rd()
{
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
//--------------------//
const int N=5e5+5,LG=30;

int n,k;
int a[N];

struct ST
{
    int lg[N];
    int stg[N][LG],sto[N][LG];

    void init()
    {
        for(int i=2;i<=n;i++)
            lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;i++)
            stg[i][0]=sto[i][0]=a[i];
        for(int j=1;j<=lg[n];j++)
        {
            for(int i=1;lg[n-i+1]>=j;i++)
            {
                stg[i][j]=__gcd(stg[i][j-1],stg[i+(1<<(j-1))][j-1]);
                sto[i][j]=sto[i][j-1]|sto[i+(1<<(j-1))][j-1];
            }
        }
        return;
    }

    int qg(int l,int r)
    {
        int lgl=lg[r-l+1];
        return __gcd(stg[l][lgl],stg[r-(1<<lgl)+1][lgl]);
    }
    int qo(int l,int r)
    {
        int lgl=lg[r-l+1];
        return sto[l][lgl]|sto[r-(1<<lgl)+1][lgl];
    }
}S;//ST 表部分

int findg(int l,int r,int pos)//二分部分
{
    int res=0,val=S.qg(r,pos);
    while(l<=r)
    {
        int mid=l+r>>1;
        if(S.qg(mid,pos)==val)
            r=mid-1;
        else
            res=mid,l=mid+1;
    }
    return res;
}
int findo(int l,int r,int pos)
{
    int res=0,val=S.qo(r,pos);
    while(l<=r)
    {
        int mid=l+r>>1;
        if(S.qo(mid,pos)==val)
            r=mid-1;
        else
            res=mid,l=mid+1;
    }
    return res;
}
int tcnt,tem[N];
LL ans;
void work()
{
    for(int tp,i=1;i<=n;i++)
    {
        tem[tcnt=1]=tp=i;//对于右端点我们需要存为第一个左端点
        while(true)
        {
            tp=findg(1,tp,i);
            tem[++tcnt]=tp;
            if(tp==0)
                break;
        }
        tp=i;
        while(true)
        {
            tp=findo(1,tp,i);
            tem[++tcnt]=tp;
            if(tp==0)
                break;
        }
        sort(tem+1,tem+tcnt+1);
        tcnt=unique(tem+1,tem+tcnt+1)-tem-1;
        for(int x,xg,xo,j=tcnt;j>1;j--)
        {
            x=tem[j],xg=S.qg(x,i),xo=S.qo(x,i);
            if((xo^xg)==k)
                ans+=tem[j]-tem[j-1];//这一段长度是这一段的贡献
        }
    }
}
//--------------------//
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    S.init();
    work();
    printf("%lld",ans);
    return 0;
}