luogu P6477 [NOI Online 2 提高组]子序列问题sequence

· · 个人记录

题面传送门 考虑像HH的项链那道题一样维护最后一个位置。 如果在第j个点设f_i为当前i到j的答案，那么如果没有平方，显然可以对于每一个最后一个点last，将1到last都加上1。查询时区间查询即可。 可现在是平方和，我们知道(x+y)^2=x^2+2xy+y^2那么直接维护两个，一个是区间加，一个是区间平方和，更新时用区间加更新区间平方和即可。 代码实现:

#include<cstdio>
#include<algorithm>
#define mod 1000000007
using namespace std;
long long n,m,k,f[4000039],s[4000039],sum[4000039],a[1000039],last[1000039],x,y,z,ans,tot,pus,now[1000039],nows[1000039];
inline void read(register long long &x){
    register char s=getchar();x=0;
    while(s<'0'||s>'9') s=getchar();
    while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^48),s=getchar();
}
inline void push(register int l,register int r,register int now){
    register int m=(l+r)>>1;
    f[now<<1]+=f[now];f[now<<1|1]+=f[now];
    sum[now<<1]=s[now<<1]*f[now]*2+f[now]*f[now]*(m-l+1)+sum[now<<1];
    sum[now<<1|1]=s[now<<1|1]*f[now]*2+f[now]*f[now]*(r-m)+sum[now<<1|1];
    s[now<<1]=(m-l+1)*f[now]+s[now<<1];
    s[now<<1|1]=(r-m)*f[now]+s[now<<1|1];
    f[now]=0;
}
inline void get(register int l,register int r,register int now){
    if(x<=l&&r<=y){f[now]++,sum[now]=s[now]*2+(r-l+1)+sum[now],s[now]=s[now]+r-l+1;return;}
    if(f[now])push(l,r,now);
    register int m=(l+r)>>1;
    if(x<=m) get(l,m,now<<1);
    if(y>m) get(m+1,r,now<<1|1);
    sum[now]=sum[now<<1]+sum[now<<1|1];
    s[now]=s[now<<1]+s[now<<1|1];
}
inline long long find(register int l,register int r,register int now){
    if(x<=l&&r<=y) return sum[now];
    if(f[now])push(l,r,now);
    register int m=(l+r)>>1;
    register long long fs=0;
    if(x<=m) fs+=find(l,m,now<<1);
    if(y>m) fs+=find(m+1,r,now<<1|1);
    return fs;
}
int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    register int i,l,r,mid;
    read(n);
    for(i=1;i<=n;i++)read(a[i]),now[i]=a[i];
    sort(now+1,now+n+1);
    for(i=1;i<=n;i++){
        nows[i]=nows[i-1];
        if(now[i]!=now[i-1]) nows[i]++;
    }
    for(i=1;i<=n;i++){
        l=0;r=n+1;
        while(l+1<r){
            mid=(l+r)>>1;
            if(now[mid]<a[i]) l=mid;
            else r=mid;
        }
        a[i]=nows[r];
        x=last[a[i]]+1,y=i,z=1,get(1,n,1),last[a[i]]=i;
        x=1;y=i;
        ans=(ans+find(1,n,1))%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

这道题的极限答案只有10^{18}，但longlong可以达到9\times10^{18}的范围，所以不用在中间取模，珂以减小常数。