一、题目
描述
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。
输入
第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
输出
对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
样例输入
7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7
样例输出
2
35
8
数据范围
数据编号 1 2 3 4 5 6 7 8 9 10
N = 10 1000 1000 10000 60000 70000 80000 90000 100000 100000
M = 10 1000 1000 10000 60000 70000 80000 90000 100000 100000
附上原题链接→_→http://www.lydsy.com/JudgeOnline/problem.php?id=1798
二、题目分析
显然我们需要使用线段树来解决这个问题，关于线段树大家可以参考这两篇blog（转载已征得原博主同意）
但这道题有点不一样的地方——对于每一个区间，有两种不同的修改方式。如果我们对于每一次不同的修改操作，都下放一次Lazy_Tag，Lazy_Tag对时间复杂度的优化程度就会被无限制放小。换言之，我们如果对于每次不同的修改都下放一次Lazy_Tag，我们一定会收获一个TLE。我们不妨转化一下思路：
有个神奇的东西叫乘法交换律，大致长这个样子→_→ (x*a+b)*c+d=x*a*c+(b*c+d)
那么对于每个加法修改，我们只需要像以往一样更新区间的add标记就好。而当我们遇到乘法修改时，我们除了需要更新mul标记之后，还需要将区间的add标记乘以乘数。下放标记时也需要注意，从根节点下放下来的乘法标记要乘到叶节点的add标记和mul标记上，再给叶节点的add标记加上根节点下放的add标记。
说的似乎有点乱诶2333各位看官老爷还是看代码吧_(:з」∠)_
三、代码实现
#include<stdio.h>
const int MAXN=;
int n,q;
int m;
int a[MAXN];
struct node
{
int l,r;
long long sum,add,mul;//区间和，加法标记，乘法标记
};
node tr[MAXN<<];
void build_tree(int x,int y,int i)//建树
{
tr[i].l=x;
tr[i].r=y;
tr[i].mul=;
if(x==y)tr[i].sum=a[x]%q;
else
{
int mid=(tr[i].l+tr[i].r)>>;
build_tree(x,mid,i<<);
build_tree(mid+,y,i<<|);
tr[i].sum=(tr[i<<].sum+tr[i<<|].sum)%q;
}
}
int val;
void push_down(int i)//标记下放
{
tr[i<<].add=(tr[i<<].add*tr[i].mul+tr[i].add)%q;
tr[i<<|].add=(tr[i<<|].add*tr[i].mul+tr[i].add)%q;
//叶节点add标记 = 叶节点add标记 * 根节点mul标记 + 根节点add标记
tr[i<<].mul=(tr[i<<].mul*tr[i].mul)%q;
tr[i<<|].mul=(tr[i<<|].mul*tr[i].mul)%q;
//叶节点mul标记 = 叶节点mul标记 * 根节点mul标记
tr[i<<].sum=((tr[i<<].sum*tr[i].mul)%q+tr[i].add*(tr[i<<].r-tr[i<<].l+))%q;
tr[i<<|].sum=((tr[i<<|].sum*tr[i].mul)%q+tr[i].add*(tr[i<<|].r-tr[i<<|].l+))%q;
//叶节点sum = 叶节点sum * 根节点mul标记 + 根节点add标记 * 叶节点区间长
tr[i].mul=;
tr[i].add=;
//标记归零
}
void update_tree_mul(int x,int y,int i)//乘法维护
{
if(x<=tr[i].l&&y>=tr[i].r)
{
tr[i].add=tr[i].add*val%q;
tr[i].mul=tr[i].mul*val%q;
tr[i].sum=tr[i].sum*val%q;
return;
}
if((tr[i].mul-)||tr[i].add)push_down(i);
int mid=(tr[i].l+tr[i].r)>>;
if(y<=mid)update_tree_mul(x,y,i<<);
else if(x>mid)update_tree_mul(x,y,i<<|);
else
{
update_tree_mul(x,y,i<<);
update_tree_mul(x,y,i<<|);
}
tr[i].sum=(tr[i<<].sum+tr[i<<|].sum)%q;
}
void update_tree_add(int x,int y,int i)//加法维护
{
if(x<=tr[i].l&&y>=tr[i].r)
{
tr[i].add=(tr[i].add+val)%q;
tr[i].sum=(tr[i].sum+val*(tr[i].r-tr[i].l+))%q;
return;
}
if((tr[i].mul-)||tr[i].add)push_down(i);
int mid=(tr[i].l+tr[i].r)>>;
if(y<=mid)update_tree_add(x,y,i<<);
else if(x>mid)update_tree_add(x,y,i<<|);
else
{
update_tree_add(x,y,i<<);
update_tree_add(x,y,i<<|);
}
tr[i].sum=(tr[i<<].sum+tr[i<<|].sum)%q;
}
long long query_tree(int x,int y,int i)//区间查询
{
if(x<=tr[i].l&&y>=tr[i].r)return tr[i].sum%q;
else
{
if((tr[i].mul-)||tr[i].add)push_down(i);
int mid=(tr[i].l+tr[i].r)>>;
if(y<=mid)return query_tree(x,y,i<<);
else if(x>mid)return query_tree(x,y,i<<|);
else return (query_tree(x,y,i<<)+query_tree(x,y,i<<|))%q;
}
}
int main()
{
scanf("%d%d",&n,&q);
int i;
for(i=;i<=n;++i)
scanf("%d",&a[i]);
build_tree(,n,);
scanf("%d",&m);
for(i=;i<=m;++i)
{
int num;
scanf("%d",&num);
if(num==)
{
int x,y;
scanf("%d%d%d",&x,&y,&val);
update_tree_mul(x,y,);
}
else if(num==)
{
int x,y;
scanf("%d%d%d",&x,&y,&val);
update_tree_add(x,y,);
}
else
{
int x,y;
scanf("%d%d",&x,&y);
printf("%lld",query_tree(x,y,)%q);
printf("\n");
}
}
return ;
}
bzoj1798-维护序列seq
四、Tips
不开long long见祖宗，十年OI一场空
弱弱地说一句，本蒟蒻码字也不容易，转载请注明出处http://www.cnblogs.com/Maki-Nishikino/p/5971027.html