题目描述
维护一个长度为 N 的序列 a,现在有三种操作:
1)给出参数 U,V,C,将 a[U],a[U+1],...,a[V-1],a[V] 都赋值为 C.
2)给出参数 U,V,C,对于区间 [U,V] 里的每个数 i,将 a[i]赋值为 max(a[i]+C,0).
3)给出参数 U,V,输出 a[U],a[U+1],...,a[V-1],a[V] 里值为 0 的数字个数.
输入
第一行包含两个正整数 N,M(1<=N,M<=300000),分别表示序列长度和操作个数.
第二行包含 N 个整数,其中第 i 个数表示 a[i](0<=a[i]<=10^9),描述序列的初始状态.
接下来 M 行描述 M 个操作,保证 1<=U<=V<=N,对于操作 1,0<=C<=10^9,对于操作 2,|C|<=10^9.
输出
输出若干行,每行一个整数,依次回答每个操作 3 的问题.
样例输入
5 3
6 4 6 6 4
2 1 5 -5
1 3 4 4
3 1 5
样例输出
2
题解
线段树区间最值操作
考虑到操作 1 的 $C\le 0$ ,因此 $0$ 只可能出现在最小值.所以要统计 $0$ 的个数,只需要统计:最小值是不是 0,最小值个数即可.
对于操作 1 直接区间赋值,操作 2 我们拆成两个操作:区间 + C 直接加,区间最大值操作参考 吉老师的 Segment tree Beats! ,维护最小值,严格次小值即可.
注意标记下传顺序:区间赋值 > 区间加 > 区间最大操作.
同样 ,区间最大操作可以不维护标记,直接下传最小值.
时间复杂度 $O(n\log^2 n)$ (吉老师表示 PPT 里的证明是萎的... 复杂度证明参考集训队论文)
#include <cstdio>
#include <algorithm>
#define N 1200010
#define inf 1ll << 62
#define lson l , mid , x << 1
#define rson mid + 1 , r , x << 1 | 1
using namespace std;
typedef long long ll;
ll mn[N] , se[N] , cov[N] , add[N];
int mc[N];
inline void pushup(int x)
{
int ls = x << 1 , rs = x << 1 | 1;
if(mn[ls] < mn[rs]) mn[x] = mn[ls] , mc[x] = mc[ls] , se[x] = min(se[ls] , mn[rs]);
if(mn[ls] > mn[rs]) mn[x] = mn[rs] , mc[x] = mc[rs] , se[x] = min(mn[ls] , se[rs]);
if(mn[ls] == mn[rs]) mn[x] = mn[ls] , mc[x] = mc[ls] + mc[rs] , se[x] = min(se[ls] , se[rs]);
}
inline void pushdown(int l , int r , int x)
{
int ls = x << 1 , rs = x << 1 | 1;
if(~cov[x])
{
int mid = (l + r) >> 1;
mn[ls] = cov[x] , mc[ls] = mid - l + 1 , se[ls] = inf , cov[ls] = cov[x] , add[ls] = 0;
mn[rs] = cov[x] , mc[rs] = r - mid , se[rs] = inf , cov[rs] = cov[x] , add[rs] = 0;
cov[x] = -1;
}
if(add[x])
{
mn[ls] += add[x] , se[ls] += add[x] , add[ls] += add[x];
mn[rs] += add[x] , se[rs] += add[x] , add[rs] += add[x];
add[x] = 0;
}
if(mn[ls] < mn[x]) mn[ls] = mn[x];
if(mn[rs] < mn[x]) mn[rs] = mn[x];
}
void build(int l , int r , int x)
{
cov[x] = -1;
if(l == r)
{
scanf("%lld" , &mn[x]) , mc[x] = 1 , se[x] = inf;
return;
}
int mid = (l + r) >> 1;
build(lson) , build(rson);
pushup(x);
}
void cover(int b , int e , ll c , int l , int r , int x)
{
if(b <= l && r <= e)
{
mn[x] = c , mc[x] = r - l + 1 , se[x] = inf , cov[x] = c , add[x] = 0;
return;
}
pushdown(l , r , x);
int mid = (l + r) >> 1;
if(b <= mid) cover(b , e , c , lson);
if(e > mid) cover(b , e , c , rson);
pushup(x);
}
void update(int b , int e , ll a , int l , int r , int x)
{
if(b <= l && r <= e)
{
mn[x] += a , se[x] += a , add[x] += a;
return;
}
pushdown(l , r , x);
int mid = (l + r) >> 1;
if(b <= mid) update(b , e , a , lson);
if(e > mid) update(b , e , a , rson);
pushup(x);
}
void vmax(int b , int e , int l , int r , int x)
{
if(mn[x] >= 0) return;
if(b <= l && r <= e && se[x] > 0)
{
mn[x] = 0;
return;
}
pushdown(l , r , x);
int mid = (l + r) >> 1;
if(b <= mid) vmax(b , e , lson);
if(e > mid) vmax(b , e , rson);
pushup(x);
}
int query(int b , int e , int l , int r , int x)
{
if(b <= l && r <= e) return mn[x] ? 0 : mc[x];
pushdown(l , r , x);
int mid = (l + r) >> 1 , ans = 0;
if(b <= mid) ans += query(b , e , lson);
if(e > mid) ans += query(b , e , rson);
return ans;
}
int main()
{
int n , m , opt , x , y;
ll z;
scanf("%d%d" , &n , &m);
build(1 , n , 1);
while(m -- )
{
scanf("%d%d%d" , &opt , &x , &y);
if(opt == 1) scanf("%lld" , &z) , cover(x , y , z , 1 , n , 1);
if(opt == 2) scanf("%lld" , &z) , update(x , y , z , 1 , n , 1) , vmax(x , y , 1 , n , 1);
if(opt == 3) printf("%d\n" , query(x , y , 1 , n , 1));
}
return 0;
}
来源: http://www.bubuko.com/infodetail-2474123.html