【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