Yuanfang is puzzled with the question below:
There are n integers, a 1, a 2, …, a n. The initial values of them are 0. There are four kinds of operations.
Operation 1: Add c to each number between a x and a y inclusive. In other words, do transformation a k<---a k+c, k = x,x+1,…,y.
Operation 2: Multiply c to each number between a x and a y inclusive. In other words, do transformation a k<---a k×c, k = x,x+1,…,y.
Operation 3: Change the numbers between a x and a y to c, inclusive. In other words, do transformation a k<---c, k = x,x+1,…,y.
Operation 4: Get the sum of p power among the numbers between a x and a y inclusive. In other words, get the result of a x p+a x+1 p+…+a y 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 自己一直對線段樹的掌握不夠精通
線段樹入門較慢 需要花費精力去刷一些題目
主要在假期做題目的時候 獨立思考較少
最近要找個時間 補一補線段樹題目
本題卡時間卡的很近
主要考察的就是對于線段樹各種操作的熟悉性
顯然更新時将每個單點更新一次不現實
是以就用flag數組記錄所有一樣的值
區間内所有的值相同 就把flag設為1
以此來優化時間
#include<cstdio>
#include<iostream>
#define fla tree[root].flag
#define lson tree[root*2]
#define rson tree[root*2+1]
using namespace std;
const int MAX=100005;
const long long mod=10007;
struct node
{
long long num;
bool flag;
}tree[MAX*4] ;
int n,m;
int temp1,temp2,temp3,temp4;
long long ans;
void build(int l,int r,int root)
{
tree[root].num=0;
tree[root].flag=1;
if(l==r) return ;
int mid=(l+r)/2;
build(l,mid,root*2);
build(mid+1,r,root*2+1);
}
//當一個節點的全部值相等時 flag=1
void update(int l,int r,int root)
{
if(temp2<=l&&r<=temp3&&(fla==1||temp1==3))//全部相同 一起更新
{
if(temp1==1) tree[root].num=(tree[root].num+temp4)%mod;
if(temp1==2) tree[root].num=(tree[root].num*temp4)%mod;
if(temp1==3) tree[root].num=temp4%mod,fla=1;
return ;
}
if(fla==1)
{
fla=0;
lson.flag=1;
rson.flag=1;
lson.num=tree[root].num;
rson.num=tree[root].num;
}
int mid=(l+r)/2;
if(temp2<=mid) update(l,mid,root*2);
if(temp3>mid) update(mid+1,r,root*2+1);
if(!lson.flag||!rson.flag)//回溯過程維護flag
{
fla=0;
}
else
{
if(lson.num==rson.num) fla=1,tree[root].num=lson.num;
else fla=0;
}
return ;
}
void query(int l,int r,int root)
{
if(temp2<=l&&temp3>=r&&fla==1)//子區間
{
long long tmp=1;
for(int i=1;i<=temp4;i++)
{
tmp=(tmp*tree[root].num)%mod;
}
ans=(ans+(tmp*(r-l+1))%mod)%mod;
return ;
}
if(fla==1)
{
lson.flag=1;rson.flag=1;
lson.num=tree[root].num;
rson.num=tree[root].num;
}
int mid=(l+r)/2;
if(temp2<=mid) query(l,mid,root*2);
if(temp3>mid) query(mid+1,r,root*2+1);
return ;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0&&m==0) break;
build(1,n,1);
while(m--)
{
scanf("%d%d%d%d",&temp1,&temp2,&temp3,&temp4);
if(temp1<=3)
{
update(1,n,1);
}
else
{
ans=0;
query(1,n,1);
printf("%lld
",ans);
}
}
}
}
//caowenbo