1 条题解

  • 0
    @ 2022-1-29 11:46:11

    part1 暴力

    这题可以直接暴力过。

    先排序，每次扫一遍，如果在区间中就加上答案，具体不再赘述。

    part2 正解

    考虑没有修改操作，那么直接用莫队，这样就只需要考虑加一个或者删掉一个数就好了。

    考虑新加入一个数会让后面的数都向后平移，即 ax×fibya_x\times fib_y 变成了 ax×fiby+1a_x\times fib_{y+1}。

    那么这个变化就相当于乘上了一个 fib 的矩阵。

    那么这个东西就可以直接用线段树维护了。


    代码 
    #include<bits/stdc++.h>
#define seg int p,int l,int r
#define mid (l+r>>1)
#define lid p<<1,l,mid
#define rid p<<1|1,mid+1,r
using namespace std;
const int N=3e4+5;
struct mat{int cnt[2][2];}Fib,InvFib;
struct segtree{int laz;mat Cnt,la;}tr[N<<2];
int mod;
mat cnt[N];
void clear(mat &a){
    a.cnt[0][0]=a.cnt[1][1]=1;
    a.cnt[1][0]=a.cnt[0][1]=0;
}
mat operator*(const mat &a,const mat &b){//矩阵乘
    mat ans;
    memset(ans.cnt,0,sizeof(ans.cnt));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++){
            long long S=0;
            for(int k=0;k<2;k++)S=S+a.cnt[i][k]*b.cnt[k][j];
            ans.cnt[i][j]=S%mod;
        }
            
    return ans;
}
mat operator+(const mat &a,const mat &b){
    mat ans;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)ans.cnt[i][j]=(a.cnt[i][j]+b.cnt[i][j])%mod;
    return ans;
}
mat operator*(int a,mat b){
    mat ans;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)ans.cnt[i][j]=a*b.cnt[i][j]%mod;
    return ans;
}
void pd(seg){
    if(l==r)return;
    if(l==mid)cnt[l]=cnt[l]*tr[p].la;
    if(r==mid+1)cnt[r]=cnt[r]*tr[p].la;
    tr[p<<1].Cnt=tr[p<<1].Cnt*tr[p].la;
    tr[p<<1|1].Cnt=tr[p<<1|1].Cnt*tr[p].la;
    tr[p<<1].la=tr[p<<1].la*tr[p].la;
    tr[p<<1|1].la=tr[p<<1|1].la*tr[p].la;
    tr[p<<1].laz=tr[p<<1|1].laz=1;
    clear(tr[p].la);
    tr[p].laz=0;
}
void change(seg,int x,int z){
    if(l==r){
        tr[p].Cnt=z*cnt[l];
        return;
    }
    if(tr[p].laz)pd(p,l,r);
    if(x<=mid)change(lid,x,z);
    else change(rid,x,z);
    tr[p].Cnt=tr[p<<1].Cnt+tr[p<<1|1].Cnt;
}
void add(seg,int L,int R,int z){
    if(l>=L&&r<=R){
        if(l!=r)tr[p].la=tr[p].la*(z==1?Fib:InvFib);
        tr[p].laz=1;
        if(l==r)cnt[l]=cnt[l]*(z==1?Fib:InvFib);
        tr[p].Cnt=tr[p].Cnt*(z==1?Fib:InvFib);
        return;
    }
    if(tr[p].laz)pd(p,l,r);
    if(L<=mid)add(lid,L,R,z);
    if(R>mid)add(rid,L,R,z);
    tr[p].Cnt=tr[p<<1].Cnt+tr[p<<1|1].Cnt;
}
int s[N],rk[N],n,a[N],b[N],id[N],Q,ans[N];
struct que{int l,r,id;}q[N];
void add(int x){
    s[rk[x]]++;
    if(s[rk[x]]==1){
        add(1,1,n,rk[x],n,1);
        change(1,1,n,rk[x],a[x]);
    }
}
void del(int x){
    s[rk[x]]--;
    if(s[rk[x]]==0){
        change(1,1,n,rk[x],0);
        add(1,1,n,rk[x],n,-1);
    }
}
void build(seg){
    clear(tr[p].la);
    if(l==r){
        cnt[l].cnt[0][0]=1;
        return;
    }
    build(lid),build(rid);
}
int main(){
    scanf("%d%d",&n,&mod);
    Fib.cnt[0][0]=1,Fib.cnt[0][1]=1;
    Fib.cnt[1][0]=1;
    InvFib.cnt[0][1]=1;
    InvFib.cnt[1][0]=1;
    InvFib.cnt[1][1]=mod-1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)rk[i]=lower_bound(b+1,b+n+1,a[i])-b;
    for(int i=1;i<=n;i++)a[i]%=mod;
    scanf("%d",&Q);
    int S=sqrt(n);
    build(1,1,n);
    for(int i=1;i<=n;i++)id[i]=(i-1)/S+1;
    for(int i=1;i<=Q;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+Q+1,[](que a,que b){if(id[a.l]!=id[b.l])return a.l<b.l;return a.r<b.r;});
    int L=1,R=0;
    for(int i=1;i<=Q;i++){//莫队
        while(R<q[i].r)add(++R);
        while(L>q[i].l)add(--L);
        while(R>q[i].r)del(R--);
        while(L<q[i].l)del(L++);
        ans[q[i].id]=tr[1].Cnt.cnt[0][1];
    }
    for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
}

    然后你就发现，这个代码超时了，考虑优化。

    其实不需要延迟标记，直接考虑单点修改，只要可以维护两个区间直接的合并就好了。

    原来两个区间的和分别是

    x1fib1+x2fib2...+xkfibkx_1fib_1+x_2fib_2...+x_kfib_k xk+1fib1+xk+2fib2...+xk+nfibnx_{k+1}fib_1+x_{k+2}fib_2...+x_{k+n}fib_n

    合并成

    x1fib1+x2fib2...+xn+kfibn+kx_1fib_1+x_2fib_2...+x_{n+k}fib_{n+k}

    实际上就是右边的乘上 FibkFib^k，因为 nn 很小，直接预处理就好了。


    代码 
    #include<bits/stdc++.h>
#define seg int p,int l,int r
#define mid (l+r>>1)
#define lid p<<1,l,mid
#define rid p<<1|1,mid+1,r
using namespace std;
const int N=3e4+5;
struct mat{int cnt[2][2];}Fib,F[N];
struct segtree{int s;mat Cnt;}tr[N<<2];
int mod;
mat cnt[N];
void clear(mat &a){
    a.cnt[0][0]=a.cnt[1][1]=1;
    a.cnt[1][0]=a.cnt[0][1]=0;
}
mat operator*(const mat &a,const mat &b){
    mat ans;
    memset(ans.cnt,0,sizeof(ans.cnt));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++){
            long long S=0;
            for(int k=0;k<2;k++)S=S+a.cnt[i][k]*b.cnt[k][j];
            ans.cnt[i][j]=S%mod;
        }    
    return ans;
}
mat operator+(const mat &a,const mat &b){
    mat ans;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)ans.cnt[i][j]=(a.cnt[i][j]+b.cnt[i][j])%mod;
    return ans;
}
mat operator*(int a,mat b){
    mat ans;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)ans.cnt[i][j]=a*b.cnt[i][j]%mod;
    return ans;
}
void change(seg,int x,int z){
    if(l==r){
        tr[p].s=(z>=0?1:0);
        tr[p].Cnt=max(z,0)*Fib;
        return;
    }
    if(x<=mid)change(lid,x,z);
    else change(rid,x,z);
    tr[p].Cnt=tr[p<<1].Cnt+tr[p<<1|1].Cnt*F[tr[p<<1].s];
    tr[p].s=tr[p<<1].s+tr[p<<1|1].s;
}
int s[N],rk[N],n,a[N],b[N],id[N],Q,ans[N];
struct que{int l,r,id;}q[N];
void add(int x){
    s[rk[x]]++;
    if(s[rk[x]]==1)change(1,1,n,rk[x],a[x]);
}
void del(int x){
    s[rk[x]]--;
    if(s[rk[x]]==0)change(1,1,n,rk[x],-1);
}
int main(){
    scanf("%d%d",&n,&mod);
    Fib.cnt[0][0]=1,Fib.cnt[0][1]=1;
    Fib.cnt[1][0]=1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    clear(F[0]);
    for(int i=1;i<=n;i++)F[i]=F[i-1]*Fib;
    for(int i=1;i<=n;i++)rk[i]=lower_bound(b+1,b+n+1,a[i])-b;
    for(int i=1;i<=n;i++)a[i]%=mod;
    scanf("%d",&Q);
    int S=sqrt(n);
    for(int i=1;i<=n;i++)id[i]=(i-1)/S+1;
    for(int i=1;i<=Q;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+Q+1,[](que a,que b){if(id[a.l]!=id[b.l])return a.l<b.l;return (id[a.l]&1?a.r<b.r:a.r>b.r);});
    int L=1,R=0;
    for(int i=1;i<=Q;i++){
        while(R<q[i].r)add(++R);
        while(L>q[i].l)add(--L);
        while(R>q[i].r)del(R--);
        while(L<q[i].l)del(L++);
        ans[q[i].id]=tr[1].Cnt.cnt[0][1];
    }
    for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
}
    • 1

    Fibonacci-ish II

    信息

    ID
    4367
    时间
    5000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. 版权申诉
    6. Language
    7. 兼容模式
    8. 主题
    2. © 2021-2024 Hydro.ac
    4. Worker 0 in 72ms
    5. Hydro v4.11.2 Professional