HDU - 4578Transformation——線段樹+區間加法修改+區間乘法修改+區間置數+區間和查詢+區間平方和查詢+區間立方和查詢

【題目描述】
HDU - 4578Transformation
Problem Description
Yuanfang is puzzled with the question below:
There are n integers, a1, a2, …, an. The initial values of them are 0. There are four kinds of operations.
Operation 1: Add c to each number between ax and ay inclusive. In other words, do transformation ak<—ak+c, k = x,x+1,…,y.
Operation 2: Multiply c to each number between ax and ay inclusive. In other words, do transformation ak<—ak×c, k = x,x+1,…,y.
Operation 3: Change the numbers between ax and ay to c, inclusive. In other words, do transformation ak<—c, k = x,x+1,…,y.
Operation 4: Get the sum of p power among the numbers between ax and ay inclusive. In other words, get the result of axp+ax+1p+…+ay p.
Yuanfang has no idea of how to do it. So he wants to ask you to help him.

Input
There are no more than 10 test cases.
For each case, the first line contains two numbers n and m, meaning that there are n integers and m operations. 1 <= n, m <= 100,000.
Each the following m lines contains an operation. Operation 1 to 3 is in this format: “1 x y c” or “2 x y c” or “3 x y c”. Operation 4 is in this format: “4 x y p”. (1 <= x <= y <= n, 1 <= c <= 10,000, 1 <= p <= 3)
The input ends with 0 0.

Output
For each operation 4, output a single integer in one line representing the result. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10007.

Sample Input

5 5
3 3 5 7
1 2 4 4
4 1 5 2
2 2 5 8
4 3 5 3
0 0

Sample Output

307
7489
【題目分析】
這道題真的是老妖怪級別的了，此處省略吐槽兩千字
題目的意思很明確，就是給你一個全為0 的數組，讓你實現區間加法修改+區間乘法修改+區間置數+區間和查詢+區間平方和查詢+區間立方和查詢功能。
根據需求，每個區間有三個需要維護的數據——區間和，區間平方和，區間立方和，有三種修改操作，因此需要三種標記，分別用來標記區間加法、區間乘法、區間置數
難點在于對于三種數據的快速維護和標記之間的關系

標記之間的關系（關鍵）
我們為了實現區間修改就需要引入lazy標記（沒有掌握這個的同學請出門左拐，詳見線段樹入門），但是當存在多種標記的時候處理標記的順序就很重要，因為這反應了修改操作的效用關系以及時間關系。
上面三種操作里面最厲害的顯然是區間置數，一個區間置數后之前什么加法乘法統統作廢。然后是區間乘法，因為區間乘法，因為對同一個區間，后來的乘法標記會對之前的加法標記產生影響，但是后來的加法標記對乘法標記卻沒有什么影響（先算乘法再算加法嘛）
因此在處理區間置數的時候可以直接對區間加法置零，對區間乘法的標記置一
在處理區間乘法的時候如果發現下面的區間還要進行區間加法就要修改區間加法的標記（給標記也乘上同一個數）
在處理區間加法的時候對其他標記沒有影響
同樣的，在下傳標記的時候同樣要面對這樣的問題
這樣，后面的操作對前面操作的影響就能傳遞下去
三種數據的快速維護
區間置數后三種數據直接計算
區間乘法后立方和乘上乘數的立方，平方和乘上乘數的平方，區間和乘上乘數，需要注意取模（時刻取模，時刻提防爆數據）
最麻煩的是區間加法
對于區間和，應該加上區間長度乘上加數
對于平方和，見下圖

立方和同理
【AC代碼】（可寫死我了）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<climits>
#include<queue>
#include<vector>using namespace std;
typedef long long ll;const int MAXN=100005;
const ll MOD=10007;struct node
{ll a,aa,aaa;
}tree[MAXN<<2];
ll set[MAXN<<2],add[MAXN<<2],multiply[MAXN<<2];
int n,m;
ll t;void pushdown(int k,int l,int r)
{int mid=(l+r)>>1; if(set[k]>0){tree[k<<1].a=set[k]%MOD*(mid-l+1)%MOD; tree[k<<1|1].a=set[k]%MOD*(r-mid)%MOD;tree[k<<1].aa=set[k]%MOD*set[k]%MOD*(mid-l+1)%MOD; tree[k<<1|1].aa=set[k]%MOD*set[k]%MOD*(r-mid)%MOD;tree[k<<1].aaa=set[k]%MOD*set[k]%MOD*set[k]%MOD*(mid-l+1)%MOD; tree[k<<1|1].aaa=set[k]%MOD*set[k]%MOD*set[k]%MOD*(r-mid)%MOD;set[k<<1]=set[k<<1|1]=set[k];	add[k<<1]=add[k<<1|1]=0;	//直接取消標記multiply[k<<1]=multiply[k<<1|1]=1;	//直接取消標記set[k]=0;}if(multiply[k]!=1){tree[k<<1].a=tree[k<<1].a*multiply[k]%MOD;tree[k<<1|1].a=tree[k<<1|1].a*multiply[k]%MOD;tree[k<<1].aa=tree[k<<1].aa*multiply[k]%MOD*multiply[k]%MOD;tree[k<<1|1].aa=tree[k<<1|1].aa*multiply[k]%MOD*multiply[k]%MOD;tree[k<<1].aaa=tree[k<<1].aaa*multiply[k]%MOD*multiply[k]%MOD*multiply[k]%MOD;tree[k<<1|1].aaa=tree[k<<1|1].aaa*multiply[k]%MOD*multiply[k]%MOD*multiply[k]%MOD;multiply[k<<1]=multiply[k<<1]*multiply[k]%MOD;multiply[k<<1|1]=multiply[k<<1|1]*multiply[k]%MOD;if(add[k<<1]) add[k<<1]=add[k<<1]*multiply[k]%MOD;	//注意對加法標記的影響if(add[k<<1|1]) add[k<<1|1]=add[k<<1|1]*multiply[k]%MOD;-multiply[k]=1;}if(add[k]>0){tree[k<<1].aaa=(((tree[k<<1].aaa+3*add[k]%MOD*tree[k<<1].aa%MOD)%MOD+3*add[k]%MOD*add[k]%MOD*tree[k<<1].a%MOD)%MOD+(mid-l+1)*add[k]%MOD*add[k]%MOD*add[k]%MOD)%MOD; //順序很重要，應該先立方后平方再區間和（因為會用到原始數據）tree[k<<1|1].aaa=(((tree[k<<1|1].aaa+3*add[k]%MOD*tree[k<<1|1].aa%MOD)%MOD+3*add[k]%MOD*add[k]%MOD*tree[k<<1|1].a%MOD)%MOD+(r-mid)*add[k]%MOD*add[k]%MOD*add[k]%MOD)%MOD; tree[k<<1].aa=((tree[k<<1].aa+add[k]*add[k]%MOD*(mid-l+1)%MOD)%MOD+2*add[k]%MOD*tree[k<<1].a%MOD)%MOD;tree[k<<1|1].aa=((tree[k<<1|1].aa+add[k]*add[k]%MOD*(r-mid)%MOD)%MOD+2*add[k]%MOD*tree[k<<1|1].a%MOD)%MOD;tree[k<<1].a=(tree[k<<1].a+add[k]*(mid-l+1)%MOD)%MOD;tree[k<<1|1].a=(tree[k<<1|1].a+add[k]*(r-mid)%MOD)%MOD;add[k<<1]=(add[k<<1]+add[k])%MOD;add[k<<1|1]=(add[k<<1|1]+add[k])%MOD;//時刻注意取模add[k]=0;}
}void update(int k)
{tree[k].a=(tree[k<<1].a+tree[k<<1|1].a)%MOD;tree[k].aa=(tree[k<<1].aa+tree[k<<1|1].aa)%MOD;tree[k].aaa=(tree[k<<1].aaa+tree[k<<1|1].aaa)%MOD;
}void interval_add(int k,int l,int r,int x,int y,ll z)
{if(l>=x && r<=y){tree[k].aaa=(((tree[k].aaa+3*z%MOD*tree[k].aa%MOD)%MOD+3*z%MOD*z%MOD*tree[k].a)%MOD+(r-l+1)*z%MOD*z%MOD*z%MOD)%MOD;tree[k].aa=((tree[k].aa+2*z%MOD*tree[k].a%MOD)%MOD+(r-l+1)*z%MOD*z%MOD)%MOD;tree[k].a=(tree[k].a+z*(r-l+1)%MOD)%MOD;add[k]=(add[k]+z)%MOD;return;}int mid=(l+r)>>1;pushdown(k,l,r);if(x<=mid) interval_add(k<<1,l,mid,x,y,z);if(y>mid) interval_add(k<<1|1,mid+1,r,x,y,z);update(k); 
}void interval_multiply(int k,int l,int r,int x,int y,ll z)
{if(l>=x && r<=y){multiply[k]=(multiply[k]*z)%MOD;if(add[k]>0){add[k]=(add[k]*z)%MOD;}tree[k].a=tree[k].a*z%MOD;tree[k].aa=tree[k].aa*z%MOD*z%MOD;tree[k].aaa=tree[k].aaa*z%MOD*z%MOD*z%MOD;return;}int mid=(l+r)>>1;pushdown(k,l,r);if(x<=mid) interval_multiply(k<<1,l,mid,x,y,z);if(y>mid) interval_multiply(k<<1|1,mid+1,r,x,y,z);update(k); 
}void interval_set(int k,int l,int r,int x,int y,ll z)
{if(l>=x && r<=y){tree[k].a=z*(r-l+1)%MOD;tree[k].aa=z*z%MOD*(r-l+1)%MOD;tree[k].aaa=z*z%MOD*z%MOD*(r-l+1)%MOD;add[k]=0;multiply[k]=1;set[k]=z;return;}int mid=(l+r)>>1;pushdown(k,l,r);if(x<=mid) interval_set(k<<1,l,mid,x,y,z);if(y>mid) interval_set(k<<1|1,mid+1,r,x,y,z);update(k); 
}ll query(int k,int l,int r,int x,int y,int z)
{if(l>=x && r<=y){if(z==1)return tree[k].a%MOD;if(z==2)return tree[k].aa%MOD;if(z==3)return tree[k].aaa%MOD;}int mid=(l+r)>>1;ll ans=0;pushdown(k,l,r);if(x<=mid) ans=(ans+query(k<<1,l,mid,x,y,z))%MOD;if(y>mid) ans=(ans+query(k<<1|1,mid+1,r,x,y,z))%MOD;return ans;
}void search_point(int k,int l,int r,int x)
{if(l==r && l==x){t=tree[k].a;return;}pushdown(k,l,r);int mid=(l+r)>>1;if(x<=mid) search_point(k<<1,l,mid,x);else search_point(k<<1|1,mid+1,r,x);
}void test()
{for(int i=1;i<=n;i++){search_point(1,1,n,i);printf("%lld ",t);}printf("\n");
}int main()
{ll cmd,u,v,w;while(~scanf("%d%d",&n,&m) && (n||m)){memset(tree,0,sizeof(tree));memset(set,0,sizeof(set));memset(add,0,sizeof(add));for(int i=0,j=n<<2;i<=j;i++) multiply[i]=1;for(int i=0;i<m;i++){scanf("%lld%lld%lld%lld",&cmd,&u,&v,&w);if(cmd==1){interval_add(1,1,n,u,v,w%MOD);}else if(cmd==2){interval_multiply(1,1,n,u,v,w%MOD);}else if(cmd==3){interval_set(1,1,n,u,v,w%MOD);}else if(cmd==4){//test();printf("%lld\n",query(1,1,n,u,v,w));}}}return 0;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/384144.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/384144.shtml
英文地址，請注明出處：http://en.pswp.cn/news/384144.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！