注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4085][Sdoi2015]quality  

2015-06-20 19:54:01|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4085: [Sdoi2015]quality

Time Limit: 80 Sec  Memory Limit: 512 MB
Submit: 58  Solved: 11
[Submit][Status][Discuss]

Description

在一些音乐播放器的生产中,常常需要用到音频文件的音质检测。你现在需要模拟这个过程。对于一段音频文件,我们可以将其离散为一个长度为 N 的正整数序列 A 1 , A 2 , ... , A N 。所谓的音质检测,可以评定任何的一段区间[L,R],其音质性能取决于以下评分:
[BZOJ4085][Sdoi2015]quality - Trinkle - n+e
其中 F 是满足如下性质的数列:
F[1] = 1 , F[2] = 2 , F[i+2] = F[i+1] +a* F[i] +b 。
同时,A 数列还需要支持修正操作:对于一段区间[L,R],同时将其中的元素增加一,或减少一。

Input

输入的第一行有两个正整数 N,Q,分别表示序列的长度以及操作次数。
第二行有两个非负整数 a,b。
第三行有 N 个正整数,描述序列 A。
接下来 Q 行,每行是如下三种格式之一:
plus L R:表示将 A 序列中[L,R]中的元素增加一。
minus L R:表示将 A 序列中[L,R]中的元素减少一。
query L R:表示询问 A 序列中[L,R]的音质评分。
所有操作均保证 L ≤ R,且保证 A i 严格大于总修改次数加一(包括 plus 操作和 minus 操作)。

Output

对于每个query操作,你需要输出一个整数,为所求的音质评分对 10^9 +7 取模后的值。

Sample Input

17 7
1 0
3 4 5 6 7 8 9
query 2 4
query 3 7
plus 3 5
query 2 4
plus 4 7
query 3 7
query 1 7

Sample Output

64
1766
104
7479
7687

HINT

对于 15%的数据,N ≤ 8000 , Q ≤ 8000
对于另 15%的数据,每一次修改的区间都是[1,N]
对于另 30%的数据,保证 a=0 , b=1
对于 100% 的数据,N ≤ 300000 , Q ≤ 10000,0 ≤ a,b ≤ 10^9

Solution

初始的F[]用矩阵快速幂处理,因为是要执行30w次,所以要优化:
1.先把转移矩阵的2的幂次处理出来;
2.3*3的矩阵注意到有一行怎么乘都不变所以可以变成2*3的矩阵。

然后接下来对于每个节点i,维护F[a[i-1]+1]*F[a[i+1]-1],类似于F[a]*F[b]
然而直接维护是不行的,还需要额外维护8个东西,总共维护一个9*1的列向量[F[a]*F[b],F[a]*F[b+1],F[a+1]*F[b],F[a+1]*F[b+1],F[a],F[a+1],F[b],F[b+1],1],然后构一个9*9的矩阵就能转移了
每次修改区间[l,r]就变成修改[l+1,r+1]的F[a]和[l-1,r-1]的F[b],查询直接查。
注意特判A=0的情况。

Code

/**************************************************************
    Problem: 4085
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:56076 ms
    Memory:50612 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define p 1000000007
int a,b,inv,x,y,z;
int power(int t,int k){int f=1;
    for(;k;k>>=1,t=1LL*t*t%p)
    if(k&1)f=1LL*f*t%p;
    return f;
}
struct M0{int m[3][3];}pw0[33];
M0 operator*(const M0&a,const M0&b){
    static M0 c;
    c.m[0][0]=(1LL*a.m[0][0]*b.m[0][0]+1LL*a.m[0][1]*b.m[1][0])%p;
    c.m[0][1]=(1LL*a.m[0][0]*b.m[0][1]+1LL*a.m[0][1]*b.m[1][1])%p;
    c.m[0][2]=(1LL*a.m[0][0]*b.m[0][2]+1LL*a.m[0][1]*b.m[1][2]+a.m[0][2])%p;
    c.m[1][0]=(1LL*a.m[1][0]*b.m[0][0]+1LL*a.m[1][1]*b.m[1][0])%p;
    c.m[1][1]=(1LL*a.m[1][0]*b.m[0][1]+1LL*a.m[1][1]*b.m[1][1])%p;
    c.m[1][2]=(1LL*a.m[1][0]*b.m[0][2]+1LL*a.m[1][1]*b.m[1][2]+a.m[1][2])%p;
    c.m[2][0]=c.m[2][1]=0,c.m[2][2]=1;return c;
}
void getf(int n){
    if(n==1){x=1,y=2;return;}
    static M0 f;f=pw0[0];int i;
    for(n-=2,i=1;n;n>>=1,i++)if(n&1)f=f*pw0[i];
    y=(2LL*f.m[0][0]+f.m[0][1]+f.m[0][2])%p;
    x=(2LL*f.m[1][0]+f.m[1][1]+f.m[1][2])%p;
}
struct M{int m[9][9];}dt[4][16],I;
M operator*(const M&a,const M&b){
    static M c;memset(&c,0,sizeof(c));
    for(int i=0;i<9;i++)
    for(int k=0;k<9;k++)
    for(int j=0;j<9;j++)
    c.m[i][j]=(c.m[i][j]+1LL*a.m[i][k]*b.m[k][j])%p;
    return c;
}
M power(M t[],int k){
    static M f;f=t[0];
    for(int i=1;k;k>>=1,i++)if(k&1)f=f*t[i];
    return f;
}
void init(int op,M a[],int x,int y,int z){
    if(op==0){
        int b[9][9]={
{0,0,1,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0,0},
{y,0,x,0,0,0,z,0,0},
{0,y,0,x,0,0,0,z,0},
{0,0,0,0,0,1,0,0,0},
{0,0,0,0,y,x,0,0,z},
{0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,1},
        };
        memcpy(a[1].m,b,sizeof(b));
    }
    else if(op==1){
        int b[9][9]={
{0,1,0,0,0,0,0,0,0},
{y,x,0,0,z,0,0,0,0},
{0,0,0,1,0,0,0,0,0},
{0,0,y,x,0,z,0,0,0},
{0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,1,0,0,0},
{0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,y,x,z},
{0,0,0,0,0,0,0,0,1},
        };
        memcpy(a[1].m,b,sizeof(b));
    }
    else if(op==2){
        int b[9][9]={
{y,0,x,0,0,0,z,0,0},
{0,y,0,x,0,0,0,z,0},
{1,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0},
{0,0,0,0,y,x,0,0,z},
{0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,1},
        };
        memcpy(a[1].m,b,sizeof(b));
    }
    else{
        int b[9][9]={
{y,x,0,0,z,0,0,0,0},
{1,0,0,0,0,0,0,0,0},
{0,0,y,x,0,z,0,0,0},
{0,0,1,0,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,1,0,0,0},
{0,0,0,0,0,0,y,x,z},
{0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,0,1},
        };
        memcpy(a[1].m,b,sizeof(b));
    }
    a[0]=I;
    for(int i=2;i<=15;i++)a[i]=a[i-1]*a[i-1];
}
int n,q,d[300010][4],a1[1<<20],a0[1<<20];char op;
struct V{
    int m[9];
    void setup(int fa,int ifa,int fb,int ifb){
        m[0]=1LL*fa*fb%p,m[1]=1LL*fa*ifb%p,m[2]=1LL*ifa*fb%p,m[3]=1LL*ifa*ifb%p;
        m[4]=fa,m[5]=ifa,m[6]=fb,m[7]=ifb,m[8]=1;
    }
}t[1<<20],ans;
V operator+(const V&a,const V&b){
    static V c;
    for(int i=0;i<=9;i++)c.m[i]=(a.m[i]+b.m[i])%p;
    return c;
}
V operator*(const M&a,const V&b){
    static V c;memset(&c,0,sizeof(c));
    for(int i=0;i<9;i++)
    for(int j=0;j<9;j++)c.m[i]=(c.m[i]+1LL*a.m[i][j]*b.m[j])%p;
    return c;
}
void bt(int o,int l,int r){
    if(l==r){
        t[o].setup(d[l-1][2],d[l-1][3],d[r+1][0],d[r+1][1]);
        return;
    }
    int mid=l+r>>1;
    bt(o<<1,l,mid);
    bt(o<<1|1,mid+1,r);
    t[o]=t[o<<1]+t[o<<1|1];
}
void pw(V&f,M t[],int k){
    for(int i=1;k;k>>=1,i++)
    if(k&1)f=t[i]*f;
}
void calc(int o,int a,int b){
    if(a!=0){
        if(a<0)pw(t[o],dt[2],-a);
        else pw(t[o],dt[0],a);
    }
    if(b!=0){
        if(b<0)pw(t[o],dt[3],-b);
        else pw(t[o],dt[1],b);
    }
}
void pd(int o,int l,int r){
    calc(o,a0[o],a1[o]);
    if(l<r){
        a0[o<<1]+=a0[o],a0[o<<1|1]+=a0[o];
        a1[o<<1]+=a1[o],a1[o<<1|1]+=a1[o];
    }a0[o]=a1[o]=0;
}
void mt(int o,int l,int r){
    int mid=l+r>>1;
    pd(o<<1,l,mid);
    pd(o<<1|1,mid+1,r);
    t[o]=t[o<<1]+t[o<<1|1];
}
void upd(int o,int l,int r){
    if(x<=l&&r<=y){
        if(z==0)a0[o]++;
        else if(z==1)a1[o]++;
        else if(z==2)a0[o]--;
        else a1[o]--;return;
    }
    int mid=l+r>>1;pd(o,l,r);
    if(x<=mid)upd(o<<1,l,mid);
    if(mid<y)upd(o<<1|1,mid+1,r);
    mt(o,l,r);
}
void update(int op,int l,int r){
    if(x=l,y=r,z=op,x>y)return;
    upd(1,2,n-1);
}
void query(int o,int l,int r){
    pd(o,l,r);
    if(x<=l&&r<=y){
        ans=ans+t[o];
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)query(o<<1,l,mid);
    if(mid<y)query(o<<1|1,mid+1,r);
}
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
int main(){
    for(int i=0;i<9;i++)I.m[i][i]=1;
    n=F(),q=F(),a=F()%p,b=F()%p;
    pw0[0].m[0][0]=pw0[0].m[1][1]=pw0[0].m[2][2]=1;
    pw0[1].m[0][0]=pw0[1].m[1][0]=pw0[1].m[2][2]=1,pw0[1].m[0][1]=a,pw0[1].m[0][2]=b;
    for(int i=2;i<=31;i++)pw0[i]=pw0[i-1]*pw0[i-1];
    for(int i=1;i<=n;i++){
        getf(F());d[i][0]=x,d[i][1]=y;
        d[i][2]=(d[i][1]+1LL*d[i][0]*a+b)%p;
        d[i][3]=(d[i][2]+1LL*d[i][1]*a+b)%p;
    }
    init(0,dt[0],1,a,b),init(1,dt[1],1,a,b);inv=power(a,p-2);
    if(a)init(2,dt[2],inv,(p-inv)%p,1LL*b*(p-inv)%p),init(3,dt[3],inv,(p-inv)%p,1LL*b*(p-inv)%p);
    else init(2,dt[2],0,1,(p-b)%p),init(3,dt[3],0,1,(p-b)%p);
    for(bt(1,2,n-1);q--;){
        while(op=getc(),op!='q'&&op!='p'&&op!='m');int l=F(),r=F();
        if(op=='q'){
            memset(&ans,0,sizeof(ans));
            if(x=l+1,y=r-1,x<=y)query(1,2,n-1);
            printf("%d\n",ans.m[0]);
        }
        else if(op=='p')
            update(0,l+1,min(n-1,r+1)),update(1,max(l-1,2),r-1);
        else
            update(2,l+1,min(n-1,r+1)),update(3,max(l-1,2),r-1);
    }
}
  评论这张
 
阅读(314)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018