【cf266e】

2015.03.21 15:46 Sat | 3次阅读 | 旧日oi | 固定链接 | 源码

You've got an array, consisting of n integers: a_1, _a_2, ..., _an. Your task is to quickly run the queries of two types:
1. Assign value x to all elements from l to r inclusive. After such query the values of the elements of array al, al + 1, ..., ar become equal to x
2. Calculate and print sum , where k doesn't exceed 5. As the value of the sum can be rather large, you should print it modulo 1000000007 (109 + 7).
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 105), showing, how many numbers are in the array and the number of queries, correspondingly. The second line contains n integers: a_1, _a_2, ..., _an (0 ≤ ai ≤ 109) — the initial values of the array elements.
Then m queries follow, one per line:

  1. The assign query has the following format: "", (1 ≤ l ≤ r ≤ n; 0 ≤ x ≤ 109)
  2. The query to calculate the sum has the following format: "", (1 ≤ l ≤ r ≤ n; 0 ≤ k ≤ 5). All numbers in the input are integers. Output For each query to calculate the sum print an integer — the required sum modulo 1000000007 (109 + 7). Sample test(s) input 4 5 5 10 2 1 ? 1 2 1 = 2 2 0 ? 2 4 3 = 1 4 1 ? 1 4 5 output 25 43 1300 input 3 1 1000000000 1000000000 1000000000 ? 1 3 0 output 999999986

题解

把公式拆开,用线段树维护就可以了

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define q(x) query(1,n,1,l+1,r,x)%mod
#define p(x,y) qpow(x,y)
#define ull unsigned long long
#define rson mid+1,r,rt<<1|1
#define lson l,mid,rt<<1
#define mod 1000000007
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 100010
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,l,r,x;
char s[2];
ll val[maxn<<2][6],sum[6][maxn<<2];
int flag[maxn<<2];
ll qpow(ll a,int k)
{
    ll ret=1;
    while(k)
    {
        if(k&1) ret=(ret*a)%mod;
        k>>=1;
        a=(a*a)%mod;
    }
    return ret;
}
void push_up(int rt)
{
    for(int i=0;i<6;i++)
    val[rt][i]=(val[rt<<1][i]+val[rt<<1|1][i])%mod;
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        val[rt][0]=read();
        for(int i=1;i<=5;i++) val[rt][i]=val[rt][0]*qpow(l,i)%mod;
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}
void rebuild(int l,int r,int rt,int x)
{
    for(int i=0;i<=5;i++)
    val[rt][i]=(x*(sum[i][r]-sum[i][l-1])%mod+mod)%mod;
    flag[rt]=x;
}
void push_down(int rt,int l,int r)
{
    if(flag[rt]!=-1)
    {
        int mid=l+r>>1;
        rebuild(lson,flag[rt]);
        rebuild(rson,flag[rt]);
        flag[rt]=-1;
    }
}
void update(int l,int r,int rt,int L,int R,int c)
{
    if(L<=l&&R>=r)
    {
        rebuild(l,r,rt,c);
        return;
    }
    push_down(rt,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) update(lson,L,R,c);
    if(R>mid) update(rson,L,R,c);
    push_up(rt);
} 
ll query(int l,int r,int rt,int L,int R,int k)
{
    if(L<=l&&R>=r) return val[rt][k];
    push_down(rt,l,r);
    ll ret=0;
    int mid=(l+r)>>1;
    if(L<=mid) ret=query(lson,L,R,k);
    if(R>mid) ret=(ret+query(rson,L,R,k))%mod;
    return (ret%mod+mod)%mod;
}
ll get_ans(int l,int r,int k)
{
    if(k==0) return q(0);
    if(k==1) return (q(1)-l*q(0)%mod+mod)%mod;
    if(k==2) return (q(2)-2*l*q(1)%mod+p(l,2)*q(0)%mod+mod)%mod;        
    if(k==3) return (q(3)-3*l*q(2)%mod+3*p(l,2)%mod*q(1)%mod-p(l,3)%mod*q(0)%mod)%mod;      
    if(k==4) return (q(4)-4*l*q(3)%mod+6*p(l,2)%mod*q(2)%mod-4*p(l,3)%mod*q(1)%mod+p(l,4)%mod*q(0)%mod)%mod;        
    if(k==5) return (q(5)-5*l*q(4)%mod+10*p(l,2)%mod*q(3)%mod-10*p(l,3)%mod*q(2)%mod+5*p(l,4)%mod*q(1)%mod-p(l,5)*q(0)%mod)%mod;                    
}
int main()
{
    freopen("query.in","r",stdin);
    freopen("query.out","w",stdout);
    //freopen("me.out","w",stdout);
    memset(flag,-1,sizeof(flag));
    n=read();m=read();
    build(1,n,1);
    for(int i=0;i<=5;i++)
    {
        for(int j=1;j<=n;j++)
        sum[i][j]=(sum[i][j-1]+p(j,i))%mod;
    }
    while(m--)
    {
        scanf("%s",s);
        l=read();r=read();x=read();
        if(s[0]=='=') update(1,n,1,l,r,x);
        else printf("%d\n",(get_ans(l-1,r,x)+mod)%mod);
    }
    return 0;
}```