codeforces 1030E Vasya and Good Sequences

题解

很容易观察到的两点是，$a_i$有用的只有二进制表示下的1的个数，那么既然只有个数有用，如果某个区间的1的个数的和是偶数的话，会有很大可能是好序列，在验证过程中可以发现，1 1 4这种序列是不可以的，因为4*2>6，简单的说，序列总和必须要至少为其中最大的数的两倍，那么就转化为新的问题：

求一个序列中有多少连续子序列的和是偶数，并且和不小于最大值的两倍

（我的做法可能有点复杂，细节很多）
第二个限制非常难搞，但是我们注意到，新的序列$b_i$中，最大值大约是60多。可不可以枚举最大值？可不可以把区间按最大值分类？假设枚举出一个最大值M，序列（指新序列，下同）中某些位置是等于M的，我们要考虑的是跨越了至少一个这些位置，并且没有包含比M大的数的区间。假设b[cur]=M,枚举i>=cur作为区间右端点，（因为最多枚举60次最大值，所以这部分枚举的复杂度是O(60n)，是可以接受的）我们要快速找有多少个合法左端点。
考虑怎么搞掉限制2就好了，如果右端点是$j$左端点是$i$，那么是要求$Su{m}_b(j)?Su{m}_b(i?1)>=M?2$（ * ）。我们注意到题中的$a_i>=1$也就是说$b_i>=1$加上M最大为60，这意味着，我最多从j暴力往前找60*2=120个位置，（ * ）式必然能够被满足，然后就只需要考虑在此位置之前$Su{m}_b(i)$有多少个和$Su{m}_b(j)$奇偶性一样的就可以了。

这是大体框架，其次还需要注意不能包含比M大的数值，需要在细节上加一些处理。

代码

//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define out(i,u) for(int i=first[u];i!=-1;i=next[i])
#define repvc(i,vc) for(int i=0,Sz=vc.size();i<Sz;++i)
typedef long long ll;
inline ll read()
{
    char ch=getchar();ll ret=0,f=1;while(ch<'0' || ch>'9') {
    if(ch=='-')f=-1;ch=getchar();}for(;ch>='0' && ch<='9';ch=getchar()) ret=ret*10+ch-'0';return ret*f;
}
using namespace std;const int INF=1<<30;const int maxn=300000+10;int a[maxn],sum[maxn],ji[maxn],ou[maxn],t[maxn];inline int cal(ll x)
{
    int ret=0;for(;x;x>>=1) ret+=x&1ll;return ret;	
}inline int check(int x){
    return !(x&1);}
inline int s_ji(int l,int r){
    return ji[r]-(l==0?0:ji[l-1]);}
inline int s_ou(int l,int r){
    return ou[r]-(l==0?0:ou[l-1]);}int main()
{
    int n;cin>>n;ou[0]=1;rep(i,1,n) {
    a[i]=cal(read()),sum[i]=sum[i-1]+a[i];ji[i]=(sum[i]&1)+ji[i-1];ou[i]=!(sum[i]&1)+ou[i-1];t[i]=a[i];}sort(t+1,t+n+1);long long ans=0;int k=unique(t+1,t+n+1)-t-1;rep(o,1,k){
    int M=t[o],cur=1,pre=0;while(a[cur]!=M) {
    if(a[cur]>M) pre=cur;++cur;}while(cur<=n){
    while(cur<=n&&a[cur]!=M) {
    if(a[cur]>M) pre=cur;++cur;}int j;for(j=cur;(a[j]<M ||j==cur)&& j<=n;++j){
    int pos=cur-1;while(pos>=pre && sum[j]-sum[pos]<M*2) --pos;if(pos<pre) continue;if(sum[j]&1) ans+=s_ji(pre,pos);else ans+=s_ou(pre,pos);}cur=j;}}cout<<ans<<endl;return 0;
}