【NOIP校内模拟】T2 字胡串(分治)

【NOIP校内模拟】T2 字胡串(分治)

%%%%%%%%%%%lst神仙 这是他的做法 吊了标算

对于这种有多少区间满足要求的 我们套路的用分治做 每次都统计左端点在左半边 右端点在右半边的个数

设f(i) 表示当前点到中间分割点的最大值,g(i)表示当前点到中间分割点的或和

我们发现 g(i)≥f(i) 所以只需找到g[i]=f[i]的区间就好

然后f肯定是单调递增的

所以可以维护双指针

边界条件很坏坏 膜lst神仙啊

#include<bits/stdc++.h>
#define N 1000005
#define int long long
using namespace std;
template<class T>
inline void read(T &x)
{
    x=0; int f=1;
    static char ch=getchar();
    while((!isdigit(ch))&&ch!='-')  ch=getchar();
    if(ch=='-') f=-1;
    while(isdigit(ch))  x=x*10+ch-'0',ch=getchar();
    x*=f;
}
int n,s[N],f[N],g[N],ans;
inline void solve(int l,int r)
{
    if(l>=r)    return;
    int mid=(l+r)>>1;
    f[mid]=s[mid],f[mid+1]=s[mid+1];
    for(int i=mid-1;i>=l;i--)   f[i]=max(s[i],f[i+1]);
    for(int i=mid+2;i<=r;i++)   f[i]=max(s[i],f[i-1]);
    g[mid]=s[mid],g[mid+1]=s[mid+1];
    for(int i=mid-1;i>=l;i--)   g[i]=s[i]|g[i+1];
    for(int i=mid+2;i<=r;i++)   g[i]=s[i]|g[i-1];
    int pos=mid;
    for(int i=mid;i>=l;i--) //左端点 
    {
        if(f[i]==g[i])
        {
            while(pos<r&&((g[pos+1]|g[i])==g[i])&&f[pos+1]<=f[i])   pos++;  //1.没越界 2.是子集 3.最大值在左边 
            ans-=pos-mid;
        }
    } 
    pos=mid+1;
    for(int i=mid+1;i<=r;i++)
    {
        if(f[i]==g[i])
        {
            while(pos>l&&((g[pos-1]|g[i])==g[i])&&f[pos-1]<f[i])    pos--;
            ans-=mid-pos+1;
        }
    } 
    solve(l,mid);
    solve(mid+1,r);
}
main()
{
    read(n);
    for(int i=1;i<=n;i++)   read(s[i]);
    ans=n*(n-1)/2;
    solve(1,n);
    cout<<ans;
    return 0;
}

转载于:https://www.cnblogs.com/Patrickpwq/articles/9877788.html