P2572 [SCOI2010] 序列操作 Solution

Description

给定 01 01 01 序列 a = ( a 1 , a 2 , ⋯   , a n ) a=(a_1,a_2,\cdots,a_n) a=(a1,a2,,an),并定义 f ( l , r ) = [ ( ∑ i = l r a i ) = r − l + 1 ] f(l,r)=[(\sum\limits_{i=l}^r a_i)=r-l+1] f(l,r)=[(i=lrai)=rl+1].
执行 m m m 个操作,分五种:

  • reset ⁡ ( l , r ) \operatorname{reset}(l,r) reset(l,r):对每个 i ∈ [ l , r ] i\in[l,r] i[l,r] 执行 a i ← 0 a_i\gets 0 ai0.
  • set ⁡ ( l , r ) \operatorname{set}(l,r) set(l,r):对每个 i ∈ [ l , r ] i\in[l,r] i[l,r] 执行 a i ← 1 a_i\gets 1 ai1.
  • negate ⁡ ( l , r ) \operatorname{negate}(l,r) negate(l,r):对每个 i ∈ [ l , r ] i\in[l,r] i[l,r] 执行 a i ← 1 − a i a_i\gets 1-a_i ai1ai.
  • sum ⁡ ( l , r ) \operatorname{sum}(l,r) sum(l,r):求 ∑ i = l r a i \sum\limits_{i=l}^r a_i i=lrai.
  • gss ⁡ ( l , r ) \operatorname{gss}(l,r) gss(l,r):求 max ⁡ [ s , t ] ∈ [ l , r ] ( t − s + 1 ) × f ( s , t ) \max\limits_{[s,t]\in[l,r]}(t-s+1)\times f(s,t) [s,t][l,r]max(ts+1)×f(s,t).

Limitations

1 ≤ n , m ≤ 1 0 5 1\le n,m\le 10^5 1n,m105
1 ≤ l ≤ r ≤ n 1\le l\le r\le n 1lrn
1 s , 128 MB 1\text{s},128\text{MB} 1s,128MB

Solution

线段树做法.
节点上维护 S = ( sum , lsum , rsum , tsum , len ) S=(\textit{sum},\textit{lsum},\textit{rsum},\textit{tsum},\textit{len}) S=(sum,lsum,rsum,tsum,len),用类似最大子段和的方法更新.
由于要取反, 0 0 0 1 1 1 都分别需要一个 S S S(下记为 S 0 S_0 S0 S 1 S_1 S1) .
然后需要标记 T T T,显然 T = ( cov , rev ) T=(\textit{cov},\textit{rev}) T=(cov,rev)(分别为赋值和取反标记)

  • 考虑赋值,我们直接将 S c o v S_{cov} Scov 全部填上 len \textit{len} len S 1 − c o v S_{1-cov} S1cov 全部清零( len \textit{len} len 要不变)
  • 考虑翻转,我们直接交换 S 0 S_0 S0 S 1 S_1 S1.

然后需要考虑 T + T T+T T+T

  • 赋值可以直接打标记.
  • 对于取反,当一个区间赋值后,取反就相当于赋值 ( 1 − cov ) (1-\textit{cov}) (1cov),那么我们可以将 cov \textit{cov} cov 取反(此时 rev \textit{rev} rev 没用,要置为 0 0 0),否则,直接更新 rev \textit{rev} rev.

有不少坑点:

  • 下标从 0 0 0 开始.
  • 没有被赋值的节点, cov \textit{cov} cov 要置为 − 1 -1 1 表示没有赋值.
  • 更新 S S S 时,左半区间满了, lsum \textit{lsum} lsum 才能跨越中点, rsum \textit{rsum} rsum 同理.
  • 先处理 cov \textit{cov} cov 再处理 rev \textit{rev} rev.
  • rev \textit{rev} rev 标记时 ^= 1 不要写成 = 1.

Code

3.9 KB , 0.45 s , 11.63 MB    (in   total,   C++20   with   O2) 3.9\text{KB},0.45\text{s},11.63\text{MB}\;\texttt{(in total, C++20 with O2)} 3.9KB,0.45s,11.63MB(in total, C++20 with O2)
建议封装 S S S(见代码中的 Data),会好写不少.

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

namespace seg_tree {
	struct Data {
		int sum, lsum, rsum, tsum, len;
		inline Data() {}
		inline Data(int x) : sum(x), lsum(x), rsum(x), tsum(x), len(1) {}
		inline Data(int _sum, int _lsum, int _rsum, int _tsum, int _len)
		        : sum(_sum), lsum(_lsum), rsum(_rsum), tsum(_tsum), len(_len) {}
	};
	
	inline Data operator+(const Data& lhs, const Data& rhs) {
		const int _sum = lhs.sum + rhs.sum;
		const int _lsum = lhs.lsum + (lhs.sum == lhs.len) * rhs.lsum;
		const int _rsum = rhs.rsum + (rhs.sum == rhs.len) * lhs.rsum;
		const int _tsum = std::max({lhs.tsum, rhs.tsum, lhs.rsum + rhs.lsum});
		const int _len = lhs.len + rhs.len;
		return Data(_sum, _lsum, _rsum, _tsum, _len);
	}
	
	struct Node {
		int l, r;
		array<Data, 2> dat;
		int cov, rev;
		inline Data& operator[](int i) { return dat[i]; }
		inline Data operator[](int i) const { return dat[i]; }
	};
	
	inline int ls(int u) { return 2 * u + 1; }
	inline int rs(int u) { return 2 * u + 2; }
	
	struct SegTree {
		vector<Node> tr;
		inline SegTree() {}
		inline SegTree(const vector<int>& a) {
			const int n = a.size();
			tr.resize(n << 1);
			build(0, 0, n - 1, a);
		}
		
		inline void pushup(int u, int mid) {
			for (int i = 0; i < 2; i++) tr[u][i] = tr[ls(mid)][i] + tr[rs(mid)][i];
		}
		
		inline void apply(int u, int cov, int rev) {
			if (~cov) {
				const int len = tr[u][cov].len;
				tr[u][cov] = Data(len, len, len, len, len);
				tr[u][cov ^ 1] = Data(0, 0, 0, 0, len);
				tr[u].cov = cov;
				tr[u].rev = 0;
				return;
			}
			
			if (rev) {
				swap(tr[u][0], tr[u][1]);
				if (~tr[u].cov) tr[u].cov ^= 1;
				else tr[u].rev ^= 1;
			}
		}
		
		inline void pushdown(int u, int mid) {
			apply(ls(mid), tr[u].cov, tr[u].rev);
			apply(rs(mid), tr[u].cov, tr[u].rev);
			tr[u].cov = -1, tr[u].rev = 0;
		}
		
		void build(int u, int l, int r, const vector<int>& a) {
			tr[u].l = l, tr[u].r = r, tr[u].cov = -1;
			if (l == r) {
				for (int i = 0; i < 2; i++) tr[u][i] = Data(a[l] == i);
				return;
			}
			const int mid = (l + r) >> 1;
			build(ls(mid), l, mid, a);
			build(rs(mid), mid + 1, r, a);
			pushup(u, mid);
		}
		
		void update(int u, int l, int r, int cov, int rev) {
			if (l <= tr[u].l && tr[u].r <= r) return apply(u, cov, rev);
			const int mid = (tr[u].l + tr[u].r) >> 1;
			pushdown(u, mid);
			if (l <= mid) update(ls(mid), l, r, cov, rev);
			if (r > mid) update(rs(mid), l, r, cov, rev);
			pushup(u, mid);
		}
		
		Data query(int u, int l, int r) {
			if (l <= tr[u].l && tr[u].r <= r) return tr[u][1];
			const int mid = (tr[u].l + tr[u].r) >> 1;
			pushdown(u, mid);
			if (r <= mid) return query(ls(mid), l, r);
			else if (l > mid) return query(rs(mid), l, r);
			else return query(ls(mid), l, r) + query(rs(mid), l, r);
		}
		
		inline void range_cover(int l, int r, int v) { update(0, l, r, v, 0); }
		inline void range_negate(int l, int r) { update(0, l, r, -1, 1); }
		inline int range_sum(int l, int r) { return query(0, l, r).sum; }
		inline int range_gss(int l, int r) { return query(0, l, r).tsum; }
	};
}
using seg_tree::SegTree;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m;
	scanf("%d %d", &n, &m);
	
	vector<int> a(n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	
	SegTree sgt(a);
	for (int i = 0, op, l, r; i < m; i++) {
		scanf("%d %d %d", &op, &l, &r);
		if (op == 0) sgt.range_cover(l, r, 0);
		if (op == 1) sgt.range_cover(l, r, 1);
		if (op == 2) sgt.range_negate(l, r);
		if (op == 3) printf("%d\n", sgt.range_sum(l, r));
		if (op == 4) printf("%d\n", sgt.range_gss(l, r));
	}
	
	return 0;
}
内容概要:本文档详细介绍了在三台CentOS 7服务器(IP地址分别为192.168.0.157、192.168.0.158和192.168.0.159)上安装和配置Hadoop、Flink及其他大数据组件(如Hive、MySQL、Sqoop、Kafka、Zookeeper、HBase、Spark、Scala)的具体步骤。首先,文档说明了环境准备,包括配置主机名映射、SSH免密登录、JDK安装等。接着,详细描述了Hadoop集群的安装配置,包括SSH免密登录、JDK配置、Hadoop环境变量设置、HDFS和YARN配置文件修改、集群启动与测试。随后,依次介绍了MySQL、Hive、Sqoop、Kafka、Zookeeper、HBase、Spark、Scala和Flink的安装配置过程,包括解压、环境变量配置、配置文件修改、服务启动等关键步骤。最后,文档提供了每个组件的基本测试方法,确保安装成功。 适合人群:具备一定Linux基础和大数据组件基础知识的运维人员、大数据开发工程师以及系统管理员。 使用场景及目标:①为大数据平台建提供详细的安装指南,确保各组件能够顺利安装和配置;②帮助技术人员快速掌握Hadoop、Flink等大数据组件的安装与配置,提升工作效率;③适用于企业级大数据平台的建与维护,确保集群稳定运行。 其他说明:本文档不仅提供了详细的安装步骤,还涵盖了常见的配置项解释和故障排查建议。建议读者在安装过程中仔细阅读每一步骤,并根据实际情况调整配置参数。此外,文档中的命令和配置文件路径均为示例,实际操作时需根据具体环境进行适当修改。
在无线通信领域,天线阵列设计对于信号传播方向和覆盖范围的优化至关重要。本题要求设计一个广播电台的天线布局,形成特定的水平面波瓣图,即在东北方向实现最大辐射强度,在正东到正北的90°范围内辐射衰减最小且无零点;而在其余270°范围内允许出现零点,且正西和西南方向必须为零。为此,设计了一个由4个铅垂铁塔组成的阵列,各铁塔上的电流幅度相等,相位关系可自由调整,几何布置和间距不受限制。设计过程如下: 第一步:构建初级波瓣图 选取南北方向上的两个点源,间距为0.2λ(λ为电磁波波长),形成一个端射阵。通过调整相位差,使正南方向的辐射为零,计算得到初始相位差δ=252°。为了满足西南方向零辐射的要求,整体相位再偏移45°,得到初级波瓣图的表达式为E1=cos(36°cos(φ+45°)+126°)。 第二步:构建次级波瓣图 再选取一个点源位于正北方向,另一个点源位于西南方向,间距为0.4λ。调整相位差使西南方向的辐射为零,计算得到相位差δ=280°。同样整体偏移45°,得到次级波瓣图的表达式为E2=cos(72°cos(φ+45°)+140°)。 最终组合: 将初级波瓣图E1和次级波瓣图E2相乘,得到总阵的波瓣图E=E1×E2=cos(36°cos(φ+45°)+126°)×cos(72°cos(φ+45°)+140°)。通过编程实现计算并绘制波瓣图,可以看到三个阶段的波瓣图分别对应初级波瓣、次级波瓣和总波瓣,最终得到满足广播电台需求的总波瓣图。实验代码使用MATLAB编写,利用polar函数在极坐标下绘制波瓣图,并通过subplot分块显示不同阶段的波瓣图。这种设计方法体现了天线阵列设计的基本原理,即通过调整天线间的相对位置和相位关系,控制电磁波的辐射方向和强度,以满足特定的覆盖需求。这种设计在雷达、卫星通信和移动通信基站等无线通信系统中得到了广泛应用。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值