The Way Through The Forest

BZOJ 3343 and Chunks Problem Statement There are N≤1000000 counters. You are asked to do Q≤3000 actions on these counters, either: Increment all counters between L and R by W, given that 1≤L≤R≤N and 1≤W≤1000. This command will be in the format "M <L> <R> <W>", where L, R, and W are integers. Count the amount of counters between L and R and are greater than W, given that 1≤L≤R≤N and 1≤W≤1000. This command will be in the format "A <L> <R> <W>", where L, R, and W are integers. Core Idea Any array of integer size N can be broke up into √N+1 chunks of √N elements each for the first N blocks and then the remainder amount for the last block. Although this may seem as  the bloody obvious at first, splitting up an extremely large array into chunks and then doing work on the chunks can make a program vastly more efficient. There are various example: Searching - if a block's lowest value is above the targe...

POJ 2352: Stars Problem Statement Stars Time Limit:  1000MS Memory Limit:  65536K Total Submissions:  49960 Accepted:  21558 Description Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars. For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3. You are to write a program that will count the amounts of the stars of each level on a given map. Input The first line of the input file contains a number of stars N (1<=N...

POJ 2155: Matrix Problem Statement Matrix Time Limit:  3000MS Memory Limit:  65536K Total Submissions:  29825 Accepted:  10900 Description Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N). We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using "not" operation (if it is a '0' then change it into '1' otherwise change it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions. 1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2). 2. Q x y (1 <= x, y <= n) querys A[x, ...

ACM-ICPC Live Archive 4329: Ping Pong My Problem Version Given N (3 ≤ N ≤ 20000) distinct numbers, a 1  , a 2  ,  a 3 ... a N , each not more than 100000, how many ways can we select a pair of three numbers, a x  , a y  , and a z  , such that a x < a y  < a z   and x < y < z? Note: x=1, y=2, z=3 is different from x=2, y=1, z=3. The Algorithm We can take a hint from "... how many ways can we select ..." that this would involve prefix sums. Since we are asked to select the way to make 3 things, we would need to make 3 prefix sum arrays... unless we try to consider the problem from a y  's point of view: the amount of ways to select a number to "its" left and smaller times the number of ways to select a number to "its" right and bigger is the amount of ways to create a pair where "it" is  a y . We do this for every possible value of y. Wait a minute... smaller and to its left ... larger and to its...

NOI China 2002: Legend of Galactic Heroes Original Problem Statement 描述 公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。 然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。 在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。 最终的决战已经展开，银河的历史又翻过了一页…… 格式 输入格式 输入的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。 以下有T行，每行有一条指令。指令有两种格式： 1.M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。 2.C i j ：i和j是两个整数（1<=i , j...