【AC_LCC_CWJ 第四场】Algorithmic Engagements 2009 & 【第一把SRM】

【AC_LCC_CWJ】

 本场纯打酱油……

就切了J题这个线段树。

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22200

【题目大意】

给一个A[1..n]，问是否存在1~n的一个排列，满足所有p[i]<=A[i]。然后后面还有m次修改，每次修改某个位置的A[i]的值。

n,m<=200000     1<=A[i]<=n

【算法分析】

……令Sum[k]表示数组A[i]里包含多少个<=k的数字。然后这个判定性问题转化为是否所有Sum[k]<=k。

然后就用线段树维护所有Sum[k]里，Max(Sum[k]-k)是不是小于等于0，如果是就满足，否则不满足。

【其它】

还想了好一会儿，真是太弱了。

【CODE】

http://xiudaima.appspot.com/code/detail/4489019

哎，弱得一塌糊涂……神马都弱

========================================================================================================

然后是昨天晚上的第一把SRM。

Orz，一进去就见到WJMZBMR和zbwmqlw！！！

WJMZBMR还被人用中文膜拜……

然后看到很多熟悉的ID，像swgr，RoBa之类的…

膜拜完以后开始比赛，显然第一把必须DIV2。

250神马二叉算法都能秒，直接暴力枚举。然后编译了半天不成功，都不知道干神马……

弄了好久，发现语言选了JAVA

接着打开500，据说就是DIV1的275。

觉得就是左边扫一遍右边扫一遍，得到每个位置的上限和下限，于是直接枚举。复杂度就是O(N√N + M)。

Orz表示1000^2 * 50毫无压力的神犇们！！！原来TC的精髓就是暴力……

搞完以后看到最后一题瞬间被秒。。。最后没有交1000。

其实当时的想法很接近正解，也是求连通块，就是没想出每个连通块有n!/2种方案。

好像DIV2里面也没有多少个交1000的……居然搞了DIV2里面第6，Rating一下变到1700+，然后名字就变成黄色了。。。

今天听说别人TC都用插件，下了个KawigiEdit，导入了以后再里面点Run Test Case显示神马g++不行之类的，鸭梨山大。改天再搞一搞。

刚在调这个KawigiEdit的时候被zbwmqlw神牛喊了一声没有听到Orz~罪过罪过