You are given n segments on a coordinate line; each endpoint of every segment has integer coordinates. Some segments can degenerate to points. Segments can intersect with each other, be nested in each other or even coincide. Your task is the following: for every k∈[1…n], calculate the number of poi...

从前有个人名叫 WNB，他有着天才般的记忆力，他珍藏了许多许多的宝藏。 在他离世之后留给后人一个难题（专门考验记忆力的啊！），如果谁能轻松回答出这个问题，便可以继承他的宝藏。 题目是这样的：给你一大串数字（编号为 1 到 N，大小可不一定哦！），在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你 M 个询问，每次询问就给你两个数字 A,B，要求你瞬间就说出属于 A 到 B 这段区间内的最大数。 一天，一位美丽的姐姐从天上飞过，看到这个问题，感到很有意思（主要是据说那个宝藏里面藏着一种美容水，喝了可以让这美丽的姐姐更加迷人），于是她就竭尽全力想解决这个问题。 但是，她每次都以失败...

学习报告：主席树真的nb，如果朴素做要开n个线段树，内存爆炸，优化的方式，每次插入一个数，并不是整个权值线段树都改变了，只是改变logn个节点，我们只需要多开logn个节点就OK，用root数组记录历史个线段树版本，询问区间，可以做相减，询问第k小值，与左树的所有节点sum作比较，如果小就在左边，否则在右边，在右边的时候注意是k-sum，由于值域太大，可以使用离散化，获得每个数的排名，可以把值域缩小到n。 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring&...

题目背景 面对蚂蚁们的疯狂进攻，小FF的Tower defence宣告失败……人类被蚂蚁们逼到了Greed Island上的一个海湾。现在，小FF的后方是一望无际的大海， 前方是变异了的超级蚂蚁。 小FF还有大好前程，他可不想命丧于此， 于是他派遣手下最后一批改造SCV布置地雷以阻挡蚂蚁们的进攻。 题目描述 小FF最后一道防线是一条长度为N的战壕， 小FF拥有无数多种地雷，而SCV每次可以在[ L , R ]区间埋放同一种不同于之前已经埋放的地雷。 由于情况已经十万火急，小FF在某些时候可能会询问你在[ L’ , R’] 区间内有多少种不同的地雷， 他希望你能尽快的给予答复。 对于30%的...

校门外马路上本来从编号0到L，每一编号的位置都有1棵树。有砍树者每次从编号A到B处连续砍掉每1棵树，就连树苗也不放过（记 0 A B ，含A和B）；幸运的是还有植树者每次从编号C到D 中凡是空穴（树被砍且还没种上树苗或树苗又被砍掉）的地方都补种上树苗（记 1 C D，含C和D）；问最终校门外留下的树苗多少棵？植树者种上又被砍掉的树苗有多少棵？ 输入格式 第一行L和N,表示校园外原来有L+1棵树，并有N次砍树或种树的操作。 以下N行，砍树或植树的标记和范围，每行3个整数。 L（1 <= L <= 10000）和 N（1 <= N <= 100） 输出格式 共两行。...

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为 N 的数列，不妨设为 a1,a2,…,aN。 有如下三种操作形式： 把数列中的一段数全部乘一个值； 把数列中的一段数全部加一个值； 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 P 的值。 输入格式 第一行两个整数 N 和 P； 第二行含有 N 个非负整数，从左到右依次为 a1,a2,…,aN； 第三行有一个整数 M，表示操作总数； 从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作 1：1 t g c，表示把所有满足 t≤i≤g 的 ai 改为 ai×c； 操作 2：2 t g ...

每年的 1024 程序员节日，黑马程序员都会举办大型的庆祝活动。今年的程序员节也不例外，每个班级的同学都发了橙子。 班级里有 nn 名同学从前到后排成一排，且已经得知了这些同学的成绩，其中第 ii 名同学的成绩是 a_ia i ​ 。班主任想根据同学们上个阶段的考试成绩来评定发橙子的数量。为了激励成绩优秀同学，发橙子时需要满足如下要求： 相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样，则它们分到的数量必须平等。 每个同学至少分配一个橙子 由于预算有限，班主任希望在符合要求的情况下发出尽可能少的橙子。请问，至少需要准备多少橙子呢？ 输入格式 第一行是一个不超过 10^610 ...

Hanks 博士是 BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。 今天在课堂上，老师讲解了如何求两个正整数 c_1c 1 和 c_2c 2 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 a_0,a_1,b_0,b_1a 0 ,a 1​ ,b 0​ ,b 1​ ，设某未知正整数x满足：xx 和 a_0a 0​ 的最大公约数是 a_1a 1 ​ ；xx 和 b_0b 0​ ...

解题报告：如果用dfs做 就tle，其实我也没多大思路，就算想出来了状态转移，还是写不好状态初始，哎。。。我这里的dp[i][j]代表总和为i,j为分组。以最小值是不是1来分组，如果是1，减去这一组，如果最小值大于等于2，那么每一组都减去1就ok了 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #include&lt...

The inversion number of a given number sequence a1, a2, …, an is the number of pairs (ai, aj) that satisfy i < j and ai > aj. For a given sequence of numbers a1, a2, …, an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n s...

Holidays are almost over and our dear friend Mr. Potato Head wants to enjoy his last days of vacations with different fun activities like solving equations, calculating areas of figures, among others. Currently, he is playing with different strings, although he finds that most of strings are boring...

题 3 分值 13 一天蒜头君在想，[l,r][l,r] 之间有多少个数字是 dd 的倍数呢？ 但是区间 [l,r][l,r] 是 dd 的倍数的数字太多，于是聪明的蒜头君便找到了你。 当 l = 1032l=1032，r = 12302135942453r=12302135942453，d = 234d=234，dd 的倍数有多少个呢？ 程序 设计题F 一天蒜头君猜想，是不是所有的偶数（除了 22），都可以用两个质数相加得到呢？于是聪明的蒜头君就找你来验证了。 输入格式 第一行输入一个整数 tt 表示测试组数。 接下来 tt 行，每行一个整数 nn。 输出格式 输出两个整数，因...

Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test. And now we assume that doing everyo...

有两个长度均为n的字符串A和B。可以从A中选一个可以为空的子串A[l1…r1]，B中选一个可以为空的子串B[l2…r2]，满足r1=l2，然后把它们拼起来（A[l1…r1]+B[l2…r2]）。求用这样的方法能得到的最长回文串的长度。注意：求的不是本质不同的回文串个数哦！！！ 解题报告：找两个之间的最长回文串，只不过我卡了一下午而已，其实很简单，跑两遍马拉车，把两个字符串的len处理出来，开始枚举a的字符串的最后一个点，注意这里b的i-2是和a[i]是配对的，因为他们之间加了我们之前加过的字符，用tmp存他们的最大值，为什么呢？是为了减少匹配的次数，当他是最大值的时候不匹配也没事，因为可以是...