线段树 - Page 5

「BZOJ2325」[ZJOI2011] 道馆之战
Description口袋妖怪(又名神奇宝贝或宠物小精灵)红/蓝/绿宝石中的水系道馆需要经过三个冰地才能到达馆主的面前，冰地中的每一个冰块都只能经过一次。当一个冰地上的所有冰块都被经过之后，到下一个冰地的楼梯才会被打开。三个冰地分别如下：当走出第三个冰地之后，就可以与馆主进行道馆战了。馆主发现这个难度太小，导致经常有挑战者能通过，为了加大难度，将道馆分成了n个房间，每个房间中是两个冰块或障碍，表示一列冰地。任意两...
22014年7月26日7,066线段树,树链剖分

「BZOJ3702」「FJ互测」二叉树
Description(tree.c/.cpp/.pas)现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点，满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。要求进行一系列交换，使得最终所有叶子节点的权值按照中序遍历写出来，逆序对个数最少。InputFormat(tree.in)第一行n下面每行，一个数x如果x==0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x!=0，表示...
12014年7月24日4,878模拟,线段树
「BZOJ3693」「FJ2014集训」圆桌会议
问题描述有n组人要一起开一个圆桌会议（编号为0~n-1），会议的圆桌上有m个位置（编号为0~m-1）。每个组有ai个人，他们需要被安排在（li，(li+1)%m，(li+2)%m，…，ri）的座位范围内。每个座位只能安排一个人就坐，并且每个人都需要被安排一个座位。现在你需要判断是否存在满足条件的座位安排。输入格式输入包含不超过10组数据。第一行有一个数字T，表示数据组数。接下来有T组数据，每组数据第一行包含两个数n，m，表示有多少组的...
02014年7月23日5,619线段树
「BZOJ3694」「FJ2014集训」最短路
题目描述给出一个n个点m条边的无向图，n个点的编号从1~n，定义源点为1。定义最短路树如下：从源点1经过边集T到任意一点i有且仅有一条路径，且这条路径是整个图1到i的最短路径，边集T构成最短路树。给出最短路树，求对于除了源点1外的每个点i，求最短路，要求不经过给出的最短路树上的1到i的路径的最后一条边。输入格式第一行包含两个数n和m，表示图中有n个点和m条边。接下来m行，每行有四个数ai，bi，li，ti，表示图中第i条边连接...
02014年7月20日5,459线段树,树链剖分
「FJ2014集训」信心题
「题目描述」在二维平面上有若干个多边形，每个多边形都覆盖了一定的区域，它们之间有可能重叠，请求出这些多边形遮住了多大的平面区域。即，求多边形的面积并。「输入格式」本题为提交答案题，共有10个输入，分别是cover1.in∼cover10.in。每个文件第一行，一个整数，表示这个输入文件的序号(1∼10)。接下来一行，一个整数n，表示这组数据中有n个多边形。接下来n行，每行第一个整数Pi，表示这个多边形有Pi个点，接下来有Pi组整...
02014年7月20日3,938线段树,几何
「CODEVS3044」矩形面积求并
题目描述Description输入n个矩形，求他们总共占地面积（也就是求一下面积的并）输入描述InputDescription可能有多组数据，读到n=0为止(不超过15组)每组数据第一行一个数n，表示矩形个数(n<=100)接下来n行每行4个实数x1,y1,x2,y1(0<=x1<x2<=100000;0<=y1<y2<=100000)，表示矩形的左下角坐标和右上角坐标输出描述OutputDescription每组数据输出一行表示答案样例输入SampleInput[crayon-690e76ff7d4e1806...
52014年6月18日12,639线段树
「BZOJ3295」[CQOI2011] 动态逆序对
Description对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。Input输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。Output输出包含m行，依次为删除每个元素之前，逆序对...
42014年6月17日8,739树套树,线段树,树状数组
「BZOJ1012」[JSOI2008] 最大数maxnumber
Description现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：QL功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作。语法：An功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有...
42014年6月15日11,055线段树,单调栈,单调队列
「BZOJ1146」[CTSC2008] 网络管理Network
DescriptionM公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通...
22014年6月13日8,194treap,树套树,二分法,线段树,树链剖分
「BZOJ3531」[SDOI2014] 旅行
Description S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，...
32014年6月13日7,735线段树,树链剖分
「BZOJ1651」[Usaco2006 Feb] Stall Reservations 专用牛棚
DescriptionOhthosepickyN(1<=N<=50,000)cows!TheyaresopickythateachonewillonlybemilkedoversomeprecisetimeintervalA..B(1<=A<=B<=1,000,000),whichincludesbothtimesAandB.Obviously,FJmustcreateareservationsystemtodeterminewhichstalleachcowcanbeassignedforhermilkingtime.Ofcourse,nocowwillsharesuchaprivatemomentwithothercows.HelpFJbydetermining:*Theminimumnumberofstallsreq...
02014年5月28日4,215线段树
「BZOJ1828」[Usaco2010 Mar] balloc 农场分配
DescriptionInput第1行：两个用空格隔开的整数：N和M*第2行到N+1行：第i+1行表示一个整数C_i*第N+2到N+M+1行：第i+N+1行表示2个整数A_i和B_iOutput*第一行：一个整数表示最多能够被满足的要求数SampleInput541321313252345SampleOutput3题解贪心，按照右端点排序以后冲突的舍弃[crayon-690e76ff7f217358395255/] ...
02014年5月28日4,175贪心,线段树