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

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

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

题目：给出一个数列，修改操作是将区间的数改为同一个数，查询操作是查询区间 CF 266E More Queries to Array.(线段树)

。

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 long
using 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)^j
void 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;
}

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

相关推荐