P2757 [国家集训队]等差子序列

2018-09-18 16:36:09

~~如果你常数够小的话可以得到 $50$ 或 $55$ ~~

$01$ 串长这样： ${110101}$

$CF452F$ 也是这个题，不过数据范围 $3e5$ 嘿嘿嘿

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef unsigned long long ll;
const int N=1e4+5,base=127;
int n,a[N];
ll pw[N],hs1[N<<2],hs2[N<<2];
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline void pushup(int now,int l,int r)
{
hs1[now]=(hs1[now<<1]*pw[r]+hs1[now<<1|1]);
hs2[now]=(hs2[now<<1]+hs2[now<<1|1]*pw[l]);
}
void update(int l,int r,int now,int x)
{
if (l==r){hs1[now]=hs2[now]=1; return;}
int mid=(l+r)>>1;
if (x<=mid) update(l,mid,now<<1,x);
else update(mid+1,r,now<<1|1,x);
pushup(now,mid-l+1,r-mid);
}
ll query1(int L,int R,int l,int r,int now)
{
if (l>R||r<L) return 0;
if (l>=L&&r<=R) return hs1[now];
int mid=(l+r)>>1;
if (mid>=R) return query1(L,R,l,mid,now<<1);
if (mid<L) return query1(L,R,mid+1,r,now<<1|1);
return (query1(L,mid,l,mid,now<<1)*pw[R-mid]+query1(mid+1,R,mid+1,r,now<<1|1));
}
ll query2(int L,int R,int l,int r,int now)
{
if (l>R||r<L) return 0;
if (l>=L&&r<=R) return hs2[now];
int mid=(l+r)>>1;
if (mid>=R) return query2(L,R,l,mid,now<<1);
if (mid<L) return query2(L,R,mid+1,r,now<<1|1);
return (query2(L,mid,l,mid,now<<1)+query2(mid+1,R,mid+1,r,now<<1|1)*pw[mid-L+1]);
}
int main()
{
pw[0]=1;
for (reg int i=1;i<=10000;i++) pw[i]=pw[i-1]*base;
{
memset(hs1,0,sizeof(hs1));
memset(hs2,0,sizeof(hs2));
}