uva 1451 - Average 数形结合

     数形结合那篇论文的例题，维护一个下凸队列，一开始为了省事，用了栈，但是原理上有问题，因为有可能正好起点为上凸点的情况，WA了好多次……

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int org[100005],l,r;
struct node
{
    int v,ind;
    node(int a,int b)
    {
        v=a;
        ind=b;
    }
    node(){}
};
node q[100005];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,L;
        scanf("%d%d",&n,&L);
        while(getchar()!='\n');
        int i;
        int now=0;
        int aa=0,ab=0;
        for(i=1;i<=n;i++)
        {
            if(getchar()=='1')now++;
            org[i]=now;
        }
        r=0;
        q[r++]=node(0,-1);
        q[r++]=node(0,0);
        l=1;
        int ta=-1,tb=0;
        for(int k=L;k<=n;k++)
        {
            i=k-L;
            while(l<r-1&&(((org[i]-q[r-2].v)*(i-q[r-1].ind))-(org[i]-q[r-1].v)*(i-q[r-2].ind))>=0)
               r--;
            q[r++]=node(org[i],i);
            while(l<r-1&&(((org[k]-q[l+1].v)*(k-q[l].ind))-(org[k]-q[l].v)*(k-q[l+1].ind))>=0)
               l++;
            if(((org[k]-q[l].v)*tb-ta*(k-q[l].ind))>0||(((org[k]-q[l].v)*tb-ta*(k-q[l].ind))==0&&(k-q[l].ind)<(ab-aa+1)))
            {
                aa=q[l].ind+1;
                ab=k;
                ta=(org[k]-q[l].v);
                tb=(k-q[l].ind);
            }
        }
        printf("%d %d\n",aa,ab);
    }
}