题目大意

给定一个数列，支持区间加一个数和区间取 \(max\)，询问单点询问数值和它被更改的次数
思路

模板的吉司机线段树

维护区间最小值和严格次小值以及最小值的个数

针对询问维护区间和以及区间修改次数

那么我们可以 \(O(n\log^2 n)\) 解决问题
\(Code\)

#include<cstdio>

#include<iostream>

#define ls (k << 1)

#define rs (ls | 1)

using namespace std;

typedef long long LL;

const int N = 1e5 + 5 , INF = 0x3f3f3f3f;

int n , m , a[N];

struct segment{

	LL sum , ch_cnt;

	int mn , sec , mn_cnt , tag_add , tag_max , add_cnt , max_cnt;

}seg[N << 2];

inline void pushup(int k)

{

	seg[k].sum = seg[ls].sum + seg[rs].sum;

	seg[k].ch_cnt = seg[ls].ch_cnt + seg[rs].ch_cnt;

	seg[k].mn = min(seg[ls].mn , seg[rs].mn);

	if (seg[ls].mn == seg[rs].mn)

	{

		seg[k].mn_cnt = seg[ls].mn_cnt + seg[rs].mn_cnt;

		seg[k].sec = min(seg[ls].sec , seg[rs].sec);

	}

	else if (seg[ls].mn < seg[rs].mn)

	{

		seg[k].mn_cnt = seg[ls].mn_cnt;

		seg[k].sec = min(seg[ls].sec , seg[rs].mn);;

	}

	else {

		seg[k].mn_cnt = seg[rs].mn_cnt;

		seg[k].sec = min(seg[ls].mn , seg[rs].sec);

	}

}

inline void push_add(int l , int r , int k , int cnt , int v)

{

	seg[k].sum += (r - l + 1LL) * v , seg[k].tag_add += v , seg[k].mn += v;

	seg[k].add_cnt += cnt , seg[k].ch_cnt += (r - l + 1LL) * cnt;

	if (seg[k].sec < INF) seg[k].sec += v;

	if (seg[k].tag_max > -INF) seg[k].tag_max += v;

}

inline void push_max(int k , int cnt , int v)

{

	if (v <= seg[k].mn) return;

	seg[k].sum += 1LL * (v - seg[k].mn) * seg[k].mn_cnt , seg[k].mn = seg[k].tag_max = v;

	seg[k].max_cnt += cnt , seg[k].ch_cnt += 1LL * seg[k].mn_cnt * cnt;

}

inline void pushdown(int l , int r , int k)

{

	int mid = (l + r) >> 1;

	if (seg[k].add_cnt)

	{

		push_add(l , mid , ls , seg[k].add_cnt , seg[k].tag_add);

		push_add(mid + 1 , r , rs , seg[k].add_cnt , seg[k].tag_add);

		seg[k].add_cnt = seg[k].tag_add = 0;

	}

	if (seg[k].max_cnt)

	{

		push_max(ls , seg[k].max_cnt , seg[k].tag_max);

		push_max(rs , seg[k].max_cnt , seg[k].tag_max);

		seg[k].max_cnt = 0 , seg[k].tag_max = -INF;

	}

}

inline void build(int l , int r , int k)

{

	seg[k].tag_max = -INF;

	if (l == r)

	{

		seg[k].sum = seg[k].mn = a[l];

		seg[k].mn_cnt = 1 , seg[k].sec = INF;

		return;

	}

	int mid = (l + r) >> 1;

	build(l , mid , ls) , build(mid + 1 , r , rs);

	pushup(k);

}

inline void update_add(int l , int r , int k , int x , int y , int c)

{

	if (x <= l && r <= y)

	{

		push_add(l , r , k , c == 0 ? 0 : 1 , c);

		return;

	}

	pushdown(l , r , k);

	int mid = (l + r) >> 1;

	if (x <= mid) update_add(l , mid , ls , x , y , c);

	if (y > mid) update_add(mid + 1 , r , rs , x , y , c);

	pushup(k);

}

inline void update_max(int l , int r , int k , int x , int y , int c)

{

	if (seg[k].mn >= c) return;

	if (x <= l && r <= y && seg[k].sec > c)

	{

		push_max(k , 1 , c);

		return;

	}

	pushdown(l , r , k);

	int mid = (l + r) >> 1;

	if (x <= mid) update_max(l , mid , ls , x , y , c);

	if (y > mid) update_max(mid + 1 , r , rs , x , y , c);

	pushup(k);

}

inline int query_sum(int l , int r , int k , int x)

{

	if (l == r && l == x) return seg[k].sum;

	pushdown(l , r , k);

	int mid = (l + r) >> 1;

	if (x <= mid) return query_sum(l , mid , ls , x);

	else return query_sum(mid + 1 , r , rs , x);

}

inline int query_ch_cnt(int l , int r , int k , int x)

{

	if (l == r && l == x) return seg[k].ch_cnt;

	pushdown(l , r , k);

	int mid = (l + r) >> 1;

	if (x <= mid) return query_ch_cnt(l , mid , ls , x);

	else return query_ch_cnt(mid + 1 , r , rs , x);

}

int main()

{

	scanf("%d" , &n);

	for(register int i = 1; i <= n; i++) scanf("%d" , &a[i]);

	build(1 , n , 1);

	scanf("%d" , &m);

	char op[2];

	int l , r , c;

	for(; m; m--)

	{

		scanf("%s" , op);

		if (op[0] == 'A')

		{

			scanf("%d%d%d" , &l , &r , &c);

			update_add(1 , n , 1 , l , r , c);

		}

		else if (op[0] == 'M')

		{

			scanf("%d%d%d" , &l , &r , &c);

			update_max(1 , n , 1 , l , r , c);

		}

		else{

			scanf("%d" , &c);

			printf("%d %d\n" , query_sum(1 , n , 1 , c) , query_ch_cnt(1 , n , 1 , c));

		}

	}

}
巴特西

JZOJ 3992.Christmas

题目大意

思路

\(Code\)

最新文章

热门文章
