hdu 3415 Max Sum of Max-K-sub-sequence

#include <cstdio>
#include <cstring>
const int MAXN = 100000 + 123;
struct node
{
    int id, val;
    node(int x, int y): id(x), val(y) {}
    node() {}
} q[MAXN * 2];
int a[MAXN * 2];
int main()
{
    int T;
    int n, k;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++)  scanf("%d", &a[i]);

        int rmax = -2000, begin = -1, end = -1;
        for(int i = 1; i <= n; i++)
        {
            if(a[i] > rmax)
            {
                rmax = a[i];
                begin = end = i;
            }
        }

        for(int i = n + 1; i < n + k; i++)  a[i] = a[i - n];
        for(int i = 2; i < n + k; i++)  a[i] = a[i] + a[i - 1];//变成线性序列

        //用单调队列进行
        //先处理前k个

        int head = 0, tail = -1;
        int cnt = 0;
        node tnow(++cnt, a[1]);
        q[++tail] = tnow;

        for(int i = 2; i <= k; i++)
        {
            //while(tail > head) head++;
            int val = q[head].val;
            if(a[i] - val > rmax)
            {
                rmax = a[i] - val;
                begin = q[head].id + 1;
                end = i;
            }

            if(a[i] > rmax)
            {
                rmax = a[i];
                begin = 1;
                end = i;
            }

            //插入
            while(tail >= head && q[tail].val >= a[i]) tail--;
            node now(++cnt, a[i]);
            q[++tail] = now;
        }

        int leave = 0;
        for(int i = k + 1; i < n + k; i++)
        {
            while(tail > head && q[head].id <= leave) head++;
            int val = q[head].val;
            if(a[i] - val > rmax)
            {
                rmax = a[i] - val;
                begin = q[head].id + 1;
                end = i;
            }

            //插入
            while(tail >= head && q[tail].val >= a[i]) tail--;
            node now(++cnt, a[i]);
            q[++tail] = now;
            leave++;
        }

        if(begin > n) begin -= n;
        if(end > n) end -= n;
        printf("%d %d %d\n",rmax, begin, end);
    }
    return 0;
}