「NOIP2016」蚯蚓

题意：本题中，我们将用符号 $\lfloor c \rfloor$ 表示对 $c$ 向下取整，例如：$\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。

蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有 $n$ 只蚯蚓（$n$ 为正整数）。每只蚯蚓拥有长度，我们设第 $i$ 只蚯蚓的长度为 $a_i$ ($i=1,2,\dots,n$)，并保证所有的长度都是非负整数（即：可能存在长度为 $0$ 的蚯蚓）。

每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 $p$（是满足 $0 < p < 1$ 的有理数）决定，设这只蚯蚓长度为 $x$，神刀手会将其切成两只长度分别为 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$ 的蚯蚓。特殊地，如果这两个数的其中一个等于 $0$，则这个长度为 $0$ 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 $q$（是一个非负整常数）。

蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 $m$ 秒才能到来……（$m$ 为非负整数）

蛐蛐国王希望知道这 $m$ 秒内的战况。具体来说，他希望知道：

• $m$ 秒内，每一秒被切断的蚯蚓被切断前的长度（有 $m$ 个数）；
• $m$ 秒后，所有蚯蚓的长度（有 $n + m$ 个数）。

蛐蛐国王当然知道怎么做啦！但是他想考考你……

算法一 $(60\ pts)$：

考虑 $q=0$ 的情况，题意就相当于维护一个支持查询最值，删除最值，插入新值的集合，二叉堆即可完成，时间复杂度为 $O(m\ \log\ n)$。

算法二 $(35\ pts)$：

考虑 $q>0$ 的情况，除了最大值拆成的两个数，其他值都会增加 $q$。设最大值为 $x$ ，我们可以认为产生了两个大小为 $\lfloor px\rfloor-q$ 和 $x-\lfloor px\rfloor -q$ 的新数，然后再把整个集合加上 $q$。

于是我们就可以像线段树一样，打一个 $lazy$ 标记，维护一个变量 $delta$ ，集合中的数要加上它才是真实值，最初 $delta=0$。

对于每一秒：

1. 取出集合中最大值 $x$，$x=x+delta$。
2. 把 $\lfloor px\rfloor-q-delta$ 和 $x-\lfloor px\rfloor -q-delta$ 插入集合。
3. $delta=delta+q$。

重复 $m$ 轮，就可以得到最终答案，但是由于时间复杂度过高，依然不能拿到满分。

算法三 $(100\ pts)$：

因为 $p,q$ 是常数，我们设 $x_1,x_2$ 为非负整数，当 $x_1\geq x_2$ 时，有 $\lfloor px_1\rfloor+q=\lfloor px_1+q\rfloor\geq\lfloor px_2+pq\rfloor=\lfloor p(x_2+q)\rfloor$。

又因为 $x_1-x_2\geq p(x_1-x_2)$，所以 $x_1-px_1\geq x_2-px_2\geq x_2-p(x_2+q)$。

得到 $x_1-\lfloor px_1\rfloor+q=\lfloor x_1-px_1\rfloor+q\geq \lfloor x_2-p(x_2+q)\rfloor+q=x_2+q-\lfloor p(x_2+q)\rfloor$。

上面的意义是，若 $x_1$ 在 $x_2$ 之前被取出集合，则在一秒后，$x_1$ 分成的两个数 $\lfloor px_1\rfloor+q$ 和 $x_1-\lfloor px_1\rfloor+q$ 分别不小于 $x_2+q$ 分成的两个数 $\lfloor p(x_2+q)\rfloor$ 和 $x_2+q-\lfloor p(x_2+q)\rfloor$。即从集合中取出的数是单调递减的，新产生的两类数值也单调递减。

我们可以建立三个队列 $A,B,C$ ，共同维护集合，$A$ 队列保存初始 $n$ 个数，从大到小排序，$B$ 队列保存每秒产生的 $\lfloor px\rfloor$ 的数值，$C$ 队列保存每秒产生的 $x-\lfloor px\rfloor$ 的数值。起初 $B,C$ 队列为空，新产生的数从队尾插入，根据结论，$B,C$ 单调递减，因此每个时刻集合中最大的数就是队列 $A,B,C$ 的三个队头之一，再结合上 $delta$ ，整个算法时间复杂度为 $O(m+n\ \log\ n)$。

code：

#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
queue<long long> a;
queue<long long> b;
queue<long long> c;
bool cmp(long long a,long long b)
{
    return a>b;
}
long long n,m,q,u,v,t,x,y;
long long s[101010];
int main()
{
    scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);
    for(int i=1;i<=n;i++)
        scanf("%lld",&s[i]);
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++)
        a.push(s[i]);
    for(int i=1;i<=m;i++)
    {
        long long maxx=-1<<30;
        long long p;
        if(!a.empty())
            if(a.front()>maxx)
            {
                maxx=a.front();
                p=1;
            }
        if(!b.empty())
            if(b.front()>maxx)
            {
                maxx=b.front();
                p=2;
            }
        if(!c.empty())
            if(c.front()>maxx)
            {
                maxx=c.front();
                p=3;
            }
        if(p==1)
            a.pop();
        else if(p==2)
            b.pop();
        else if(p==3)
            c.pop();
        maxx+=(i-1)*q;
        x=maxx*u/v;
        y=maxx-x;
        if(!(i%t))
            printf("%lld ",maxx);
        b.push(x-i*q);
        c.push(y-i*q);
    }
    printf("\n");
    long long r=1;
    while(r)
    {
        long long maxx=-1<<30,p;
        if(a.empty()&&b.empty()&&c.empty())
            break;
        if(!a.empty())
            if(a.front()>maxx)
            {
                maxx=a.front();
                p=1;
            }
        if(!b.empty())
            if(b.front()>maxx)
            {
                maxx=b.front();
                p=2;
            }
        if(!c.empty())
            if(c.front()>maxx)
            {
                maxx=c.front();
                p=3;
            }
        if(p==1)
            a.pop();
        else if(p==2)
            b.pop();
        else if(p==3)
            c.pop();
        if(r%t==0)
            printf("%lld ",maxx+m*q);
        r++;
    }
    return 0;
}