http://acm.hdu.edu.cn/showproblem.php?pid=4578
Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 65535/65536 K (Java/Others)
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.
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.
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
Sample Output
Source
题意：
给你一个数组，初始值为零，有四种操作:
（1）"1 x y c",代表 把区间 [x,y] 上的值全部加c
（2）"2 x y c",代表 把区间 [x,y] 上的值全部乘以c
（3）"3 x y c" 代表 把区间 [x,y]上的值全部赋值为c
（4）"4 x y p" 代表 求区间 [x,y] 上值的p次方和1<=p<=3
典型的线段树区间更新，不过是增加了多种操作。
多种操作时，更新的时候各个懒惰标记之间更新顺序是有讲究的，而且各个懒惰标记之间往下推的时候也是能够互相影响。
这道题思路简单，但是挺复杂的，很考验编码能力。
注意：当线段树有多个懒惰标记时，一定要考虑到懒惰标记之间的互相影响。
解法一：
使用懒惰标记标记的是整个区间是否为同一个状态
并且每次更新的时候回溯状态 即如果左右子结点都是相同状态 则在线段树的父节点上更新标记这一统一状态
如此一来，只需要在计算区间的时候先判断区间内状态是否相同，然后进行区间内的更新操作即可 因为区间内都为统一状态。
写法一（2433MS、5500k）：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <math.h>
const int INF=0x3f3f3f3f;
typedef long long LL;
const int mod=1e4+;
const int maxn=1e5+;
using namespace std; struct SegTree_node
{
int l;
int r;
int lazy;//懒惰标记 但是标记的是整个区间是否为同一个状态
int num;
}SegTree[maxn<<]; int n,m; void Build(int l,int r,int rt)
{
SegTree[rt].l=l;
SegTree[rt].r=r;
SegTree[rt].lazy=;
SegTree[rt].num=;
if(l==r)
return ;
int mid=(l+r)>>;
Build(l,mid,rt<<);
Build(mid+,r,rt<<|);
} void PushUp(int rt)
{
if(SegTree[rt<<].lazy&&SegTree[rt<<|].lazy&&SegTree[rt<<].num==SegTree[rt<<|].num)
{//可以下放，因为我们每次都是先递归下去更改的子节点的值，所以在更改后将子节点的值赋给父节点。
SegTree[rt].lazy=;
SegTree[rt].num=SegTree[rt<<].num;
}
else//子节点的懒标记不同时为0或子节点值都不一样，肯定区间值不一样
SegTree[rt].lazy=;
} void PushDown(int rt)//下放懒标记
{
if(SegTree[rt].l==SegTree[rt].r)
return ;
if(SegTree[rt].lazy)
{
SegTree[rt<<].lazy=SegTree[rt<<|].lazy=;
SegTree[rt<<].num=SegTree[rt<<|].num=SegTree[rt].num;
SegTree[rt].lazy=;
}
} void Update(int L,int R,int C,int op,int rt)
{
int l=SegTree[rt].l;
int r=SegTree[rt].r;
if(L<=l&&R>=r&&SegTree[rt].lazy)//这里要注意，一定要保证现在区间值都一样才能修改。
{
if(op==)
SegTree[rt].num=(SegTree[rt].num+C)%mod;
else if(op==)
SegTree[rt].num=(SegTree[rt].num*C)%mod;
else
SegTree[rt].num=C;
return ;
}
PushDown(rt);
int mid=(l+r)>>;
if(L<=mid)
Update(L,R,C,op,rt<<);
if(R>mid)
Update(L,R,C,op,rt<<|);
PushUp(rt);
} int Query(int L,int R,int P,int rt)
{
int l=SegTree[rt].l;
int r=SegTree[rt].r;
if(L<=l&&R>=r&&SegTree[rt].lazy)//要保证区间值一样才满足sum=(r-l+1)*a[rt]^p;这个式子
{
int ans=;
for(int i=;i<=P;i++)
ans=(ans*SegTree[rt].num)%mod;
ans=(ans*(r-l+))%mod;
return ans;
}
PushDown(rt);
int ans=;
int mid=(l+r)>>;
if(L<=mid)
ans+=Query(L,R,P,rt<<);
if(R>mid)
ans+=Query(L,R,P,rt<<|);
return ans%mod;
} int main()
{
while(~scanf("%d %d",&n,&m)&&(n||m))
{
Build(,n,);
for(int i=;i<=m;i++)
{
int op,x,y,c;
scanf("%d %d %d %d",&op,&x,&y,&c);
if(op>=&&op<=)//更新操作
Update(x,y,c,op,);
else if(op==)//查询操作
{
printf("%d\n",Query(x,y,c,));
}
}
}
return ;
}
写法一的改进（2137MS、5496k）：
只有在二分子区间时写法不同
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <math.h>
const int INF=0x3f3f3f3f;
typedef long long LL;
const int mod=1e4+;
//const int mod=1e9+7;
//const double PI=acos(-1);
const int maxn=1e5+;
using namespace std;
//ios::sync_with_stdio(false);
// cin.tie(NULL); struct SegTree_node
{
int l;
int r;
int lazy;//懒惰标记 但是标记的是整个区间是否为同一个状态
int num;
}SegTree[maxn<<]; int n,m,ans; void Build(int l,int r,int rt)
{
SegTree[rt].l=l;
SegTree[rt].r=r;
SegTree[rt].lazy=;
SegTree[rt].num=;
if(l==r)
return ;
int mid=(l+r)>>;
Build(l,mid,rt<<);
Build(mid+,r,rt<<|);
} void PushUp(int rt)
{
if(SegTree[rt<<].lazy&&SegTree[rt<<|].lazy&&SegTree[rt<<].num==SegTree[rt<<|].num)
{//可以下放，因为我们每次都是先递归下去更改的子节点的值，所以在更改后将子节点的值赋给父节点。
SegTree[rt].lazy=;
SegTree[rt].num=SegTree[rt<<].num;
}
else//子节点的懒标记不同时为0或子节点值都不一样，肯定区间值不一样
SegTree[rt].lazy=;
} void PushDown(int rt)
{
if(SegTree[rt].l==SegTree[rt].r)
return ;
if(SegTree[rt].lazy)
{
SegTree[rt<<].lazy=SegTree[rt<<|].lazy=;
SegTree[rt<<].num=SegTree[rt<<|].num=SegTree[rt].num;
SegTree[rt].lazy=;
}
} void Update(int L,int R,int C,int op,int rt)
{
int l=SegTree[rt].l;
int r=SegTree[rt].r;
if(L==l&&R==r&&SegTree[rt].lazy)//这里要注意，一定要保证现在区间值都一样才能修改。
{
if(op==)
SegTree[rt].num=(SegTree[rt].num+C)%mod;
else if(op==)
SegTree[rt].num=(SegTree[rt].num*C)%mod;
else
SegTree[rt].num=C;
return ;
}
PushDown(rt);
int mid=(l+r)>>;
if(R<=mid)
Update(L,R,C,op,rt<<);
else if(L>mid)
Update(L,R,C,op,rt<<|);
else
{
Update(L,mid,C,op,rt<<);
Update(mid+,R,C,op,rt<<|);
}
PushUp(rt);
} void Query(int L,int R,int P,int rt)
{
int l=SegTree[rt].l;
int r=SegTree[rt].r;
if(L==l&&R==r&&SegTree[rt].lazy)//要保证区间值一样才满足sum=(r-l+1)*a[rt]^p;这个式子
{
int tem=;
for(int i=;i<=P;i++)
tem=(tem*SegTree[rt].num)%mod;
tem=(tem*(r-l+))%mod;
ans=(ans+tem)%mod;
return ;
}
PushDown(rt);
int mid=(l+r)>>;
if(R<=mid)
Query(L,R,P,rt<<);
else if(L>mid)
Query(L,R,P,rt<<|);
else
{
Query(L,mid,P,rt<<);
Query(mid+,R,P,rt<<|);
}
} int main()
{
while(~scanf("%d %d",&n,&m)&&(n||m))
{
Build(,n,);
ans=;
for(int i=;i<=m;i++)
{
int op,x,y,c;
scanf("%d %d %d %d",&op,&x,&y,&c);
if(op>=&&op<=)//更新操作
Update(x,y,c,op,);
else if(op==)//查询操作
{
ans=;
Query(x,y,c,);
printf("%d\n",ans);
}
}
}
return ;
}
解法二：
用线段树维护里面的值都相等的区间 ,那么这个区间的所需答案为(r-l+1)*(tree[v].eq)^q
用add表示加号标记，mul表示乘，eq表示等，无疑在向下更新的时候等号的优先级应该最高，先处理等号标记，并把加号和乘号标记置为0和1（初始值），然后重点来了，在处理乘号标记的时候，如果发现子区间有等号标记，直接修改等号标记，否则先将子区间pushdwon一下清空标记，再进行该子区间标记，加号同理，如果子区间有等号标记，就修改等号标记，否则将子区间pushdown清空标记，再将该子区间标记，所有操作完都要清空当前区间标记，然后修改的时候也差不多，先检查该区间有没有等号标记，有的话直接修改等号标记，否则pushdown清空该区间标记，再进行各种标记，查询的时候是整个算法的精髓，他是查询到要查询区间的子区间的等号标记不为初始标记，即为一段相同的数字的时候停止，然后返回该区间的值，进行各个子区间累加，得出答案。
写法二（2574MS、6516k）：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <math.h>
const int INF=0x3f3f3f3f;
typedef long long LL;
const int mod=1e4+;
const int maxn=1e5+;
using namespace std; struct SegTree_node
{
int l;
int r;
int add;//表示加号标记
int mul;//表示乘号标记
int eq; //表示等号标记
}SegTree[maxn<<]; int n,m; void Build(int l,int r,int rt)
{
SegTree[rt].l=l;
SegTree[rt].r=r;
SegTree[rt].add=;
SegTree[rt].mul=;
SegTree[rt].eq=-;
if(l==r)
{
SegTree[rt].eq=;//最底层要赋值为0
return ;
}
int mid=(l+r)>>;
Build(l,mid,rt<<);
Build(mid+,r,rt<<|);
} void PushDown(int rt)
{
int l=SegTree[rt].l;
int r=SegTree[rt].r;
if(l==r)//没有子区间了不用向下更新了
return ;
if(SegTree[rt].eq!=-)//处理等号
{
SegTree[rt<<].eq=SegTree[rt<<|].eq=SegTree[rt].eq;//更新子区间等号标记
SegTree[rt<<].add=SegTree[rt<<|].add=;//还原子区间乘法标记
SegTree[rt<<].mul=SegTree[rt<<|].mul=;//清空子区间加乘标记
SegTree[rt].eq=-;//记得还原
return ;
}
if(SegTree[rt].mul!=)//处理乘号
{
if(SegTree[rt<<].eq!=-)//如果子区间有等号标记，直接修改等号标记
SegTree[rt<<].eq=(SegTree[rt<<].eq*SegTree[rt].mul)%mod;
else//否则清空该子区间标记，进行子区间标记
{
PushDown(rt<<);
SegTree[rt<<].mul=(SegTree[rt<<].mul*SegTree[rt].mul)%mod;
}
if(SegTree[rt<<|].eq!=-)//同理处理右区间
SegTree[rt<<|].eq=(SegTree[rt<<|].eq*SegTree[rt].mul)%mod;
else
{
PushDown(rt<<|);
SegTree[rt<<|].mul=(SegTree[rt<<|].mul*SegTree[rt].mul)%mod;
}
SegTree[rt].mul=;//记得还原
}
if(SegTree[rt].add)//处理加号标记，和上面同理处理
{
if(SegTree[rt<<].eq!=-)
SegTree[rt<<].eq=(SegTree[rt<<].eq+SegTree[rt].add)%mod;
else
{
PushDown(rt<<);
SegTree[rt<<].add=(SegTree[rt<<].add+SegTree[rt].add)%mod;
}
if(SegTree[rt<<|].eq!=-)
SegTree[rt<<|].eq=(SegTree[rt<<|].eq+SegTree[rt].add)%mod;
else
{
PushDown(rt<<|);
SegTree[rt<<|].add=(SegTree[rt<<|].add+SegTree[rt].add)%mod;
}
SegTree[rt].add=;//记得还原
}
} void Update(int L,int R,int C,int op,int rt)
{
int l=SegTree[rt].l;
int r=SegTree[rt].r;
if(L<=l&&R>=r)
{
if(op==)
{
SegTree[rt].add=;
SegTree[rt].mul=;
SegTree[rt].eq=C;
return ;
}
if(SegTree[rt].eq!=-)//如果有等号标记，就直接修改等号标记
{
if(op==)
SegTree[rt].eq=(SegTree[rt].eq+C)%mod;
else if(op==)
SegTree[rt].eq=(SegTree[rt].eq*C)%mod;
}
else
{
PushDown(rt);//否则清空该区间，进行标记
if(op==)
SegTree[rt].add=(SegTree[rt].add+C)%mod;
else if(op==)
SegTree[rt].mul=(SegTree[rt].mul*C)%mod;
}
return ;
}
PushDown(rt);//向下传递状态
int mid=(l+r)>>;
if(L<=mid)
Update(L,R,C,op,rt<<);
if(R>mid)
Update(L,R,C,op,rt<<|);
} int Query(int L,int R,int P,int rt)//查询
{
int l=SegTree[rt].l;
int r=SegTree[rt].r;
if(L<=l&&R>=r&&SegTree[rt].eq!=-)//查到是查询区间的子区间且一段全为相同的数
{
int ans=;
for(int i=;i<=P;i++)
ans=(ans*SegTree[rt].eq)%mod;
return (ans*(r-l+)) %mod;//注意要乘上长度
}
PushDown(rt);
int mid=(l+r)>>;
if(R<=mid)
return Query(L,R,P,rt<<);
else if(L>mid)
return Query(L,R,P,rt<<|);
else
return (Query(L,mid,P,rt<<)+Query(mid+,R,P,rt<<|))%mod;
} int main()
{
while(~scanf("%d %d",&n,&m)&&(n||m))
{
Build(,n,);
for(int i=;i<=m;i++)
{
int op,x,y,c;
scanf("%d %d %d %d",&op,&x,&y,&c);
if(op>=&&op<=)//更新操作
Update(x,y,c,op,);
else if(op==)//查询操作
printf("%d\n",Query(x,y,c,)%mod);
}
}
return ;
}