坦克大战这道题真是做郁闷了，一道平衡树的题，我写了Splay、Treap、至顶向下伸展树、线段树但是都过不到，caesius还写了SBT他也没过，也不知道为什么，没办法vijos又不能给数据，这道题数据太大又不可能把它骗出来，或许是我们的RP还不够吧。 

在登陆的时候，很奇怪的出现了以下的画面，本以为是自己RP暴增，结果显示验证码输错，才明白过来是firefox的问题，居然打开的是原来的画面，让我白高兴一场。

不知道为什么，这道题过的人很少，但其实是一道很简单的题。
就是变了一点形LCS：求lcs的时候记录一下决策，做完后再返回来用一个数组记录B串中公共子串在A串中所对应的位置，再把字串中相邻字符中间的字符串插入A中既可。

关于LCS:  f[i,j]:= f[i-1,j-1]+1                   (a[i]=b[j])
                            max(f[i,j-1],f[i-1,j])       (a[i]<>b[j])
                                                               

nlogn，一道练动态树的不错题

vijos P1081
    
From Vivian Snow
野生动物园　     
    

    描述 Description     

    　　cjBBteam拥有一个很大的野生动物园。这个动物园坐落在一个狭长的山谷内，这个区域从南到北被划分成N个区域，每个区域都饲养着一头狮子。这些狮子从北到南编号为1,2,3,…,N。每头狮子都有一个觅食能力值Ai，Ai越小觅食能力越强。饲养员cmdButtons决定对狮子进行M次投喂，每次投喂都选择一个区间[I,J]，从中选取觅食能力值第K强的狮子进行投喂。值得注意的是，cmdButtons不愿意对某些区域进行过多的投喂，他认为这样有悖公平。因此cmdButtons的投喂区间是互不包含的。你的任务就是算出每次投喂后，食物被哪头狮子吃掉了。
    

    输入格式 Input Format     

    输入第一行有两个数N和M。此后一行有N个数，从南到北描述狮子的觅食能力值。此后M行，每行描述一次投喂。第t+2的三个数I,J,K表示在第t次投喂中，cmdButtons选择了区间[I,J]内觅食能力值第K强的狮子进行投喂。
    

    输出格式 Output Format     

    输出有M行，每行一个整数。第i行的整数表示在第i次投喂中吃到食物的狮子的觅食能力值。
    

    样例输入 Sample Input     

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

    样例输出 Sample Output     

    3 2

    时间限制 Time Limitation     

    各个测试点2s

    注释 Hint     

    对于100%的数据，有1<=N<=100000，1<=M<=50000。

    来源 Source     

    周戈林
        
    
关于数据结构的题，知道算法之后觉得的确经典。从N的数据范围就可以看出必须在log n的复杂度下完成，当然找第K大元素在log n的时间下完成很容易想到动态树，但是，它限定了区间的。这也许是这道题最科学的地方，“因此cmdButtons的投喂区间是互不包含的。你的任务就是算出每次投喂后，食物被哪头狮子吃掉了”，说明它所询问的所有区间都互不相包含，于是想到了现预处理所给出的区间，按开头顺序排序，这样，当你找了该区间之后只要通过前面删除一些数后面添加一些数就可以得到下一个区间（排好序的）。若用动态树，每个数删除和添加都是log n的，又因为每个数只可能添加一次，删除一次，（当然，m肯定是<=n的）所以总复杂度就变成了nlogn。

昨天到机房终于可以上网了，没办法，在重大那个办公室上不起网。无意间发现vijos进得去了，于是感慨vijos年过完了。突然想起那上面有一道最优匹配的题http://www.vijos.cn/Problem_Show.asp?id=1228，想练一练费用流（该题可以用KM，但那东西没怎么弄懂，反正用费用流也行），但是找了半天没找到这道题。后面才发现原来这道题之前是AC过了，但我是用贪心＋随机调整过的。