1291 火车线路(区间修改,区间最值)

眼前的话

  HTTP磋商对于前端工程师是格外主要的。我们在浏览网站时,访问的每一个WEB页面都亟需运用HTTP协议落到实处。倘诺不打听HTTP协议,就不容许精晓网站的原形。在求学HTTP在此之前,本文先介绍部分网络基础知识

 

1291 火车线路

 

 时间限制: 1 s

 空间范围: 128000 KB

 题目等级 : 大师 Master

 

 

网络

  简单地说,网络就是在必然的区域内将五个或七个以上的处理器以一定的法子连接起来,以供用户共享文件、程序、数据等资源。下边就二种普遍的网络项目及分类方法做不难介绍

1、按覆盖范围分

  局域网(local area
network,LAN):局域网一般在几十米到几英里范围内,一个局域网能够容纳几台到几千台计算机,局域网往往用来某一部落,比如一个供销社、一个单位、某一幢楼、某一个院校等

  城域网(Metropolis Area
Network,MAN):城域网是规模局限在一座城市范围内的区域性网络,一般的话,覆盖范围介于10~100KM之间

  广域网(Wide Area
Network,WAN):广域网是将分布在四处的局域网连接起来的网络,是网络之间的网络。广域网的界定非常大,可以跨越国界、洲界,甚至海内外限量。广域网的天下第一代表是Internet

  方今,还有七个相比盛行的网络概念:存储区域网(Storage Area
Network,SAN)和编造专用网(Virtual Private
Network,VPN)。SAN是专用的高性能网络,它用于在服务器与存储资源之间传输数据。由于SAN是一个单身的专用网络,从而可以防止在客户机与服务器之间的任何传输争辩。VPN是一种在公共网络上传输私有网络数据的专用网络技术,利用VPN,一个中远距离用户或分支机构能够与总部之间确立一条安全的隧道,用于传输私有多少

2、按拓扑结构分

  网络拓扑(Topology)确定了网络的布局。网络拓扑有三种:一种是情理拓扑,是指实际布线或配备相互连接的几何方式;另一种是逻辑拓扑,它定义了媒体怎样存取由主机发送的多少

(1)物理拓扑

  依据物理拓扑结构的两样,可以将网络分为星型网络、环型网络、总线型网络三种为主项目

  a、总线型网络。网络中有着的站点共享一条数据通道,总线的两端有端结点。总线型网络安装简便方便,要求铺设的电线最短,费用低,某个站点的故障一般不会影响总体网络,但介质的故障会招致网络瘫痪。总线网安全性低、监控相比较艰辛、扩张新站点也不如星型拓扑网络简单。所以,总线型网络布局现在大多已经被淘汰

  b、环型拓扑。环型网络布局的各站点通过通信介质连成一个查封的环形。环形网络简单安装和监察,但容量有限,网络建成后,难以伸张新的站点。由此,现在组建局域网已经基本上不行使环形网络布局了

  c、星型拓扑。各站点通过点到点的链路与宗旨站点相连。星型网络很简单在网络中加进新的站点,数据的安全性和预先级简单控制,易完结网络监督,一个站点出了问题,不会潜移默化总体网络的运转,但基本站点的故障会挑起一切网络瘫痪,星型网络布局是现行最常用的网络拓扑结构

图片 1

  在那两种档次的网络布局基础上,可以组成出举办星型、层次型、网状型等任何类型拓扑结构的网络

(2)逻辑拓扑

  网络逻辑拓扑指各台主机通过传输介质相互通信的章程。最广泛的三种逻辑拓扑格局是广播拓扑和令牌拓扑

  a、广播拓扑。每台主机都把所要发送数据的对象地方设为网络介质上某个特定网络接口卡的地点、多播地址或播报地址,然后把该数据发送到传输介质中。每台主机使用传输介质时不必遵守某种次序,即先来先服务。现在最常使用的以太网就是采取那种方法来干活的

  b、令牌拓扑。令牌拓扑通过向各台主机顺序传递一个电子令牌来控制网络介质的造访。当一台主机接收到令牌时,它就可以把多少发送到网络介质上。即使该主机没有数据要发送,那么就将令牌传递给下一台主机,如此循环。使用令牌传递的重大有令牌环和光纤分布式数据接口(FDDI),它们都是在大体环形拓扑上运用令牌传递的

3、按传输介质分

  根据网络的传输介质分类,可以将统计机网络分为有线网络和有线网络二种。有线网络蕴涵选拔同轴电缆、双绞线、光纤等有线介质连接的统计机网络。局域网平日使用单一的传导介质,而城域网和广域网拔取多种传输介质

(1)双绞线

  选择双绞线连网,因价格便宜,安装方便,所以是当前最广泛的一连方式。总括机局域网中的双绞线可分为非屏蔽双绞线、铝箔屏蔽的双绞线和屏蔽双绞线

  a、非屏蔽双绞线(Unshielded Twisted
Paired,UTP)价格低廉、简单安装及重新配置,所以是最普遍的传输介质,它由两股线规很细的铜线组成,互相绝缘,以稳住间隔互相绞合在一道,绞合的法力是为平衡电脉冲传输进度中所形成的电磁场。在传输距离(理论上是100m)范围内,五类UTP的多寡传输速率可以完成100Mb/s,甚至
1000Mb/s

  b、铝箔屏蔽的双绞线(Foil Twisted
Pair,FTP)带宽较大,抗苦恼能力强。相对的,屏蔽线比非屏蔽线价格及安装费用要高一些,线缆弯曲性能稍差。六类线及六类此前的遮挡系统多使用那种格局

图片 2

  c、屏蔽双绞线(Shielded Twisted-Pair,
STP)每一对双绞线都有一个铝箔屏蔽层。四对双绞线合在一起,并且还有一个国有的金属编织屏蔽层,那是七类线的正统社团,它适用于神速网络的运用

图片 3

  [注意]双绞线的造作口诀一般为白橙橙、白绿蓝、白蓝绿、白棕棕

  双绞线有3种类型:直通线、交叉线和全反线。直通线(Straight-through)紧要用来分歧种装备的互连;交叉线(Crossover)主要用以同种设备的互连;全反线(Rollover)用于对路由器和沟通机进行初始配置或用于异步传输

(2)同轴电缆

  与双绞线相比,同轴电缆含有线规较粗的单层实心导体,导体一般由铜或覆以铜的铝制成。中间的导体外面覆以一层绝缘材料,那种绝缘材料有助于把高中级的导体和外围的五金铝箔屏蔽层隔开。外面日常会包一层金属网,再包一层尊崇皮对电缆加以保养。中间的导体可支撑高频信号,大概不会并发麻烦UTP及同类电缆的信号衰减问题

  以太网及其余LAN技术原先使用同轴电缆是因为它能帮衬高频信号,而且不受电磁干扰影响。不过,面对迅猛发展的双绞线,开支高昂加上安装困难导致同轴电缆退居其后。现在利用同轴电缆较多的网络是有线电视机网

  同轴电缆按照粗细程度不等,分为粗缆(10Base5)和细缆(10Base2)。粗缆的传导距离是500m,细缆的传输距离是185m

图片 4

(3)光纤网

  光导纤维简称光纤,光纤传输距离长,传输速率高,可达数千兆bps,抗干扰性强,不会惨遭电子监听设备的监听,是高安全性网络的漂亮选用。光纤是细如发丝般的透明玻璃丝,可用来传导光信号。光纤由纤芯和包层组成,由于纤芯的折射率大于包层的折射率,故光波在界面上形成全反射,使光只可以在纤芯中传来,完毕通信

  工程中选拔最多的分法是按光纤横截面上折射率来分,有单模光纤和多模光纤。单模光纤纤芯直径较小,采取激光作为光源,传输的趋势是沿光纤直径方向,由此单模光纤数据传输速率较快,传输距离较远,价格相对较贵;多模光纤纤芯直径较大,选用发光二极管作为光源,传输的势头是全反射,由此多模光纤数据传输速率较慢,传输距离较近,价格相对较有利于

图片 5

(4)无线网

  有线网采纳微波、红外线、无线电等传输,由于有线网络的连网方式灵活方便,是一种很有前景的连网情势

4、按服务方式分

  根据网络的劳动措施分类,可以将电脑网络分为客户机/服务器网和对等网二种

  a、客户机/服务器(Client/Server)网

  服务器是指专门提供劳动的高性能总括机或专用设备,客户机是指用户电脑。那是客户机向服务器发出请求并收获劳动的一种网络方式,多台客户机可以共享服务器提供的各个资源,那是最常用、最要害的一种网络项目,不仅符合于同类总计机联网,也符合于分化类型的处理器联网。这种网络安全性不难获得有限支撑,统计机的权能、优先级易于控制,监控简单完成,网络管理可以规范化。网络性能在很大程度上有赖于服务器的特性和客户机的数量。方今本着那类网络有不少优化性能的服务器,称为专用服务器

  b、对等网(Peer-to-Peer)

  对等网不必要专用服务器,每台客户机都可以与其余客户机对话,共享互相的信息资源和硬件资源,组网的微处理器一般品种相同。那种网络格局灵活方便,不过较难落成集中管理与监控,安全性也低,较符合于机关中间协同工作的小型网络

  此外还有局地卓殊的分类方法,如公司网、高校网,依照名称便可领略。从不相同的角度对网络有例外的分类方法,每种网络名称都有格外的意义。了然网络的分类方法和类型特征,是驾轻就熟网络技术的关键基础之一

 

问题叙述 Description

某列火车采纳在C个都市里面(出发的都市编号为1,截至达到的城池的号码为C),假诺该列火车有S个席位,现在有R笔预约票的作业。现在想对这R笔业务开展处理,看什么预约能满意,哪些无法满意。

一笔预订由O、D、N五个整数组成,表示从起源站O到目标站D必要预订N个座位。一笔预约能满意是指该笔业务在路途范围内有能满意的空座位,否则就不可能满意。一笔业务不可以拆分,也就是源点和终点站无法改变,预约的席位数目也无法改变。所有的预约须求按给出先后顺序举办拍卖。

请您编写程序,看这些预订业务能满意,那个无法满意。

OSI

  OSI和ISO简单混淆。ISO是国际标准化社团(International Standard
Organization)。而OSI是ISO提议的关于电脑网络的一个开放式系统互连参考模型(Open
System Interconnection/Reference Model)

  要想让两台电脑举办通信,必须使它们接纳同样的新闻调换规则。我们把在计算机网络中用来规定音讯的格式,以及咋样发送和吸收新闻的一套规则称为网络协议(Network
Protocol)或通信协议(Communication Protocol)

  为了减少网络协议设计的复杂,网络设计者并不是陈设性一个十足、巨大的说道来为拥有形式的通信规定完整的底细,而是利用把通信问题分割为无数个小题目,然后为种种小问题设计一个单身的情商的主意,绝一大半网络使用分段设计方法。所谓分层设计艺术,就是根据音信的流动进度将网络的完好功用分解为一个个的功效层,分歧机器上的一律听从层之间选取同一的商事,同一机器上的附近功能层之间通过接口进行新闻传送

  OSI模型是一个开花种类布局,它规定将网络分为7层,并规定每层的效劳

图片 6

物理层

  物理层的第一成效是完毕相邻结点之间原始比特流的传输,控制数据如何被停放到通信介质上。物理层协议关注的优秀问题是行使什么的物理信号来表示数据“1”和“0”;一位持续的年华多少长度;数据传输是否可同时在八个趋势上进行;最初的延续怎么样树立和成功,通信后总是怎样终止;物理接口(插头和插座)有微微针以及各针的用处等。物理层的宏图重点涉嫌物理层接口的机械、电气、作用和进程特征,以及物理层接连接的传导介质等问题,物理层的筹划还关系通信工程领域内的有的问题

1、中继器(Repeater)

  中继器是接连网络线路的一种装置,常用来三个网络结点之间物理信号的双向转载工作。中继器是最简便的网络互联设备,首要形成物理层的法力,负责在多少个结点的物理层上按位传递音讯,完结信号的复制、调整和松手效能,以此来拉开网络的长短。由于存在消耗,在路经上传输的信号功率会逐步衰减,衰减到一定水准时将造成信号失真,由此会导致接收错误。中继器就是为涸泽而渔这一题材而布署的,它形成物理线路的连接,对衰减的信号举行拓宽,保持与原数据一致

  双绞线理论上的最大传输距离是100m,假使超过100m,由于信号的衰减,很难有限支持音讯传输的正确性,可以利用中继器来拉开传输的离开。中继器仅适用于以太网,可将两段或两段以上(使用两个中继器)的以太网互连起来

2、集线器(Hub)

  集线器相当于多端口的中继器,也得以把信号整形、放大后发送到具有结点上。在环型网络中只存在一个大体信号传输通道,都是通过一条传输介质来传输的,那样就存在各结点争抢信道的争辨,传输功能较低。引入集线器这一网络设施后,每一个工作站是用它和谐专用的传导介质连接到集线器的,各结点间不再只有一个传输通道,各结点发回去的信号通过集线器集中,集线器再把信号整形、放大后发送到拥有结点。那样至少在上行通道上不再次出出现碰撞现象。但基于集线器的网络仍旧是一个共享介质的局域网,那里的“共享”其实就是集线器内部总线,所以当上行通道与下水通道同时发送数据时依旧会存在信号碰撞现象。当集线器在其里面端口检测到冲击时,发生猛击强化信号向集线器所连接的有着端口举办传递,那时所有数据都将不可以发送成功

  正因为集线器的这一不足之处,所以它不可以独立选取于较大网络中(平时是与交流机等装置一起分担小部分的网络通信负荷),似乎在大城市中坚不可以有单车道一样,因为网络越大,出现网络碰撞现象的火候就越大。也正因如此,集线器的数量传输功能是相比较低的,因为它在同样时刻只好有一个方向的数额传输,也就是所谓的“半双工”格局。若是网络中要选择集线器作为纯粹的连年装置,那么网络的范围最好在10台以内,而且集线器带宽应为10/100Mb/s以上

  集线器除了共享带宽这一不足之处外,还有另一个上边的不足必须要考虑,那就是它的播音工作措施。因为集线器属于OSI七层模型的物理层,基本上不具有“智能”的力量,更别说“学习”功能了。它也不享有调换机所独具的MAC地址表,所以它发送数据时都是从未有过针对的,而是使用广播方式发送。也就是说,当它要向某结点发送数据时,不是直接把数据发送到目的结点,而是把数量包发送到与集线器相连的享有结点

  那里引入八个概念:争辩域(CollisionDomain)和广播域(布罗德castDomain)。当几个比特在相同介质上同时传输时就会发生争辨。所谓顶牛域就是指发送数据给一个纯粹目的所影响的范围;所谓广播域是指发送数据给一个不通晓对象所影响的限制,集线器将把该广播包转载到除收取端口以外的具备端口,集线器上的持有装备属于同一个广播域

  所有通过集线器(不管有稍许个集线器)互连的网络中唯有一个广播域、一个争执域。那种广播式发送数据有两地点相差:一、用户数量包向所有结点发送,很可能带来多少通信的不安全因素,一些狡猾的人很不难就能收获别人的数目包:二、由于负有数据包都是向具有结点同时发送,可能造成网络不通现象,下降网络实施效用

图片 7

数据链路层

  数据链路层的第一功用是什么样在不可靠的大体线路上展开数量的可相信传输。数据链路层落成的是网络中相邻结点之间可信的数据通信。为了有限支撑数据的笃定传输,发送方把用户数据封装成帧(Frame),并按顺序传送各帧。由于大体线路的不可依赖,因而发送方发出的数据帧有可能在路经上出错或有失,从而造成接收方不可能科学接受到数据帧。为了有限支持能让接收方对收到到的多寡进行科学判断,发送方为每个数据分块计算出CRC(循环冗余检验),并把CRC添加到帧中,那样接收方就足以经过重复计算CRC来判定数据接收的科学。一旦接收方发现收到到的数额有错,则发送方必须重传这一帧数据。可是,相同帧的累累传递也恐怕使接收方收到重复的帧。比如,接收方给发送方的“确认帧”被毁掉后,发送方也会重传上一帧,此时接收方就可能收到到再也帧。数据链路层必须解决由于帧的毁坏、丢失和重新所带来的题材

  数据链路层要化解的另一个问题是防患高速发送方的数码把低速接收方“淹没”。因而,必要某种音信流量控制机制使发送方得知接收方当前还有稍稍缓存空间。为了操纵的便利,流量控制日常和不是处理一起已毕

  在最普遍的以太网中,数据链路层通过MAC(Media Access
Control,媒体访问控制)地址负责主机之间数据的保证传输。数据链路层的装备必须可以辨识出多少链路层的地点,即MAC地址。一个设施假若能识别MAC地址,该设施至少是数量链路层以上的装置。数据链路层的网络设施主要有网卡、网桥和沟通机

1、网卡(NIC)

  网卡(Network Interface
Card,NIC)也叫网络适配器,是一连电脑与网络的硬件设施。网卡的要害办事原理是收拾计算机上发往网线上的多少,并将数据表明为方便大小的数据帧之后向网络上发送出去。对于网卡而言,每块网卡都有一个唯一的网络结点地址,
它是网卡生产厂家在生产时烧入ROM(Read Only
Memory,只读存储芯片)中的,叫做MAC地址,且有限支持相对不会再一次

  网卡插在微机或服务器伸张槽中,通过网络线(如双绞线、同轴电缆或光纤)与网络调换数据、共享资源。计算机对吸收到的数据帧举行相比,若是数据帧中的目的MAC地址与本机网卡的MAC地址一样,或者目标MAC地址是广播MAC地址,即
“FFFFFFFFFFFF”,则总计机对数据帧进行处理;否则,计算机摒弃该数据帧

  可以在DOS窗口中应用“ipconfig/all”命令査看统计机网卡的MAC地址,网卡的MAC地址用十六进制表示,占用48个比特,前24个比特表示厂商,后24个比特为设备编号

图片 8

2、网桥(Bridge)

  网桥工作在多少链路层,用于将六个LAN连接在联名并按MAC地址转载帧。物理层的集线器可以增加网络的局面,但具备通过集线器相连的主机属于同一个争辨域,任何时刻只好有一台主机发送数据,如果有两台主机同时发送数据就会发生争辩,导致数据发送战败。当同一个争论域中的主机数据量非凡多时,数据暴发争辩的可能大大扩大,此时得以采取网桥来分隔龃龉域

  网桥可以用来分隔争持域,把一个顶牛域分隔成七个顶牛域,通过扩大争辩域的数额,减小各样顶牛域的轻重,减弱争持时有暴发的或者。连接七个网段的网桥能从一个网段向另一个网段传送完整而且不易的帧,不会传递苦恼或有问题的帧

  网桥主要用以互联以太网分段,传输需在几个分歧分支间传输的音信,不过阻断局地分段内的新闻,因而网桥收缩了网络上的通信总量

  因为网桥能检査出部分故障,所以比中继器使用更广泛。两个经过中继器相连的网段,如若出于打雷而致使其中一个网段上有电干扰,中继器会把它传送到另一个网段。相反,若是苦恼发生在通过网桥连接的网段中,网桥接收到一个不科学的帧,舍弃该帧。类似地,网桥不会把从一个网段传送来的顶牛信号传递到另一个网段。由此,网桥会把故障控制在一个网段中而不会影响到另一个网段

  网桥比中继器和集线器对数码包做更多的拍卖,延时也针锋相对扩大,一个双端口的网桥包罗四个争辨域和一个广播域

图片 9

3、交换机(Switch)

  与网桥的行事进度看似,调换机也按照源MAC学习,依据目的MAC举行转载,按每一个数据帧中的MAC地址决策音信转化地址表

  调换机转载方式分为3种景况:情形一、交流机对己知的单播帧,只往对应的端口转载;情况二、互换机对未知的单播帧,即调换机还尚未学到数据帧中的目标MAC地址,调换机泛洪数据包,即发往除接受端口以外的装有端口;情形三、沟通机对组播帧和广播帧举办泛洪转载,即发往除接受端口以外的兼具端口

  类似网桥,沟通机提供了网络互联功效。交流机的各样端口都是一个单身的争执域,
可以为各类工作站提供更高的带宽。因为调换机可以运用现有的电线、中继器、集线器和工作站的网卡,不必做高层的硬件升级;交流机对工作站是晶莹的,那样管理支出低廉,简化了网络结点的加码、移动和网络转移的操作;并且互换机的价位与集线器所差无几,所以在前天的网络中,交流机被广泛使用

  可以简简单单地把调换机看成是多端口的网桥,但互相有局地分别。网桥一般唯有2个端口,而貌似沟通机最少也有4个端口,还有24端口、48端口,甚至越来越多口的交流;网桥采取软件进行转账,而交流机选拔专门规划的集成电路,基于硬件举办数量转载,沟通机以线路速率在享有的端口并行转载新闻,提供了比传统网桥高得多的操作性能,操作看似单个局域网性能,远远超过一般网桥互联网络之间的中转性能;而且,调换机的端口造价远小于网桥

图片 10

网络层

  网络层(Network)的要紧作用是完成网络中主机间的报文传输。在广域网中,那包蕴暴发从源端到目的端的路由,依照使用的路由协议,选取最优的路线

  网络层涉及的商谈有IP、IPX等,网络层的装备必须能鉴别出网络层的地方,比如路由器、三层沟通机等都可以依照IP地址做路径选用,它们都属于网络层设备

  路由器是一种连接四个网络或网段的网络层设备,它能将不相同网络或网段之间的多少新闻举行“翻译”,以使它们能够相互“读懂”对方的数据,从而结成一个更大的网络。它不是使用于同一网段的装备,而是利用于分化网段或不一样网络之间的设施。路由器之所以能在差距网络之间起到“翻译”的效益,是因为它不再是一个纯硬件配备,而是援助格外丰裕路由协和的软、硬结合的设施,接济的商议有RIP、OSPF、EIGRP等,这么些路由协和就是用来兑现连通不一样网段或网络的

  路由器有两大卓越效能,即数据通道功效和控制作用。数据通道作用包蕴转载决定、背板转载,以及出口链路调度等,一般由特定的硬件来成功;控制功用相似用软件来落到实处,包蕴与隔壁路由器之间的音讯互换、系统布署、系统管理等

  路由器具有判断网络地址和挑选路径的功能,它能在多网络互联环境中,建立灵活的连天,可用完全两样的数额分组和介质访问方法连接各个子网。路由器属于网络层的一种互联设备,有隔离广播的功效,它的各样端口都是一个独立的广播域,也是一个单身的争执域

  在局域网接入广域网的许多方式中,通过路由器接入互联网是最为广泛的不二法门。使用路由器互联网络的最大亮点是:各互联子网仍保持各自独立,每个子网可以应用差其他拓扑结构、传输介质和网络协议,网络布局层次鲜明。通过路由器与互联网不断,则可完全挡住公司里面网络。有些路由器内部还合并了侵略防御和防火墙功效,因而选用路由器可以用来防御攻击,珍视内部网络的安全

传输层

  传输层(Transport
Layer)是整整网络的要紧部分,完毕七个用户进度间端到端(End-to-End)的可信赖通信,处理多少包错误、数据包次序,以及此外部分珍爱传输问题。向下提供通信服务的最高层,弥补通信子网的异样和不足,向上是用户功用的最低层。与数据链路层有相似之处,区其余地点在于前者是端到端的,后者是点到点的,而且比数据链路层协议复杂得多

  传输层的重中之重功能有:提供建立、维护和拆迁传输层连接,向网络层提供合适的劳务,提供端到端的错误复苏和流量控制,向会话层提供单身于网络层的传递服务和可信的晶莹数据传输

  传输层相关的商议有TCP (Transmission Control
Protocol,传输控制协议)、UDP (User Datagram
Protocol,用户数量报协议),它们涉及服务使用的端口号,主机依照端口号识别服务(常用的WWW服务端口号是80,
Telnet服务端口号是23等),区分会话(源IP、源端口号、目的IP、目标端口号,四者共同唯一标识一个对话)

会话层

  会话层(Session
Layer)允许差别机器上的用户之间确立会话关系,会话层提供的劳动之一是管理对话控制。会话层允许新闻同时双向传输,或任一时刻只好单向传输。若是属于后者,类似于物理信道上的半双工情势,会话层将记录此时该轮到哪一方。一种与对话控制有关的劳务是令牌管理,有些协议有限支持双方无法而且开展同样的操作,那一点很要紧。为了管住那个移动,会话层提供了令牌,令牌可以在对话双方之间活动,唯有拥有令牌的一方得以推行某种关键性操作

  另一种会话层服务是一道,若是在平均每小时出现四遍大故障的网络上,两台机器间要开展三遍两小时的文件传输,想想会出现什么样的问题?每一回传输中途受挫后,都只能再次传送这一个文件。当网络再一次出现大故障时,可能又会暂停。为了缓解这些题材,会话层提供了一种办法,即在数码中插入同步点。每一遍网络现去世障后,仅仅重传最终一个同步点未来的数额

表示层

  表示层(Presentation
Layer)落成某些特定的成效,对那个功用人们日常希望找到普遍的解决办法,而无需由各类用户自己来完成。值得一提的是,表示层以下各层只关注从源主机到对象主机可信赖地传递比特,而表示层关注的是所传递的新闻的语法和语义

  表示层服务的一个独占鳌头例子是用一种我们一致选定的业内措施对数据开展编码

  网络上电脑可能应用分歧的数据表示,所以需求在数码传输时举办数量格式的转移。例如在区其他机器上常用差其余代码来表示字符串(ASCII和EBCDIC)、整型数(二进制反码或补码),以及机器字的分裂字节顺序等。为了让动用分化数据表示法的电脑之间可以互为通信并互换数据,在通信进程中运用抽象的数据结构来代表传送的数据,而在机器内部依旧采取各自的专业编码。管理那几个抽象数据结构,并在发送方将机械的其中编码转换为符合网上传输的传递语法,以及在接收方做反而的变换等,都是由表示层来形成的

  别的,表示层还关周到据压缩和平解决压、数据加密和平解决密等工作

应用层

  联网的目的在于接济运行于不相同电脑上的进度展开通信,而这几个过程则是为用户落成不一样义务而安排的。可能的应用是多地点的,不受网络布局的限定。应用层(Application
Layer)包罗大批量人们广泛须要的合计,如HTTP(Hyper text Transfer
Protocol,超文本传输协议),该使用默许使用的是TCP的80端口;FTP(File
Transfer Protocol,
文件传输协议),多用来因特网上的文件传输,该利用管理端口默许使用的是TCP的21号端口;SMTP(Simple
Mail Transfer
Protocol,不难邮件传输协议),用于邮件的殡葬,该使用默许使用的是TCP的25号端口;POP3(Post
Office Protocol Version
3,邮局协议版本3),用于邮件的吸纳,该利用默认使用的是TCP的110号端口;DNS(Domain
Name
System,域名连串),用于因特网上域名的剖析;Telnet(远程登录)是一种字符格局的巅峰服务,它可以使用户通过网络进入远程主机或网络设施,然后对长距离主机或网络设施进行操作,那种连接可以暴发在局域网里面,也得以因此互联网举行,该使用默认使用的是TCP的23号端口

  对于急需通信的不比采用来说,应用层的合计都是需要的。比如,当某个用户想要得到远程总结机上的一个文书拷贝时,他要向本机的文件传输软件发出请求,那些软件与长途统计机上的文件传输进度经过文件传输协议进行通信,那几个协议紧要处理公事名、用户许可状态和别的请求细节的通信。远程统计机上的文件传输进度使用任何特色来传输文件内容

 

输入描述 Input Description

     
 输入文件中的第一行为三个整数``C``、``S``、``R``,(1<=c<=60
000, 1<=s<=60 000, 1<=r<=60
000)他们之间用空隔分开。接下来的``R``行每行为三个整数O、D、N,(1<=o<d<=c,
1<=n<=s),分别代表每一笔预约业务。

出口描述 Output Description

     
 对第I笔业务,若是能满意,则在输出文件的第I行输出“T”,否则输出“N”

TCP/IP

  TCP/IP是眼前最成功、使用最频仍的互联网协议。TCP/IP参考模型是四层结构,分别是网络访问层(NetworkAccess),蕴含OSI模型的物理层和数码链路层,在这一层可以看来数据帧的源和目的MAC地址;网际层(Internet),相当于OSI模型中的网络层,在这一层能够见见数据包的源和目标IP地址;传输层(Transport),和OSI模型中的传输层一致,在这一层可以看看数据分段源和目标的端口,以及所接纳的协议;应用层(Application),包含OSI模型的上三层,即会话层、表示层和应用层

  ISO/OSI参考模型是在其情商被支付之前设计出来的。那表示ISO/OSI模型并不是依据某个特定的合计集而安排的,由此它更富有通用性。但另一方面,也代表ISO/OSI模型在商榷落到实处位置存在一些不足。而TCP/IP模型正好相反。先有协商,模型只是现有协议的讲述,由此协议与模型格外契合。问题在于TCP/IP模型不符合任何协议栈。由此,它在叙述其余非TCP/IP网络时用处不大

 图片 11

网络访问层

  网络访问层(Network
Access)的意义包蕴IP地址与物理硬件地址的炫耀,以及将IP分组封装成帧。基于分歧硬件类型的网络接口,网络访问层定义了和物理介质的总是。网络访问层包括了多少链路层的位置,如用在以太网上就是MAC地址。此层是TCP/IP模型的最底部,负责接收从IP层传来的IP数据报,并将IP数据报通过低层物理网络发送出去,或者从低层物理网络上接受物理帧,解封装出IP数据报,交给IP层处理

网际层

  网际层(Internet)的第一意义包罗六个方面:1、处理来自传输层的分组发送请求:将分组装入IP数据报,填充报头,选拔去往目标结点的途径,然后将数据报发往适中的网络接口;2、处理输入数据报:首先检查数据报的合法性,然后举办路由选拔,即使该数据报己到达目标结点(本机),则去掉报头,将IP报文的数据部分交给相应的传输层协议;要是该数额报尚未到达目标结点,则转向该多少报;3、处理ICMP(Internet
Control Message Protocol,网际控制音讯协议)报文:
即处理网络的路由采取、流量控制和隔阂控制等问题

  TCP/IP网络模型的网际层在成效上非凡类似于ISO/OSI参考模型中的网络层。网际层上的合计包罗IP协议、ICMP协议、Proxy协议、ARP协议、RARP商量、BOOTP协议和DHCP协议

1、IP协议

  IP的权利就是把数量从源传送到目标地。它不负责保障传送可相信性、流控制、包顺序和其他对于主机到主机协议以来很经常的服务。IP已毕三个基本功效:寻址和分层。IP能够依据数量报报头包含的目标地址将数据报传送到目标地址,在此进程中IP负责选拔传送的不二法门,那种选取路径功用称为路由效能。如若稍微网络内只可以传送小数据报,IP可以将数据报重新组建并在报头域内申明

  构成IP报头的字段如下图所示

图片 12

  括号中的数值表示该字段所占用的比特数。其中,优先级和服务类型字段一般用于QoS(Quality
of 瑟维斯,服务质地);存活期(提姆(Tim)e To Live,
TTL)是数量报可以生存的时日上限,它由发送者设置,每经过三遍路由,TTL至少减1,如若未到达目标地时,生存时间减为零,则废弃此数额报;源和目的IP地址用于表示数据从哪来,到哪去

  IP不提供可相信的传输服务,它不提供端到端的或结点到结点的认可,对数码没有差错控制,它只使用报头的校验码,不提供重发和流量控制。如果出错可以透过ICMP报告,ICMP在IP模块中得以完成

2、ICMP

  ICMP(Internet Control Message Protocol, Internet
控制信息协议)是TCP/IP协议族的一个子商事,用于在IP主机、路由器之间传递控制新闻。控制新闻是指网络通不通、主机是否可达、路由是否可用等网络本身的音讯。那个决定新闻固然并不传输用户数量,可是对于用户数据的传递起着至关紧要的作用

  在网络种类结构的各层次中,都急需控制,而不相同的层次有例外的分工和操纵内容,IP层的操纵效率是最复杂的,主要承担差错控制、拥塞控制等,任何决定都是树立在信息的根底之上的。在依照IP数据报的网络系列中,IP协议本身没有内在机制来获取差错音信并拍卖。为了处理那几个不当,TCP/IP设计了ICMP协议,当某个网关发现传输错误时,马上向信源主机发送ICMP报文,报告出错音信,让信源主机选拔相应处理方法,它是一种错误和决定报文协议,不仅用于传输差错报文,还传输控制报文

  常常使用的用来检査网络通不通的Ping命令,那些“Ping”的经过实际上就是ICMP协议工作的历程。发送主机首头阵送一个ICMP
Echo Request的包,包括64字节数据,它被发送后,接收方会重返一个ICMP Echo
Reply的包,再次回到的数量中隐含了接受到的数指标正片。还有此外网络命令,如跟踪路由的Tracert命令也根据ICMP协议

  ICMP报文包蕴在IP数据报中,属于IP的一个用户,IP头部就在ICMP报文的前边,所以一个ICMP报文包蕴IP头部、ICMP头部和ICMP报文,IP头部的Protocol值为1就证实这是一个ICMP报文,ICMP头部中的类型(Type)域用于评释ICMP报文的功效及格式,其它还有一个代码(Code)域用于详细表明某种ICMP报文的系列,所有数据都在ICMP头部前面

  RFC定义了13种ICMP报文格式

图片 13

  [注意]代码为15、16的新闻报文已经作废

  上面是两种普遍的ICMP报文

  a、响应请求。大家屡见不鲜行使最多的ping,就是响应请求(Type=8)和回应(Type=0),一台主机向一个结点发送一个Type=8的ICMP报文,如若中途没有尤其(例如被路由器舍弃、目的不回应ICMP或传输败北),则指标重返Type=0的ICMP报文,表达那台主机存在,更详实的tracert通过测算ICMP报文通过的结点来规定主机与对象以内的网络距离

  b、目标不可到达、源抑制和过期报文。那三种报文的格式是一模一样的,目的不可到达报文(Type=3)在路由器或主机不可以传递数据报时使用,例如要连接对方一个不存在的系统端口(端口号小于1024)时,将回到Type=3、Code=3的ICMP报文,它唤醒的情致就是目的不可到达。常见的不得到达类型还有网络不可到达(Code=0)、主机不可到达(Code=1)、协议不可到达(Code=2)等。源抑制则担任一个说了算流量的角色,它打招呼主机收缩数额报流量,由于ICMP没有过来传输的报文,所以要是截止该报文,主机就会逐年复苏传输速率。最终,无连接方式网络的题目就是数量报会丢失,或者长日子在网络游荡而找不到目的,或者拥塞导致主机在确定时间内不可能重组数据报分段,那时就要触发ICMP超时报文的发出。超时报文的代码域有三种取值:Code=0表示传输超时,Code=1表示结合分段超时

  c、时间戳。时间戳请求报文(Type=13)和岁月戳应答报文(Type=14)用于测试两台主机之间数据报来回三遍的传输时间。传输时,主机填充原始时间戳,接收方收到请求后填充接收时间戳后以Type=14的报文格式重返,发送方统计这么些时刻差

3、ARP

  ARP(Address Resolution
Protocol,地址解析协议)负责将某个IP地址解析成对应的MAC地址。在局域网中,网络中其实传输的是
“帧”,帧里面是有目的主机的MAC地址的。在以太网中,一个主机要和另一个主机进行直接通信,必要求知道对象主机的MAC地址。但那一个目的MAC地址是怎么着赢得的呢?它就是通过地点解析协议拿到的,所谓“地址解析”就是主机在发送帧前根据目的IP地址得出目标MAC地址的历程。ARP协议的基本功用就是因此目的设备的IP地址,查询目的设备的MAC地址,以管教通信的顺利举办

  借使源主机在该地缓存中找到对象主机对应的MAC地址,则源主机用此MAC地址封装帧,并发送出去;如若没有找到,则源主机发送一个ARP的询问包(ARP
Request)。ARP查询包中的源IP地址是源主机的IP地址,目的IP地址是目的主机的IP地址,源MAC地址是源主机的MAC地址,ARP査询包中的目标MAC地址是广播MAC地址FF-FF-FF-FF-FF-FF。源主机封装完毕后,把ARP查询包以广播的款型发送出去,广播域内的具备主机均收到此广播包,假使目的IP地址不是本机IP,则甩掉继续处理该数据包,并在地面缓存扩充或更新源主机对应的MAC地址。假设目的IP地址与本机相同,也在本土缓存中加进或更新源主机对应的MAC地址,然后发回ARP应答包(ARP
Reply)

  因此,ARP请求包是广播包,而ARP应答包是单播包

  使用“arp -a”命令能够查看本机的ARP缓存表;使用“arp
-d”命令删除本机的ARP缓存,使用“arp -s”命令把IP地址和MAC地址举办绑定

图片 14

4、ProxyARP 

  后边介绍的ARP协议得以援助主机或路由器获知局域网上某个IP地址对应的MAC地址,可却一筹莫展获知一台远程主机对应的IP地址,因为ARP査询包是广播包,路由器有隔离广播的作用,致使ARP查询包不可能通过路由器而到达远端的目标主机。局域网内的主机可以配备默许网关来访问远端主机,可主机不允许配置五个默许网关。假若某个默许网关(一般是路由器)因故障停机,即便该局域网还有另一台讲话路由器,主机也不会向其余的路由器发送数据,此时内需重新配置主机的网关。而代理ARP则可以在那种情景下自行支持那么些在某个子网中的主机,在不重新配置路由甚至默许网关的情事下,发送数据到远端主机

  使用ProxyARP(代理
ARP)可以在网络中单独扩充一台路由器,而不会潜移默化别的路由器的路由表。不过利用代理ARP也拉动严重不足:使用代理ARP将会明显扩充网络分段中的传输业务量,并且网络中的主机也将会维持比正常时大过多的ARP表,并以此来拍卖整个的IP到MAC的地址映射

5、RARP

  前边介绍的ARP是己知其他电脑的IP地址,查询其余计算机的MAC地址。而RARP(Reverse
Address Resolution Protocol,反向地址转换协议)
是己知本机的MAC地址,询问本机的IP地址。典型用在无盘工作站上,当一台无盘工作站启动时,它从不章程在其伊始化时精晓自己的IP地址,可是,它可以掌握自己的MAC地址。无盘工作站可以通过发送RARP的包来询问与此MAC地址相对应的IP地址,网络上会指定一个被称之为RARP服务器的处理器来响应那些请求,那样无盘工作站就会获得协调的IP地址

  RARP是初期提供的经过硬件地址获取IP的化解方案,但它有我的局限性。比如,RARP客户与RARP服务器不在同段,中间有路由器等设备连接,那时候利用RARP就显得力不从心,因为RARP请求报文不可以透过路由器。BOOTP(BootstrapProtocol,引导协议)提供了很好的化解方法,同样,在今天的大中型网络中,DHCP(Dynamic
Host Configuration Protocol,动态主机配置协议)协议也是常用协议之一

6、BOOTP

  BOOTP(BootstrapProtocol,率领协议)也是一种客户/服务器的商谈,能够为无盘操作系统或布置成动态获取的微处理器提供IP地址、子网掩码、网关(路由器地址),以及DNS新闻。完成进度分二种情景:1、那与RARP工作条件一致,即客户与服务器在同一网段,BOOTP服务器被动打开UDP端口67,客户端通过UDP端口68发送请求,因为客户端不驾驭自己的IP地址,也不驾驭服务器的IP地址,客户机使用全0的源地址与全1的靶子地点,服务器通过单播或播报方式响应;2、客户与服务器在不一样网段,完成的措施是,每个网段中装置一个连贯代理,中继代理知道服务器的地点,其接收目的端端口为67的播放报文,就将该报文封装成单播数据报,然后发送给BOOTP服务器,服务器知道该报文来自于对接代理,因为在对接代理发送的报文中有其IP地址,中继代理收到BOOTP服务器的作答后,把它发送给BOOTP请求客户

7、DHCP

  DHCP(Dynamic Host Configuration
Protocol,动态主机配置协议)与BOOTP协议大约,但DHCP功用更强,不仅可以透过租期方便地落到实处动态分配,而且还足以提供除IP地址、子网掩码、网关及DNS以外的几十个网络参数

  [注意]ARP、ProxyARP和RARP也属于网络访问层,可以说ARP协议跨越OSI七层模型的二层和三层。正因为这么,一些地处网络层的防火墙对低层的ARP攻击显得心有余而力不足

传输层

  在TCP/IP网络中,IP采纳无连接的数额报机制,对数码举办“尽力而为的传递”,即只管将报文尽力传送到目标主机,无论传输正确与否,不做表明,不发确认,也不有限支撑报文的逐条。TCP/IP的可相信性浮现在传输层,传输层协议之一的TCP协议提供面向连接的服务(传输层的另一个说道UDP是无连接的)。传输层的主要职能是毫不费劲而又准确地传输并控制源主机与目标主机之间的音信流,提供端到端的控制,通过滑行窗口机制提供流控制,通过种类号和认同机制来确保可相信性。TCP传输控制协议发送数据分段时,可以有限支撑数据的完整性。流控制可以幸免发送数据的主机使接收主机的缓存溢出的问题,缓存溢出会招致数据的丢失。可看重的传导可以透过下列方法完成:1、接收方对吸收的多少分段向发送方进行确认;2、发送方向接收方重传所有未被肯定的数据分段;3、在目的端将数据分段按正确的各类重组,并删除重复的数目分段;4、提供幸免和决定拥塞的体制

1、TCP

  TCP (Transmission Control
Protocol,传输控制协议)是一种面向连接的传输层协议,能提供有限支撑的数码传输。在面向连接的环境中,伊始传输数据之前,端点之间先要建立连接。TCP负责将音讯拆分成数据分段,重传丢失的多寡分段井将数据分段在目标主机重组成音讯

  通晓TCP报头中的源端口、目标端口、连串号、确认号和窗口,有助于精晓TCP传输的可信性和TCP的滑动窗口机制

图片 15

  TCP/IP协议组常用的协议如图所示,其中使用TCP的应用层协议有FTP、HTTP、SMTP、POP3、Telnet和DNS等,使用UDP的说道有DNS和TFTP等

图片 16

2、UDP

  UDP(User Datagram
Protocol,用户数量报协议)是TCP/IP协议栈中无连接的传输协议,它是一种简单切磋,它调换数据报而从未确认机制或传输有限支持,错误处理和重传机制必须由上层协议来成功。从TCP和UDP的多少分段格式中得以看来,UDP的简单性卓殊显然。UDP磋商主要面向请求/应答式的交易型应用,一次交易往往只有一来两遍三遍报文沟通,如若为此而树立连接和撤废连接,花费是非凡大的,那种情景下利用UDP就那几个实用。其它,UDP共商也应用于那一个对可看重性必要不高,但必要网络的推移较小的场所,如话音和视频数据的传递

  组播一般接纳的都是UDP合计,很多播放教学软件使用的就是组播地址和UDP商事,助教机只须求发送一份数据到组播地址,所有的学员机出席这一个组播地址,接收教授机的播放教学,学生机的多少对讲师机的属性影响不大

图片 17

3、三回握手

  TCP协议是面向连接的,所以它在初叶传输数据在此以前须求先成立连接。要创立或初步化一个老是,两端主机必须同步双方的先导序号。同步是通过沟通连接建立数量分段和起来序号来成功的,在接二连三建立数量分段中涵盖一个SYN(同步)的主宰位。同步须求双方都发送温馨的开首序号,并且发送确认的ACK。此进度就是四回握手

  第三遍握手:主机A发往主机B,主机A的始发序号是X,设置SYN位,未安装ACK位

  第二次握手:主机B发往主机A,主机B的伊始序号是Y,确认号(ACK)是X+1,X+1确认号暗示己经收到主机A发往主机B的联手序号。设置SYN位和ACK位

  第三回握手:主机A发往主机B,主机A的序号是X+1,确认号是Y+1,Y+1确认号暗示已经接到主机B发往主机A的一块儿序号。设置ACK位,未设置SYN位

  三回握手解决的不只有序号问题,还解决了席卷窗口大小、MTU(Maximum
Transmission Unit,最大传输单元),以及所希望的网络延时等其他题材

图片 18

4、滑动窗口

  在多数可信赖、面向连接的数量传输中,数据分组必须以与发送时一致的逐条传输到接收端。任何数据分组丢失、损坏、重复或收受时乱序都将导致协议出错。最基本的缓解办法是让接收方在收受到每一个数量分段后都认账

  假使发送方在发送每一个数目分段后都要等待确认,吞吐量是很低的,
由此一大半面向连接、可信赖的磋商都允许三遍发送三个数据分段。因为发送方在发送完数据分组之后和拍卖完接收到的确认此前是有一段时间间隔的,那段距离可以用来传输越来越多的多寡。在并未接收确认的景观下,窗口是同意发送方发送数据分组的个数的

  TCP使用期待肯定,即认同号就是所愿意接收的下一个字节。滑动窗口是指在TCP会话中窗口大小是动态协商的。滑动窗口是一种流控机制,允许源装备在向目的设备发送一定数额的数码之后接到一个认可

  假诺窗口大小为3,源装备可以发送3个字节到目标设备,然后要求等待一个认同。目标设备接收到那3个字节之后,向源设备重返一个认可,那时候源设备就足以持续传输上边3个字节了。即使目标设备尚未接到那3个字节,它就不会回到确认,源装备尚未收取到确认,它就精晓那一个字节须求重传

图片 19

5、确认机制

  TCP在传输前,必要对每个数据分段举办编号。接收端主机将数据分段重组成完全音讯,TCP必须复苏由Internet通信系统造成的数据损坏、丢失、重复或乱序。TCP通过为传输的每个字节指定序号,并且需要接收端TCP的主动认可(ACK)来贯彻

图片 20

  如上图所示,1、源主机A远程登录目的主机B,源主机使用一个本地的肆意端口1058,访问目标主机的23号劳动端口。源主机先河序号是100,没有确认号;2、主机B收到主机A的数据包举办响应,重返的数量包源端口是23,目标端口是1058,主机B重回的包中的端口号和主机A发过来的端口号中的源和目的端口刚好相反。主机B的发端序号是1,确认号101代表已经吸收主机A的序号100,希望接受序号101的包;3、主机A对主机B发过来的包进行响应,发送的序号是101,确认号2表示曾经收取主机B的序号1

应用层

  应用层包含富有的高层协商,与OSI的应用层协议相差不大,包罗HTTP(超文本传输协议,使用TCP的端口80)、Telnet(远程登录协议,使用TCP的端口23)、FTP(文件传输协议,使用TCP的端口21和一个不确定的数据传输端口)、SMTP(不难邮件传输协议,使用TCP的端口25)、POP3(邮局3协议,使用TCP的端口110)、DNS(域名服务,使用UDP和TCP的端口53)等

样例输入 山姆ple Input

4 6 4

1 4 2

1 3 2

2 4 3

1 2 3

样例输出 山姆(Sam)ple Output

T

T

N

N

分析

经验:先弄通晓思路在做题,思路要科学。

原思路:区间查询和,查询区间内有多少空座位与特需的位子相比较(相比较艺术,a站到b站内剩余座位和与a站到b站必要的坐席和),但如此做肯定不对,如果座位都在末了面的站,而我辈无法把在后头须要的座在前面的空缺处找到并运用那些,“一笔业务无法拆分,也就是源点和终点站无法更改”就是那句话。

没错思路:操作明显是可以线段树维护的,注意一个距离[l,r]中r并不必要总结,所以只须求操作[l,r-1]就足以了(到r站就下车了)。大家只需求查询区间的矮小值就可以了,因为要是这些区间的蝇头值都可以满足的话,明显整个区间是足以满足的,线段树功效:区间维护最小值、区间查询最小值。

 

code

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 #define lson l,m,rt<<1
 5 #define rson m+1,r,rt<<1|1
 6 #define MAXN 60010
 7 
 8 int mn[MAXN<<2];
 9 int col[MAXN<<2];
10 int n,s,t,d;    //n城市,s座位,t订单 
11 void putup(int rt)
12 {
13     mn[rt] = min(mn[rt<<1],mn[rt<<1|1]);
14 }
15 void putdown(int rt)
16 {
17     if (col[rt])
18     {
19         col[rt<<1] += col[rt];
20         col[rt<<1|1] += col[rt];
21         mn[rt<<1] -= col[rt];
22         mn[rt<<1|1] -= col[rt];
23         col[rt] = 0;
24     }
25 }
26 void build(int l,int r,int rt)
27 {
28     if (l==r) 
29     {
30         mn[rt] = s;
31         return ;
32     }
33     int m = (l+r)>>1;
34     build(lson);
35     build(rson);
36     putup(rt);    
37 }
38 void update(int l,int r,int rt,int L,int R,int sc)
39 {
40     if (L<=l && r<=R)
41     {
42         col[rt] += sc;
43         mn[rt] -= sc;
44         return ;
45     }
46     putdown(rt);
47     int m = (l+r)>>1;
48     if (L<=m) update(lson,L,R,sc);
49     if (R>m)  update(rson,L,R,sc);
50     putup(rt);
51 }
52 int query(int l,int r,int rt,int L,int R)
53 {
54     if (L<=l && r<=R)
55     {
56         return mn[rt];
57     }
58     putdown(rt);
59     int ret = s;
60     int m = (l+r)>>1;
61     if (L<=m) ret = min(ret,query(lson,L,R));
62     if (R>m)  ret = min(ret,query(rson,L,R));
63     return ret;
64 }
65 int main()
66 {
67     scanf("%d%d%d",&n,&s,&t);
68     build(1,n,1);
69     for (int a,b,c,i=1; i<=t; ++i)
70     {
71         scanf("%d%d%d",&a,&b,&c);
72         d = query(1,n,1,a,b-1);
73         if (d>=c)
74         {
75             printf("T\n");
76             update(1,n,1,a,b-1,c);
77         }
78         else printf("N\n");
79     }
80     return 0;
81 }