hdu4578（三个更新操作，三个求值操作）-白红宇

hdu4578（三个更新操作，三个求值操作）

阅读量：2440 次

发布时间：2019-05-10

本文共 3465 字，大约阅读时间需要 11 分钟。

题意：有长为n的数列，初始化为全部为0，我们对它有三个操作：

(1)把数列中的一段区间全部乘一个值;

(2)把数列中的一段区间全部加一个值;

(3)把数列中的一段区间全部替换成一个值；

然后再对它有一个查询操作：

求数列中的一段区间的每个数的p次方之和（1<=p<=3）

解题思路：

因为p只有三个值，所以我们可以将这三个值分别进行求解，我将它们定义为sum，sum2，sum3；

结构体定义：

struct Node{

int l,r;

ll sum,sum2,sum3;

int add,mul;

}tree[4*MAXN];

两个lazy-tag标记分别初始化为add=0,mul=1;

我们用两个lazy-tag标记来处理三个更新，对于第三个替换更新，我们可以用前面两个标记进行更新，即mul=0，add=v;然后我们设置lazy-tag标记的优先级，乘法>加法；

细节问题：

<1>(p=1)

(a1*mul+add) + (a1*mul+add) + ... + (an*mul+add) = (a1+a2+...+an)*mul + n*add;

<2>(p=2)

(a1*mul+add)^2 + (a1*mul+add)^2 + ... + (an*mul+add)^2 = (a1^2+a2^2+...+an^2)*mul^2 + 2*add*mul*(a1+a2+...+an) + n*add^2;

<3>(p=3)

(a1*mul+add)^3 + (a1*mul+add)^3 + ... + (a1*mul+add)^3 = (a1^3+a2^3+...+an^3)*mul^3 +

3*add*mul^2*(a1^2+a2^2+...+an^2) + 3*add^2*mul*(a1+a2+...+an) + n*add^3;

参考代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN = 100000+5;typedef long long ll;#define MOD 10007struct Node{	int l,r;	ll sum,sum2,sum3;	int add,mul;}tree[4*MAXN];void build(int node,int l,int r){	tree[node].l=l,tree[node].r=r;	tree[node].add=0,tree[node].mul=1;	if (l==r){		tree[node].sum=tree[node].sum2=tree[node].sum3=0;		return;	}	build(node*2,l,(l+r)/2);	build(node*2+1,(l+r)/2+1,r);	tree[node].sum=(tree[node*2].sum+tree[node*2+1].sum)%MOD;	tree[node].sum2=(tree[node*2].sum2+tree[node*2+1].sum2)%MOD;	tree[node].sum3=(tree[node*2].sum3+tree[node*2+1].sum3)%MOD;}void PushDown(int node){	if (tree[node].add==0 && tree[node].mul==1)		return;	tree[node*2].sum3=(tree[node].mul*tree[node].mul%MOD*tree[node].mul%MOD*tree[node*2].sum3%MOD + 3*tree[node].mul*tree[node].mul%MOD*tree[node].add%MOD*tree[node*2].sum2%MOD + 3*tree[node].mul*tree[node].add%MOD*tree[node].add%MOD*tree[node*2].sum%MOD + (tree[node*2].r-tree[node*2].l+1)*tree[node].add%MOD*tree[node].add%MOD*tree[node].add%MOD)%MOD;	tree[node*2].sum2=(tree[node*2].sum2*tree[node].mul%MOD*tree[node].mul%MOD + 2*tree[node].add*tree[node].mul%MOD*tree[node*2].sum%MOD + (tree[node*2].r-tree[node*2].l+1)*tree[node].add%MOD*tree[node].add%MOD)%MOD;	tree[node*2].sum=(tree[node*2].sum*tree[node].mul + tree[node].add*(tree[node*2].r-tree[node*2].l+1)%MOD)%MOD;	tree[node*2+1].sum3=(tree[node].mul*tree[node].mul%MOD*tree[node].mul*tree[node*2+1].sum3%MOD + 3*tree[node].mul*tree[node].mul%MOD*tree[node].add%MOD*tree[node*2+1].sum2%MOD + 3*tree[node].mul*tree[node].add%MOD*tree[node].add%MOD*tree[node*2+1].sum%MOD + (tree[node*2+1].r-tree[node*2+1].l+1)*tree[node].add%MOD*tree[node].add%MOD*tree[node].add%MOD)%MOD;	tree[node*2+1].sum2=(tree[node*2+1].sum2*tree[node].mul%MOD*tree[node].mul%MOD + 2*tree[node].add*tree[node].mul%MOD*tree[node*2+1].sum%MOD + (tree[node*2+1].r-tree[node*2+1].l+1)*tree[node].add%MOD*tree[node].add%MOD)%MOD;	tree[node*2+1].sum=(tree[node*2+1].sum*tree[node].mul%MOD + tree[node].add*(tree[node*2+1].r-tree[node*2+1].l+1)%MOD)%MOD;	tree[node*2].mul=(tree[node*2].mul*tree[node].mul)%MOD;	tree[node*2].add=(tree[node*2].add*tree[node].mul%MOD+tree[node].add)%MOD;	tree[node*2+1].mul=(tree[node*2+1].mul*tree[node].mul)%MOD;	tree[node*2+1].add=(tree[node*2+1].add*tree[node].mul%MOD+tree[node].add)%MOD;	tree[node].add=0;	tree[node].mul=1;}void Add(int node,int l,int r,int v){	if (tree[node].l>r || tree[node].r
        
         r || tree[node].r
         
          r || tree[node].r
          
           mid) return query(node*2+1,l,r,p); else return (query(node*2,l,mid,p)+query(node*2+1,mid+1,r,p))%MOD; /* if (tree[node].l>r || tree[node].r