学步园

晚上发现NOI不给用优先级队列，就自己写个堆，还行，速度

#include <cstdio>
const int N = (500000 + 1234) * 2;

struct heap_node
{
    int value, l, r, minv, loc;
    heap_node(int v1,int l1,int r1,int minv1, int loc1)
    {
        value = v1;
        l = l1;
        r = r1;
        minv = minv1;
        loc = loc1;
    }
    heap_node() {}
};


void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

int max(int a, int b)
{
    if(a > b)  return a;
    return b;
}

//int mark;
class Heap
{
public:
    int size;
    int heap[N];
    int l[N], r[N], minv[N], loc[N];
    void init()
    {
        size=0;
        heap[0]=1<<30;
    }
    void adjust(int i)
    {
        int j;
        if (heap[i]>heap[i>>1])
        {
            for ( ; heap[i]>heap[i>>1]; i=j)
            {
                j=i>>1;
                //if(j == 0)  break;
                swap(heap[i], heap[j]);
                swap(l[i], l[j]);
                swap(r[i], r[j]);
                swap(minv[i], minv[j]);
                swap(loc[i], loc[j]);
            }
            //mark = i;
        }
        else
        {
            for (j=i; ; i=j)
            {
                if ((i<<1)<=size && heap[j]<heap[i<<1] )
                    j=i<<1;
                if ( (i<<1)+1<=size && heap[j]<heap[(i<<1)+1] )
                    j=(i<<1)+1;
                if (j==i) break;
                swap(heap[i], heap[j]);
                swap(l[i], l[j]);
                swap(r[i], r[j]);
                swap(minv[i], minv[j]);
                swap(loc[i], loc[j]);
            }
            //mark = i;
        }
    }
    void push(heap_node c)
    {
        ++size;
        heap[size]=c.value;
        l[size] = c.l;
        r[size] = c.r;
        minv[size] = c.minv;
        loc[size] = c.loc;
        adjust(size);
    }
    heap_node pop()
    {
        swap(heap[1], heap[size]);
        swap(l[1], l[size]);
        swap(r[1], r[size]);
        swap(minv[1], minv[size]);
        swap(loc[1], loc[size]);
        if (--size) adjust(1);
        heap_node t(heap[size+1], l[size+1], r[size+1], minv[size+1], loc[size+1]);
        return t;
    }
} hp;

int st[19][500001];//RMQ是用的数组
int s[500001], log[500001];

int Query_RMQ(int a, int b)
{
    int loc = log[b-a+1];//2的多少次方
    if (s[st[loc][a]] < s[st[loc][b-(1<<loc)+1]])
        return st[loc][a];
    else
        return st[loc][b-(1<<loc)+1];
}

int main()
{
   // freopen("piano5.in","r",stdin);
    int n, k, L, R, i, j, x, minv, t1, t2;
    long long ans;
    heap_node tmp;

    scanf("%d%d%d%d", &n, &k, &L, &R);
    for (s[0] = 0, i = 1; i <= n; i ++) //前缀和
        scanf("%d", &x), s[i] = s[i-1] + x;

    for (log[1] = 0, i = 2; i <= n; i ++)
        log[i] = log[i-1] + ((i & -i) == i);

    for (i = 1; i <= n; i ++) st[0][i] = i - 1;
    for (i = 1; 1 << i <= n; i ++)
        for (j = 1; j + (1 << i) - 1 <= n; j ++)
            if (s[st[i-1][j]] < s[st[i-1][j+(1<<i-1)]])
                st[i][j] = st[i-1][j];
            else
                st[i][j] = st[i-1][j+(1<<i-1)];

    hp.init();
    for (i = L; i <= n; i ++)
    {
        t1 = max(1, i - R + 1), t2 = i - L + 1;//找到左端点所在的区间
        minv = Query_RMQ(t1, t2);
        heap_node t(s[i] - s[minv], t1, t2, minv + 1, i);
        //和，左端点所在的区间两个端点,最小值所在的序号，右端点
        hp.push(t);
        //if(i==351288) printf("mark=%d\n",mark);
    }

    for (ans = 0, i = 1; i <= k; i ++)
    {
        tmp = hp.pop();
        ans += tmp.value;
        if (tmp.l < tmp.minv)
        {
            t1 = tmp.l, t2 = tmp.minv - 1;
            minv = Query_RMQ(t1, t2);
            heap_node t(s[tmp.loc] - s[minv], t1, t2, minv + 1, tmp.loc);
            hp.push(t);
        }
        if (tmp.minv < tmp.r)
        {
            t1 = tmp.minv + 1, t2 = tmp.r;
            minv = Query_RMQ(t1, t2);
            heap_node t(s[tmp.loc] - s[minv], t1, t2, minv + 1, tmp.loc);
            hp.push(t);
        }
    }

    printf("%I64d\n", ans);
    return 0;
}