CF 266E More Queries to Array.(线段树)

CF 266E More Queries to Array...(线段树)

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by---cxlove

题目：给出一个数列，修改操作是将区间的数改为同一个数，查询操作是查询区间。http://codeforces.com/contest/266/problem/E 
有个条件大概就是k<=5，其实这个题目难在每个ai在每次查询的时候前面的系数都不一样。lepus里问了一下，得到叉姐的两个字：展开。。。TAT大概只能硬着头皮上了。由于k的范围 很小，大概就是突破口吧。对于k=0，其实就是一个区间和，可以写成ai 对于k=1，ai ( i + (1-L) ^ 1 )对于k=2，ai ( i^2 + 2 * i ^ 1 +(1-L) ^ 2)
对于k， ai * sigma(c(k,j) * i^j *(1-L) ^ (k-j) )   (0<=j<=k)那么对于每一次查询(1-L)是已知的，是常数，那么(1-L)^(k-j)是可以预处理的。那么我们只需要维护ai * i^j这个部分，用线段树就行了。对于修改，某个区间变为同一个数的话，那么区间和便是   num * sigma(i^j)  (i<=i<=r)，后者也是可以预处理的。然后组合数是需要预处理的，i^j也是需要预处理的。反正大概就是个很2的题吧~~~可惜不敢尝试，不敢展开。。。 

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<queue>#define inf 0x3f3f3f3f#define MOD 1000000007#define lson (step<<1)#define rson (step<<1|1)#define pb(a) push_back(a)#define mp(a,b) make_pair(a,b)#define mem(a,b) memset(a,b,sizeof(a))#define LL long longusing namespace std;const int N=100005;struct Seg_tree{    int left,right;    LL lazy,sum[6];}L[N<<2];int n,q,a[N];LL fac[N][6];  //fac[i][j] 表示i^j的值  LL sum[N][6]={0};  //sum[i][j] 表示1^j+2^j……+i^j的值LL c[6][6];    //组合数LL s[N][6];    //s[i][j]表示(1-i)^jvoid Init(){    for(int i=0;i<6;i++){        c[i][0]=c[i][i]=1;        for(int j=1;j<i;j++)            c[i][j]=(c[i-1][j]+c[i-1][j-1]);    }    for(int i=1;i<=n;i++){        fac[i][0]=1;        sum[i][0]=i;        s[i][0]=1;    }    for(int i=1;i<6;i++){        for(int j=1;j<=n;j++){            fac[j][i]=(fac[j][i-1]*j)%MOD;            sum[j][i]=(sum[j-1][i]+fac[j][i])%MOD;            s[j][i]=((s[j][i-1]*(1-j))%MOD+MOD)%MOD;        }    }}void push_up(int step){    for(int i=0;i<6;i++)        L[step].sum[i]=(L[lson].sum[i]+L[rson].sum[i])%MOD;}void update(int step,int l,int r,int x);void push_down(int step){    if(L[step].lazy!=-1){        int l=L[step].left,r=L[step].right,m=(l+r)>>1;        update(lson,l,m,L[step].lazy);        update(rson,m+1,r,L[step].lazy);        L[step].lazy=-1;    }}void bulid(int step,int l,int r){    L[step].left=l;    L[step].right=r;    L[step].lazy=-1;    if(l==r){        for(int i=0;i<6;i++)            L[step].sum[i]=(a[l]*fac[l][i])%MOD;        return ;    }    int m=(l+r)>>1;    bulid(lson,l,m);    bulid(rson,m+1,r);    push_up(step);}void update(int step,int l,int r,int x){    if(L[step].left==l&&L[step].right==r){        L[step].lazy=x;        for(int i=0;i<6;i++){            LL tmp=((sum[r][i]-sum[l-1][i])%MOD+MOD)%MOD;            L[step].sum[i]=(tmp*x)%MOD;        }        return ;    }    push_down(step);    int m=(L[step].left+L[step].right)>>1;    if(r<=m) update(lson,l,r,x);    else if(l>m) update(rson,l,r,x);    else{        update(lson,l,m,x);        update(rson,m+1,r,x);    }    push_up(step);}LL query(int step,int l,int r,int k){    if(L[step].left==l&&L[step].right==r)        return L[step].sum[k];    int m=(L[step].left+L[step].right)>>1;    push_down(step);    if(r<=m) return query(lson,l,r,k);    else if(l>m) return query(rson,l,r,k);    else return (query(lson,l,m,k)+query(rson,m+1,r,k))%MOD;}int main(){    //freopen("input.txt","r",stdin);    scanf("%d%d",&n,&q);    for(int i=1;i<=n;i++)        scanf("%d",&a[i]);    Init();    bulid(1,1,n);    while(q--){        char ope[5];        int l,r,k;        scanf("%s%d%d%d",&ope,&l,&r,&k);        if(ope[0]=='=') update(1,l,r,k);        else{            LL ans=0;            for(int i=0;i<=k;i++)                ans=((((query(1,l,r,i)*c[k][i])%MOD*s[l][k-i])%MOD+ans)%MOD+MOD)%MOD;            printf("%I64d\n",ans);        }    }    return 0;}

查看更多 下一篇