随机分布的三维最近点统计问题。。
注意到点是随机分布的。。弄个KD树瞎搞。。。

首先这个题解基本上是看Petr的分析和rng_58的代码。。
题目自己去看TC看吧囧。。
第一题：
此题看上去很容易。。其实很恶心。。各种贪心很容易悲剧。。
最好的办法是用对偶原理
就是最小必定可行值=最大不可行值+1
我们只需要通过DP求得最大不可行值即可。。
状态可以是Dp[i][win][lose]表示前i个位置，win个位置取得了胜利，lose个位置挂掉了的最大投票数。。
然后DP出这个玩意。。。
再以此求出最大不可行值就可以了。。
第二题：
这个题目很囧。。由于机房要关门了。。晚上再发。。
第三题：
首先显然对于一个特定的取方格的方式，只有RGB的数量有关系。。
然后欲处理一下。。枚举出所有可行的R，G，B的数量。。
然后我们枚举R，G的数量，设Max[r][g]为R选r个，G选g个，B最多有几个。。
那么如果我们无视那个两个串翻转之后一样算一个的条件。。
设Max[r][g]=b
那么在这种情况下。。答案为C(r+g,r)*(C(r+g,0)+C(r+g+1,1)+C(r+g+2,2)…+C(r+g+b,b))
那么看右边(C(r+g,0)+C(r+g+1,1)+C(r+g+2,2)…+C(r+g+b,b))
。。这式子只跟r+g和b有关系。。所以随便预处理一下就OK了。。
然后考虑翻转的条件。。只要算出所有对称的字符串的数量就OK了。。
而对称的字符串由前半部分决定。。。
用一样的办法就可以了。。
注意一下处理长度的奇偶性。。。
//嘿嘿。。我是WJMZBMR的分割线
看了这些题目之后。。我感觉TCO的难度其实是不及NOI的。。。
由于时间限制的原因，TCO的题目也不会考那种特别难的算法或者数据结构。。。
但是题目还是很考验各种能力的。。rng_58确实是强到极点了。。Orz Sro Orz。。。
我决定去看看他之前在各种SRM和TCO中的代码。。。从中吸取经验囧。。。
//嘿嘿。。我是WJBZBMR的分割线。。
其实。。我打算再去弄场模拟赛。。大家说是搞成ACM形式放在BZOJ上好呢？
还是搞成OI形式放在TYVJ或者RQNOJ上好呢？

其实这题是没神马好讲的。。关键是程序风格神马的。。
我决定不盲目模仿开哥，探索一下自己的风格。。
首先我觉得开哥的namespace非常神犇。。但我觉得把主体和定义声明分开总归有点不爽T_T囧。。
所以我还是用了namespace。然后我直接在namespace里面写程序。。就不分开了。。
然后我写了一些库。。比如
namespace Constant
{
const int ND_MAX=500000+10;
const int inf=~0U>>2;
const int CM_MAX=100;
}
namespace Function
{
inline int Max(int x,int y)
{
int m=(x-y)>>31;
return y&m|x&~m;
}
template<class T>
inline void Swap(T&a,T&b)
{
T c=a;a=b;b=c;
}
}
namespace Scanner
{
inline void scan_str(char*s)
{
char c;while(c=getchar(),c==’ ‘||c==’n’);*s++=c;
while(c=getchar(),c!=’ ‘&&c!=’n’)*s++=c;*s++=’’;
}
inline void scan(int&t)
{
int sign=1;char c;
while(c=getchar(),c<‘0’||c>’9’)
if(c==’-‘)break;
if(c==’-‘)t=0,sign=-1;
else t=c-‘0’;
while(c=getchar(),c>=’0’&&c<=’9′)t=t*10+c-‘0’;
t*=sign;
}
}Scanner的名字来源于Java囧。。
然后要用的时候就using一下就可以了。。
然后为了感觉一下这种编程方式。。
我决定去A这道XX的Spaly维护题。。。（裸的数据结构神马的，最喜欢了）
写了很久。。
1A嘻嘻。。。（第一次交的5KB那个没写完。。纯属保存代码囧。。）
Code非常囧。。写了10KB+。。见网盘。。

。。我似乎打文章名都有OI的风格了这。。。
数学联赛似乎RP不错。。。尽管我已经几乎N久没有碰数学了。。。但对那个组合和数论的题目还是有点感觉囧。。
然后考试的时候1试挂的很惨。。很多题目都跳着做。。解答错了2道。。刚刚看了答案之后一对是68的样子囧。。。
2试的时候本来我是想全不会做然后打酱油提前交卷的。。结果发现组合题很水。。于是我弄了一会儿A掉了。。
然后我就想我反正几何代数都不行。。于是就去试图做数论。。发现也是水题这。。。
然后我直接在总分中扣除了几何题的分数（就是无视掉了囧。。）去做代数。。。
其实那题感觉还是挺可做思路很多的。。但是由于我过于傻叉。。证了半天以为自己没错。。。
到快结束的时候发现我那么证有漏洞。。。修复了半天发现必须要n>=10（这。。。）。。。
于是我只好写:手工验算得，当n<10时结论成立。。
。。。。。。。。。。。。肯定0分。。。。
总哦那个也就90+68 150+的样子了T_T。。得奖是没戏了囧。。
Orz 豪哥虐爆全场无压力200+
Orz 高远神犇虐爆全场无压力200+。。

真囧。。。
今天去了14中参加了比赛。。然后发现14中门口有一个巨大的屏幕在播出一些宣传片，其中就有Lou Tian Cheng Win The First Price In IOI.。。果断Orz楼教主，然后14中还有2个人生物拿过国际金牌啊。。Orz。。。。。。
然后来的有点早。。。于是就想去见一下学军的gaoxin和lichao神犇，不过惊讶的发现没有学军的考场是设在图书馆囧。。然后就没找到T_T。。快开始的时候在考场里进来了两个帅哥（事后知道是gaoxin和lichao神犇。。）。。我居然没有认出来。。这。。太囧了。。话说两个神犇长的都很帅啊。。Orz Sro Orz。。。。
然后又见到了杭二的某个猥琐男WQX。。这家伙物理都1=了还来混NOIP。。Orz囧。。。
然后考试。。。
这。。我太SB了。。由于去年初赛选择题挂了N道，后面还可以。。于是考试前完全没有复习过程序填空神马的。。。就是仔细复习了一下各种知识。。。。。
然后我就悲剧了。。求答案第三题我SB的写了17。。。没有多想。。我的数学是不是白学了囧？
然后看程序写结果也错了一题。。。程序填空也错了个。。让我去死吧。。
单选很信春哥的全对了。。但多选错了一个囧。。HTTP完全不会T_T。。。
Orz NZK神犇96.5 GX神犇92.5 。。。。。

我某日在颓废的时候突然思索出这个傻叉的数据结构。。。可以在比O（N）小的时间内在线支持几乎一切询问（不能修改）。。。
但非常的傻叉。。。。
比如说考虑这个问题。。给出一个数列，每次询问从第l个到第r个中有几个不同的元素。。
。。。一定要在线。。
那么。。我们把这个数列分成L块，然后对每个第l块到第r块这样的子序列储存一个当前的结果。
然后计算的时候。在能使用的信息基础上，可以在O（N/L）的时间完成询问，然后再恢复。。
注意到需要的空间和预处理时间是L^2N的。。。所以L不能取很大。。比如说取个N^0.25次方。。
就能在N^1.5完成预处理，N^0.75完成询问了。。。
这。。。似乎对几乎一切的问题都适用。。。但速度可以去死了。。

题目是这个。
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1975
裸的K短路，A*就可以了。。。
我上次由于代码风格过差被T神骂了。。所以去Orz了开哥的代码。。。感到压力非常大。。
就把我写的这个贴出来吧囧。。。

总的来说感觉还不错。。不过就是觉得把所有函数定义和主体分开来写工程的时候是很好。。但搞OI就有点囧了T_T。。
http://www.ideone.com/lDlIh

尽管比赛的时候还是很多题不会做。。不过上了nimendongde这个号看了lichao神犇和gaoxin神犇的程序之后。。总算全部都会了囧。。。
Orz Sro Orz gaoxin&lichao神犇
A，纯模拟题。。直接上就好了。。但是我一开始用cin TLE，然后改成C的后不知道哪里写二了WA囧。。
最后是gaoxin神犇做的。。我太弱了囧。。。
B,纯数学题，我一开始做WA，最后是lichao神犇A的囧。。
设上面切了A次，侧面切了B次，克隆了C次，
那么A+B+C=M
(A==0?1:2A)*(B+1)+C=N
若A为0，那么得到N=M+1。。显然此时答案为0。。
若N<M+1。。那么由于每次操作之后块数增加。。。显然是无解的。。。
那么现在A>0
解得：
2*A*B+A-B=N-M.
考虑配平。。
(A-1/2)(2*B+1)+1/2=N-M
(2A-1)(2B+1)=2N-2M-1…
然后就nimendongde了。。
枚举右边的因子。。。
C：
按最短路建图，可以发现求是求一个ACG中经过一个点的路径数。。
然后设in[t]为0->t的路径数，out[t]为t出发点路径数.
那么in[t]=Sum{in[i],有边i->t}
out[t]=Sum{out[i],右边t->i}+1。。
然后乘起来就OK了。。
注意10^10*10^10会超long long
a*b=2*a*(b/2)+a*(b%2)。。。
于是二分的乘法（这。。。）就可以避免爆long long了囧。。。
D：
非常恶心的计算几何，gaoxin神犇太强了。。硬是A掉了Orz Sro。。。
各种麻烦。。。
E：
首先将所有trap按Di排序，然后一个个处理，记录当前消耗时间的和now，
每次遇到一个trap，如果它加进去之后now超过了它的D。。
那么就把当前要修复的所有trap中花费时间最大的给删掉。用堆来维护就可以了。。
F:
很简单的DP。。就是要高精度。。
然后注意到要输出约化的分数，由于分母是b-a+1的n次方。。这个玩意的质因数不多。。
一个个的两边都除过去就可以了。。
我用Java强A掉了囧。。。
G：
注意对一个ai，我们的di肯定是它的因子，然后一个数的因子数一般是比较小的，所以我们可以枚举。。
然后考虑一个di，我们需要知道在x到y有多少数t
最大公约数（ai,t）=di。。
这个可以用容斥原理解决。。
具体的说就是设F(n)表示x到y之间有多少数与ai的最大公约数为n。。
那么F(n)=x到y之间n的倍数-Sum{F(m),m是n的倍数}。。。
算出这个就可以直接DP了。。
H：
这个太囧了。。
要各种分情况讨论：
设a<b
a=0 b=0:此时就是一个点，该点的情况决定一切
a=0 b>0：此时是一维的情况，就是满足条件的线段长度/线段总长度b
a>0 b>0：此时是二维的情况，画出图来可以发现是两条线去切一个矩形。。。
还有一点。。。就是当答案=0的时候。按上面这么写甚至有可能输出-0.000000
这。。。。
I：
计算几何的水题。。不多说了囧。。。
J：神犇题啊。。。gaoxin和lichao神犇的做法太强大了。。严重Orz！！！！
首先考虑O(n)的做法。。
注意到可以列期望方程F[n]=pre*F[n-1]+nxt*F[n+1]+1
pre和nxt分别是向前和向后走的概率。。
那么解方程就是n^3了。。
但这题跟上次CF的某题很像。。这个矩阵是一个Tridiagonal_matrix
http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm
所以可以O(n)求解。。
然后测试组数过多。。。O（n）TLE囧。。。。
n=2的情况很很囧。。
可以发现m=2的情况关于n成二次关系。。是一个n的二次函数。。
若m>2
设F(n,m)为答案
然后神犇们似乎是发现当n变大了之后F(n+1,m)-F(n,m)快速趋向于常数。。。
所以只需要计算很少的n。。当这个常数变的足够稳定之后。。就可以直接给答案了。。
复杂度不清楚。。但0msAC了囧。。。

哇咔咔。。我们队A光了所有题目！！！！！
比赛前。。我跟高欣神犇和李超神犇组了个队。。队名就叫nimendongde嘿嘿。。。
然后去参加比赛。。
我一开始去做B。。然后各种WA。。又去写A。。还是各种WA。。然后我囧死。。
然后李超神犇去做B。。A掉了。。我连A都写错囧的要死。。后来高欣神犇去A掉了A..
不过我也造成了巨大的罚时。。。幸好没别的人AK囧。。
然后高欣神犇发现I是水题，就A掉了。。
同时高欣神犇也A掉了E。貌似是道几何题。。。接着我发现F似乎是道水题，不过需要高精度，就写了Java。。1Y了。。
然后我去做C。。发现是个图论的XX题。。于是强A。。
但我发现似乎这题有点猥琐。。因为10^10*10^10会超long long。。
幸好a*b=2*a*(b/2)+a*(b%2)。。
所以可以二分做乘法
然后J是道非常BT的题目。。我是毫无思路。。李超神犇有O（n）的做法。。但是会TLE。
一直也没有神马好点的办法。。李超神犇最后还是A掉了。。太神犇了Orz！！
接着我去作G。。。一开始没有处理好。。
导致TLE。。不过最后通过各种努力。。还是A掉了。。
gaoxin神犇则一直在写D。。一道非常XX的计算几何题。。
但是因为精度神马的问题。。一直在悲剧。。
最后换成long double。。于是A掉了。。
当时我们队8题。。有队9题。。。时间已经不多了。。
然后是J题。。。李超神犇在最后关头A掉了。。方法我也不知道囧。。
然后H题是XX的几何。。非常恶心。。有各种XX的特况。。我WA了好几次也终于A掉了。。。
然后在还剩几分钟的样子我们AK了。。
。。话说三道Special Judge的题目全是我A的囧。。是不是因为我常上SPOJ的缘故囧。。。

题目大意：
维护一个数据结构，支持两个操作：
给一段数+/-上一个值
求最大前缀和。
哇咔咔,我是数据结构控！！这种裸的数据结构神马的最喜欢了T_T。。。
。。。首先。。看AC人数这么少。。线段树肯定不可做。。。
然后肯定要。。块状数组。
分成根号N块，
那么在每块中的最大前缀和必然是前面块的和+这块中内部的最大前缀和。
可以发现，如果一个块整体增量为a，我们需要知道Max(S[i]+a*i)
。。用凸包XX维护一个块。。可以LogN搞出这个结果。。。
然后每次增加会有一个块被重构，其余都只要增加块增量的标记。。
询问也差不多。。。