似乎没人发的样子。。我写个吧囧。。。神犇请鄙视。。。
第一题似乎是IOI的原题的改编版。。只要看过今年IOI的题目应该都会的。。
首先二分答案X，我们需要判断能否有一个长度在L到R之间的奇数的序列中位数大于等于X。。
我们定义一个新序列Ci，若Ai>=x,Ci=1否则Ci=-1。。那么可以发现只要一个序列的C值和>=1。。
这个序列的中位数就大于X。。那么我们只需要算出C序列长度位在L到R之间的奇数的子序列的最大值就行了。。单调队列。。。
第二题首先可以发现每一位是独立的，那么对每一位都可以维护一个线段树进行经典的翻转和求和打标记等操作。。（实现的时候为了不TLE。。最好放在一起。。）
第三题网上有详细的题解。。我就不多说了。。是查分约束的题目。。。
第四题。。。题目的子树是子连通图的意思。。。
设两棵树为A和B
设Dp[a][b]为A中以a为根的子树，B中以b为根的子树同时a和b必须选的答案。
那么我们可以发现计算Dp[a][b]的过程就是给a的孩子跟b的孩子一一配对，他们配对的价值正是Dp的子结果。。
那么我们其实要做的就是求出最优匹配。。用KM或费用流就可以了。。（我居然不会KM。。临场写费用流。。。）

最近做了N场模拟赛囧。。。
Orz6：
感觉还不错。。前3题都会了。。但是第四题始终不会做。。只好骗分。。。感觉发挥的还可以。。唯一要记住的就是第一没有看清范围。。居然用了long long的。。
USACO NOV：
题目还不错。。但是我傻叉到第二题的dp想了非常久。。因为我一开始就想到的是凸包优化的模型。然后没有发现其实单调队列就差不多了。。这提醒我一定要简单化问题啊。。不能想复杂T_T。。还有第一题算法很麻烦。写错一个就可能WA。。这样的题目一定要狂对拍+仔细检查啊。。。
愿望群：
题目显然不属于NOIP范畴这。。。第一题是IOI某题的加强版。。第二题时间卡的太囧了。。我看了题目没多想就用了16*NLogN的线段树。。被卡的只有30分。。标程是5*NLogN的。。太神了T_T。。因为异或的运算每一位是独立的。。一定要记住这一点啊。。第三题不会做。。本来可以骗个40分的。。结果因为我被第四题的一个傻叉编写错误卡住没来得及写。。第四题看了题目之后错误的以为是hash。。想了半天还是悲剧了。。。最后才发现是KM+DP。。但是写了半天之后发现居然忘了KM怎么写！！！这。。。算法不够熟练啊。。只好赶紧改成费用流。。不知道为神马只有80分。。
总结：
我就是个大弱菜。我怎么这么弱啊这么弱啊这么弱啊T_T。。。

额。。下周就要比赛了。。做个正式的通告。。
首先比赛放到orzoj上了。。这个oj界面非常漂亮。。。
网址是http://www.orzoj.org/
我已经把上次模拟赛的题目放上去了。。这次的也一样吧。。
然后如果OJ挂掉的话（只是以防万一。。一般是不可能挂的。。）
交到WJMZBMR@gmail.com这个邮箱
同时我也会提前半小时放出比赛的pdf版本。。。并加密。。到时候公布密码
（gaoxin你破不掉的破不掉的破不掉的）。。
比赛会分成两部分。。第一部分是晚上6点到10点的模拟赛（题目有点xx。。。加长一小时好了。。）
第二部分是整个周末的娱乐赛。。。（题目非常xx。。一个周末好了。。）
然后是奖品的问题。。两部分分开评奖吧。。
第一部分前5名+10QB
第一部分AK +10QB
第二部分前5名+10QB
第二部分AK +30QB
可以重叠。如果你双AK又双前5就有60QB了嘻嘻。。。
审题人退散～～～～～不许抢钱
这。。为了让大家欢乐一点。。每题都会有点暴力分。。
全暴力估计也可以200分。。。

PS。题目描述精选：

LC同学在2011年的浙江省选中轻松虐爆了WJMZBMR，无压力进入省队并参加了NOI 2011，在1个小时之后，A光了所有题目的LC同学轻松的喝着茶，哼着小曲。
由于在信息学方面的杰出表现以及LC同学的父亲是伟大的LG同志。
LC同学轻松获得了2012年诺亚方舟的船票。并且得到了卖票员这一肥差。

GX同学由于风流倜傥玉树凌风貌似刘德华神似陈冠希酷似tourist，受到了众多小女生的倒追，从杭州排到北京又排回来。GX同学感到压力非常大，就请WJMZBMR同学帮助他把关。WJMZBMR把99.999%的女同学都赶走了。。还是有N个人。。

GYZ和CYX同学在IOI上见到了tourist，GYZ和CYX虎躯一震，散发王者之气，tourist纳头便拜，在秒杀了tourist之后，GYZ和CYX开始了IOI第一的争夺。。。。

JZP开发出了贾氏图表为了爱秒杀一切NPC问题之后，由于世人过于愚昧无知，没几个人学的会，JZP倍感神犇寂寞，于是又开发了一个简化1000000^1000000倍的贾氏小图表，然后大家还是不会。。再重复了1000000^100000之后。。终于有人能学会了。。JZP图标能O(1)解决以下问题。。。你能吗？

384.Country
唬人题。。可以发现给定图肯定是一个root下面挂着N个三角形。。。
然后就随便搞搞了。。
369.Game
这个题目也差不多。。若两个点x和y分量中有一个是一样的，在他们间连一条边。。然后求连通分量。。
可以发现每个联通分量必然会变成一个矩形。。算出长和宽就OK了。。。
//我模拟赛题目的来源～～
389.Strange Planet
考虑每个位，结合3个串的话有8种可能性。。可以根据对称性之考虑4种。
就是
0   0   0   0
0   1   0   1
0   0   1   1
A1A2A3A4
。。。然后设Ai中有Bi结果串选了0.。
就可以列个方程。。
就可以发现B1确定了。。everything 确定了。。。
枚举B1就可以了。。。
394.空间点维护问题。。直接二维线段树硬搞。也可以离散掉之后用一维线段树搞。/
393.各种搜索。。。

 额。。这是我第二次办模拟赛～～上次的灰色头像模拟赛参加的人好少。。。。。可能是因为时间过于仓促的原因吧。。上次的模拟赛还有一些小bug之类的。。。不过我也吸取教训了。。。经过一些XX的准备。。决定开始办第二场模拟赛。。。时间定在11月12日晚上7点到10点（跟NOIP吧上的通告比。。提前了1小时。。）
题目灰常和谐。。。一共5道题目。。。前4题是算总分的。。跟NOIP差不多～～。。最后一题就不算了。。而且最后一题到晚上12点都可以单独提交。。AC的奖QB10个。。。
前5名奖10QB（贴钱办比赛。。我容易么T_T。。。） 
比赛还是采用邮箱+手测的方式。。届时会在NOIP吧上开贴答疑。。
tieba.baidu.com/noip
邮箱是WJMZBMR@gmail.com 
P.S。。求神犇帮忙审题。。。
剧透：第一题叫“我爸是李刚”

     写个模板。。在面对TC和CF的时候可以毫无压力。。。
http://www.ideone.com/bP3MN

最近悲剧的事情特别多。。首先我的BZOJ帐号被盗了。。。我怎么有种我的过去被人抢走了的感觉。。
好吧。。也许BZOJ是该告一段落了。。正好也是警告我不要为了AC数做题吧。。以后就用小号算了。。
也没神马。。
然后可能就要转这去刷SGU了。。。。
其次我BZOJ 1841看了题目一开始没有想好。。写了个XX的点分治。。细节爆多。。各种恶心。。写到18KB。。结果发现既MLE又TLE。。其实是可以树链剖分的。。我也想到了。。但当时我觉得写了那么长了就放弃太可惜了。。哎。。真悲剧。。
然后HDOJ的比赛又被虐成傻逼。。。半天才过1题。。。
然后昨天CF的比赛的最后一题接近TC原题。。对我这样的TC党本来应该是很happy的事情才对。。
结果我碰巧没有看到那题过。。导致悲剧。。。
我怎么这么背啊。。我怎么这么弱啊。。。
近期要做的事情：
接着看TC。。从头看到尾。。
应付期中考。。
应付NOIP。。
写一堆模板：空间几何、凸包、各种字符串算法、各种网络流、各种平衡树，还有块链。。

A Problem For Fun

Time Limit:50000MS Memory Limit:265536K
Total Submit:7 Accepted:2
Case Time Limit:10000MS

Description

给出一个N个结点的树，每条边有一个正整数权值，定义两个结点的距离为连接这两个结点路径上边权的和。对于每个结点i，它到其他N-1个结点都有一个距 离，将这些距离从小到大排序，输出第K个距离。

Input

输入文件总共N行。第一行有两个正整数N和K。下面N-1行每行描述树的一条边（保证这些边可以构成一棵树），每行三个正整数u、v、w，表示从结点u到 结点v有一条权值为w的边。
输入文件保证：N <= 50000, K < N, u <= N, v <= N, w <= 10000。

Output

输出文件总共N行，每行一个正整数，第i行的数对于结点i的答案。

Sample Input

Sample Output

Source

陶文博

这个题目解法有好多。。真是道好题。。我有时间写个完整一点的解题报告罗列一下解法。。
我写的是边分治。。因为比较好弄。。
首先通过添加辅助点的办法让点的最大度数为3。。
具体的说就是对于每个度数大于3的点。。
比如说度数为d,构造d个点，每个点分到一个边。。同时这d个点用长为0的边连起来。。
然后边分治。。找到分治的边。。
那么一个点出发的所有路径最多出现在LogN个分治中。。
考虑“一个点出发的路径长度<L的有多少个”这样的询问。。
我们可以通过排序的办法在LogN^2回答这个问题。。
然后通过二分来回答K近顶点的话。。
就是LogN^3了。。
N个点就是NLogN^3
好说不好写。。写了9KB+。。
解法2：
这个想法来自twb。。就是dfs一棵树的话。。
用一个数据结构维护树的dfs序列。。
那么一个字树是一个区间。。
注意到我沿着一条边移动。。设从i->j。。
那么j对应的区间到当前点的距离全部降低cost(i->j)
其它的点全部增加cost(i->j)
那么我们要回鹘一个数据结构。。
支持:
给一段数都增加一个值。。
找所有数中的K大。。
这个情况没有办法用神马有效的办法解决。。只能块状了。。
块状的话找K大还是得先二分。。就有个LogN了。。
就是转变成解决询问比一个数小的数有几个这个问题。。
考虑我们把序列分成L块。。
考虑各种复杂度：
为了支持询问我们得给每个块维护一个排过序的数列。。
给一个块部分增加值：
找出那部分，增加，归并，O(L)
给一个块整体增加值：
直接维护一个标记 O(1)
一个块的询问 O(LogL)<O(LogN)(为了方便看成LogN)
所有块的一次询问 (N/L)*LogL< (NLogN)/L
所有块的查询K大 LogN*(NLogN)/L=(NLogN^2)/L
修改一个区间 O(L+N/L) 假设L>N/L。。则为O(L)
我们在dfs的过程中。。
要进行O（N）次询问，O(N)次修改操作。。
所以让这两个操作平衡起来。。
既L=(NLogN^2)/L
解得L=Sqrt(N)LogN
总共就是N*Sqrt(N)LogN了。。
比第一个要好写一点。。速度也差不多。。

4
6
4
7
5
6

6 3
1 2 2
1 3 4
1 4 3
3 5 1
3 6 2

熬夜参加。。。
压力很大。。。
第一题有点压力。。写的时候比较小心。。所以就写慢了。。
然后还犯了个SB错误。。看了半天T_T。。
第二题直接裸map了。。写的还挺快囧。。
第三题想到算法但是现场写凸包压力很大就上网找模板。。
。。。最后还是fst了。。
最后Rank 60多。。真囧。。

网络游戏

Time Limit:40000MS  Memory Limit:65536K
Total Submit:11 Accepted:3
Case Time Limit:3000MS

Description

TT是个富甲一方的大富豪。作为一个富有激情和创造力的新时代青年，他早做腻了一般的买卖，决定顺应时代潮流，开一家网络公司。由于他从小就热爱网络游 戏，所以TT决定把网络游戏作为他的第一个经营项目。
由于TT的制作团队相当强大，所以TT很快就开发出了一个绝对能盖过暴雪出的一堆游戏的的超牛B网络游戏，一夜之间风靡全球，TT也再次发了一笔 财。当然TT对钱并不感兴趣，他更感兴趣的是游戏本身。
TT的网络游戏会根据玩家的各方面给玩家一个实力积分。TT最喜欢的做的事情是选出一些有代表性的玩家，然后按一种特别的顺序排成一个序列，然后 调查连续的一段中积分不超过V的玩家有多少个，以得知这一片玩家是否实力太弱。当然这个序列是会经常改变的，TT经常会把看不顺眼的玩家T掉、在中间加入 一个玩家。并且，玩家的积分也是经常会变的。
刚开始的时候，由于TT选的人不多，这个序列用他的开发团队写的一个简单程序还可以勉强维护。但人一多起来，TT就有些觉得不爽了，所以他决定请 你给他写个牛B的程序来解决这个问题。

Input

输入文件的第一行包含两个整数n和Q，n代表一开始TT所选玩家个数，Q表示TT的操作数。
接下来一行包含n个整数，表示一开始TT选的各个玩家的积分。
接下来的Q行，每行第一个整数o表示本次的操作类型：
若o=0,则接下来三个整数a，b，c表示TT询问第a个人到第b个人之间积分不超过c的有多少个。
若o=1，则接下来两个整数p，v表示TT在第p个人后面插入了一个积分为v的玩家。若p=0，则表示将该玩家插在序列开头。
若o=2，则接下来一个整数p表示TT将第p个人从序列中删除。
若o=3，则接下来两个整数p，v表示TT将第p个玩家的积分更新为v。

Output

对于每个o=0的操作，输出一行包含一个整数，表示该问题的答案。

Sample Input

5 8
10 2 6 1 5
1 1 7
3 5 5
2 5
0 3 5 8
1 2 7
0 2 5 10
0 3 6 2
2 3

Sample Output

3
4
1

Hint

对于20%的数据 n < =10000，Q < =10000
对于100%的数据 n < =100000，Q < =100000，所有输入整数在maxlongint以内。

Source

2008湖南省队集训By刘鹰
嘿嘿。。让我来给出一个(N+Q)LogN+QLogN^2的算法。。。
首先用Splay或者神马平衡树把最终的序列求出来的。。
然后把还没有插入的数看成maxlongint。。不影响结果。。
然后用线段数套平衡树硬搞就可以了。。。
擦～～写了10KB。。怎么一点都不给力啊。。。还没块状链块。。。