hihocoder1080 更为复杂的买卖房屋姿势

思路:

线段树区间修改,需要使用两个懒标记set和add。处理好两个标记的优先级即可(set之前的set和add是没有作用的)。

实现:

 #include <bits/stdc++.h>
using namespace std; const int N = ; int tree[N << ], lazy_set[N << ], lazy_add[N << ], a[N], n, q; void build(int num, int l, int r)
{
if (l == r) { tree[num] = a[l]; return; }
int m = l + r >> ;
build(num << , l, m);
build(num << | , m + , r);
tree[num] = tree[num << ] + tree[num << | ];
} void pushdown(int num, int cl, int cr)
{
if (lazy_set[num])
{
tree[num << ] = lazy_set[num] * cl;
tree[num << | ] = lazy_set[num] * cr;
lazy_set[num << ] = lazy_set[num];
lazy_set[num << | ] = lazy_set[num];
lazy_add[num << ] = ;
lazy_add[num << | ] = ;
lazy_set[num] = ;
}
if (lazy_add[num])
{
tree[num << ] += lazy_add[num] * cl;
tree[num << | ] += lazy_add[num] * cr;
lazy_add[num << ] += lazy_add[num];
lazy_add[num << | ] += lazy_add[num];
lazy_add[num] = ;
}
} void update(int num, int l, int r, int x, int y, int p, int t)
{
if (x <= l && y >= r)
{
if (t == )
{
tree[num] += (r - l + ) * p;
lazy_add[num] += p;
}
else
{
tree[num] = (r - l + ) * p;
lazy_set[num] = p;
lazy_add[num] = ;
}
return;
}
int m = l + r >> ;
pushdown(num, m - l + , r - m);
if (x <= m) update(num << , l, m, x, y, p, t);
if (y >= m + ) update(num << | , m + , r, x, y, p, t);
tree[num] = tree[num << ] + tree[num << | ];
} int query(int num, int l, int r, int x, int y)
{
if (x <= l && y >= r) return tree[num];
int m = l + r >> ;
pushdown(num, m - l + , r - m);
int ans = ;
if (x <= m) ans += query(num << , l, m, x, y);
if (y >= m + ) ans += query(num << | , m + , r, x, y);
return ans;
} int main()
{
ios::sync_with_stdio(false);
cin >> n >> q;
for (int i = ; i <= n + ; i++) cin >> a[i];
build(, , n + );
int x, y, t, p;
for (int i = ; i <= q; i++)
{
cin >> t >> x >> y >> p;
x++; y++;
update(, , n + , x, y, p, t);
cout << query(, , n + , , n + ) << endl;
}
return ;
}
上一篇:HihoCoder1080 更为复杂的买卖房屋姿势(线段树+多重lazy)


下一篇:使用fiddler手机抓包