【题意】
n个操作
每个操作可以是
add x 把x加进set里
del x 把x从set中删除
sum 令A[1..m]按递增序表示set中的函数。求Sum{A[i] | i%5==3}
【算法】
直接弄棵平衡树。每个结点维护下面几个域。 long long Sum[5] ，offset ，delta，key。
然后标记上下传就可以了，不错的平衡树练手题目。
尝试了一下struct封装好各种操作的Splay。。。感觉还挺舒服，但是写得爆长。。。
我感觉离散化以后线段树也可以搞。
或者直接建5棵平衡树。index变的时候就裂开然后再合并就好了。
【其它】
看了一下watashi飘逸的treap。
然后再看了一下最短的那个人。。。
修改用一个vector二分了个位置(lower_bound)，然后直接insert erase。
然后统计直接for (i=3;i 特么坑爹啊！！！！！yandex.algorithm的题这样被人水过啊。 又想起NOI2003文本编辑器pascal那个不能吐槽的move=_=…特么比正解什么的都跑得快…
【链接】http://www.codeforces.com/problemset/problem/69/C
【其它】
其实这题很水- -，但是我STL套得很泪流满面…
比如这样
cin >> S;
S.erase(S.size()-1);
Name=S;
getline(cin,S);
Del_dot(S);
stringstream sin(S);
int Num;
Tv.clear();
while (sin >> S >> Num)
Tv.push_back(make_pair(S,Num));
pf.push_back(make_pair(Name,Tv));
再比如这样
for (vector< pair < string, vector < pair 搞了80行，压力太大了。 ym watashi的ruby和叉姐的python- –
【题意】
给你R张红牌，B张黑牌。
全翻过去。你每次可以选择翻开一张牌或者结束游戏。
翻开一张红牌你可以的1块钱，黑牌掉1块钱。
问假设你绝顶聪明，你得到的钱数是数学期望是多少？
【算法】
本来觉得红牌多就继续取，黑牌多不取了就是最优策略。
然后有个样例 11 12，期望居然>1。这才猛然发现可以通过见好就收的策略使得期望>0，于是就囧了。
解法是F[i][j]表示剩下i张红牌，j张黑牌，你绝顶聪明时的期望。
那么你怎么才叫聪明呢- -，当然是翻了以后，你继续聪明，得分的数学期望>0，那么就跑去翻，这样才叫聪明啊…
于是F[0][0]=0
F[i][j]=F[i-1][j]+1 (j=0)
F[i][j]=0 (i=0)
F[i][j]= max( (F[i-1][j]+1)*(i/(i+j)) + (F[i][j-1])*(j/(i+j)) , 0 )
最后F[R][B]就是期望…
要用滚动数组优化一下。
【CODE】
【题意】
输入n，求在所有错位排列中，在最长循环节上点的数目(如果有多个最长循环节，那么这些上面的点都要算)的期望值。
每个错排都是等概率的。
【算法】
论文上的题…写出来加深印象+方便回看。
因为是排列，而且是错排，所以可以看成无自环的多个独立环拼成的图。
F[i][j][k]表示选了i个数里面最长循环节是j，有k个最长循环节时的方案数。
令G[i][j]=Sum(F[i][0..j][k])
初始化F[0][0][0]=1。
F[i][j][k]=
{
G[i-j][j-1]*P(n-i+j,j)/j k=1 就是在剩下的n-i+j个数里取j个，得到一个长度为j的排列,但是由于是环,可以循环一圈当同样的，所以/j
F[i-j][j][k-1]*P(n-i+j,j)/j/k k>1 前面和上面一样.后面的/k是把这k个等长的环的顺序上的重复干掉。
}
最后答案就是Sum( F[n][j][k]*j*k ) / d
d是错排数目。
【CODE】
很靠前的一道题，到今天才做，主要是突然发现他是一道很纯的数学题，，，拿到题后看了下，并没有怎么弄第三个式子，没管，自己化。要想减少循环的次数，必须把每次计算的级数提高，y(x) – y(1) 这个是重点，推式子就是从这里开始的，推到后来就自然地要用到第三个式子了，那些符号不知道怎么打，不过发现在网上有人已经写了，就是这样的方法，摘录如下：
假设n是要达到精度要求的要计算到的数:
到这里就差不多了，e*中我觉得只要考虑后面部分就可以了，在大于n时是小于1/(3*n^3)的，在n达到4次方的数量级时，误差就小于10^-12了，所以计算的次数就在10000以内了，开始的时候为了保险，开了100000，6秒多过了，后来一步步往下降，到8000也可以，0.5秒多，5000就不行，中间就没试了，没意思的，反正是达不到一大片人的0.00s，0.01s了，郁闷～～～～～
code：
#include "stdio.h"
int main()
{
double sum,x,k;
int i;
x=0.000;
for (i=0;i<=2000;i++)
{
sum=0.0;
for (k=1;k<8000;k++)
sum+=1/(k*(k+1)*(k+2)*(k+x));
sum=((2-x)*sum+0.25)*(1-x)+1;
printf("%5.3f %16.12fn",x,sum);
x+=0.001;
}
return 0;
}