codeforces 466 C. Number of Ways

http://codeforces.com/problemset/problem/466/C
题意:给定一个序列。要将序列分成三个非零的连续部分,使得三部分的和相等。问有多少中分法。
思路:首先可以知道,如果是序列的和不为3的倍数,那么一定无解,输出0.设序列的和为sum,那么每一部分的和就应该为sum/3。我们可以预处理出从1开始的和为sum/3的点(我开了数组表示前缀和。。想了下其实不用。。我只需要点的信息。。所以用一个变量表示即可),将点的下标存在p[i]里。对于每一个p[i],我想要知道比p[i]大且补与p[i]相邻的点中,有多少个j,使得从j到n的和为sum/3。因为如果有两部分的和都为sum/3,那么剩下的那部分也一定为sum/3.然后要知道有多少个满足题意的j,我们可以从后往前扫一遍,标记从n开始往前扫,和为sum/3的点,可以用一个0,1数组表示。如果和为sum/3,那么标记为1,否则为0.然后再用一个类似前缀和的思路。再开一个数组c记录从j到n有的和为多少,也就是从j到n有多少个点满足该点到n的和为sum/3.

预处理完这些之后。只需要从前往后扫一遍p[i],然后ans+=c[p[i]+2]即可。

 

 

 

 

hdoj 1754 I hate it

http://acm.hdu.edu.cn/showproblem.php?pid=1754
题意:给定一个区间,有m组操作,操作可以是改变单点,或者查询区间最大值。对于每组查询,输出。
思路:分块。这篇博客说得很不错。http://www.cnblogs.com/sweetsc/archive/2012/08/15/2639395.html