线段树懒标记好题 HDU4578
2024-08-29 20:47:36
（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
维护sum1[], sum2[], sum3[]分别为一次方、二次方、三次方的和
因为P只有1到3，(x+c)^2=(x^2)+(2*x*c+c^2)，即我们可以从一次方和的结果推出二次方的和的结果。同理，我们也可以根据一次方的和的结果，二次方和的结果推出三次方和的结果。这样，我们可以用几个懒标记去记录这几个操作。但是这题明白上面这点还是不够的，因为，这几种更新操作之间会相互影响，比如对一个区间进行操作3之后，那么操作1和2就失效了。因此在PushDown传递懒标记的时候，传递的顺序也是重要的。
#include <bits/stdc++.h>
#include <string.h>
#include <iostream>
#include <stdio.h>
#define pb push_back
#define fi first
#define se second
#define lson(r) (r<<1)
#define rson(r) ((r<<1)|1) using namespace std; typedef long long ll; const int MAXN = 1e5+;
const int MAXV = ;
const int MAXE = ;
const ll MOD = ;
ll sum1[MAXN << ];
ll sum2[MAXN << ];
ll sum3[MAXN << ];
ll addmark[MAXN << ];
ll setmark[MAXN << ];
ll mulmark[MAXN << ]; void pushDown(int root, int l, int r)
{
int num = (r-l+);
ll numr = num >> ;
ll numl = num - numr;
//思考了半天用-1还是不够优秀呀 只需要把另外优先级低的懒标记 标记的左右子即可
//修改了半天 哎哎哎 这道题目深入理解懒标记
if (setmark[root])
{
ll setval = setmark[root];
//cout << "set" << l << " " << r << " " << setmark[root] << endl;
sum1[lson(root)] = (numl*setval) % MOD;
sum1[rson(root)] = (numr*setval) % MOD;
sum2[lson(root)] = (numl*setval*setval) % MOD;
sum2[rson(root)] = (numr*setval*setval) % MOD;
sum3[lson(root)] = (numl*setval*setval*setval) % MOD;
sum3[rson(root)] = (numr*setval*setval*setval) % MOD;
setmark[lson(root)] = setval;
setmark[rson(root)] = setval;
addmark[lson(root)] = addmark[rson(root)] = ;
mulmark[lson(root)] = mulmark[rson(root)] = ;
setmark[root] = ;
}
if (mulmark[root] != )
{
ll mulval = mulmark[root];
sum1[lson(root)] = (sum1[lson(root)]*mulval) % MOD;
sum1[rson(root)] = (sum1[rson(root)]*mulval) % MOD;
sum2[lson(root)] = (sum2[lson(root)]*mulval*mulval) % MOD;
sum2[rson(root)] = (sum2[rson(root)]*mulval*mulval) % MOD;
sum3[lson(root)] = (sum3[lson(root)]*mulval*mulval*mulval) % MOD;
sum3[rson(root)] = (sum3[rson(root)]*mulval*mulval*mulval) % MOD;
mulmark[lson(root)] = (mulmark[lson(root)]*mulval) % MOD;
mulmark[rson(root)] = (mulmark[rson(root)]*mulval) % MOD;
addmark[lson(root)] = (addmark[lson(root)]*mulval) % MOD;
addmark[rson(root)] = (addmark[rson(root)]*mulval) % MOD;
mulmark[root] = ;
}
if (addmark[root])
{
ll addval = addmark[root];
sum3[lson(root)] = ((sum3[lson(root)]+numl*addval*addval*addval)%MOD+(*sum2[lson(root)]*addval+*sum1[lson(root)]*addval*addval)%MOD)%MOD;
sum3[rson(root)] = ((sum3[rson(root)]+numr*addval*addval*addval)%MOD+(*sum2[rson(root)]*addval+*sum1[rson(root)]*addval*addval)%MOD)%MOD;
sum2[lson(root)] = (((sum2[lson(root)] + numl*addval*addval) % MOD) + (*sum1[lson(root)]*addval)) % MOD;
sum2[rson(root)] = (((sum2[rson(root)] + numr*addval*addval) % MOD) + (*sum1[rson(root)]*addval)) % MOD;
sum1[lson(root)] = (sum1[lson(root)] + numl * addval) % MOD;
sum1[rson(root)] = (sum1[rson(root)] + numr * addval) % MOD;
addmark[lson(root)] = (addmark[lson(root)] + addval) % MOD;
addmark[rson(root)] = (addmark[rson(root)] + addval) % MOD;
addmark[root] = ;
}
}
void update(int root, int l, int r, int ul, int ur, int mathod, ll val)
{
if (l > ur || r < ul) return ;
if (l >= ul && r <= ur)
{
ll num = r-l+;
if (mathod == )
{
//cout << l << " " << r << " " << val << endl;
setmark[root] = val%MOD;
addmark[root] = ;
mulmark[root] = ;
sum1[root] = (num*val) % MOD;
sum2[root] = (num*val*val) % MOD;
sum3[root] = (num*val*val*val) % MOD;
}
else if (mathod == )
{
mulmark[root] = (mulmark[root]*val)%MOD;
addmark[root] = (val*addmark[root])%MOD;
sum1[root] = (sum1[root]*val) % MOD;
sum2[root] = (sum2[root]*val*val) % MOD;
sum3[root] = (sum3[root]*val*val*val) % MOD;
}
else if (mathod == )
{ //cout << l << " " << r << " " << sum1[root] << endl;
addmark[root] = (addmark[root]+val)%MOD;
sum3[root] = ((sum3[root]+num*val*val*val)%MOD+(*sum2[root]*val+*sum1[root]*val*val)%MOD)%MOD;
sum2[root] = ((sum2[root] + num*val*val) % MOD + (*sum1[root]*val)) % MOD;
sum1[root] = (sum1[root] + num * val) % MOD;
//cout << l << " " << r << " " << sum1[root] << endl;
}
return ;
}
pushDown(root, l, r);
int mid = (l+r) >> ;
if (ul <= mid) update(lson(root), l, mid, ul, ur, mathod, val);
if (ur > mid) update(rson(root), mid+, r, ul, ur, mathod, val);
sum1[root] = (sum1[lson(root)] + sum1[rson(root)]) % MOD;
sum2[root] = (sum2[lson(root)] + sum2[rson(root)]) % MOD;
sum3[root] = (sum3[lson(root)] + sum3[rson(root)]) % MOD;
//cout << l << " " << r << " " << sum1[root] << endl;
} int cnt = ;
ll query(int root, int l, int r, int ql, int qr, int p)
{
// cout << l << " " << r << endl;
if (l > qr || r < ql) return ;
if (l >= ql && r <= qr)
{
if (p == ) return sum1[root];
else if (p == ) return sum2[root];
else if (p == ) return sum3[root];
}
pushDown(root, l, r);
int mid = (l+r) >> ;
ll res = ;
if (ql <= mid) res = (res + query(lson(root), l, mid, ql, qr, p)) % MOD;
if (qr >= mid+) res = (res + query(rson(root), mid+, r, ql, qr, p)) % MOD;
return res;
}
int n, m;
int main()
{
// freopen("in.txt", "r", stdin);
while (~scanf("%d%d", &n, &m))
{
for(int i = ; i < MAXN << ; i++) mulmark[i] = ;
if (!n && !m) break;
memset(addmark, , sizeof(addmark));
//memset(mulmark, 1, sizeof(mulmark));
memset(setmark, , sizeof(setmark));
memset(sum1, , sizeof(sum1));
memset(sum2, , sizeof(sum2));
memset(sum3, , sizeof(sum3));
for (int i = ; i < m; i++)
{
int op, l, r, c;
scanf("%d%d%d%d", &op, &l, &r, &c);
if (op == )
{
update(, , n, l, r, , c);
}
else if (op == )
{
update(, , n, l, r, , c);
}
else if (op == )
{
update(, , n, l, r, , c);
}
else
{
ll ans = query(, , n, l, r, c);
cout << ans << endl;
}
}
}
return ;
}
最新文章
- URL重写 urlrouting
- fuse入门
- React 随笔二
- ButterKnife--View注入框架
- jQuery $.fn 方法扩展~
- 图结构练习——最小生成树(kruskal算法（克鲁斯卡尔）)
- Wordnet的一些简单使用
- c#部分---需要实例化的内容；
- openerp学习笔记 视图更新时删除已存在的菜单或其他对象
- WPF中PasswordBox控件无法绑定Password属性解决办法
- Android -- Looper.prepare()和Looper.loop() —深度版
- springmvc3.1.1+hibernate4
- 改写BlogEngine.NET头像上传实现方式（使用baidu.flash.avatarMaker）
- 整理一点与排列组合有关的问题[组合数 Stirling数 Catalan数]
- SpringBoot+Angular2 开发环境搭建
- Composer更新慢的解决方案
- python2 python3区别（续）
- Ubuntu 14.04 安装 CUDA 问题及解决
- UI自动化（三）css优先级
- js运行机制