2018南京网络赛 g. lpl and energy-凯发ag旗舰厅登录网址下载

线段树非递归实现。点修改下的区间查询。

注意预处理的时候要把一到十万的都进行处理一遍，因为输入的月份不一定在月份的个数之内。

 

#include
#include
using namespace std;
const int inf=1e5 7;
const int themax=2e9 10;
int arr[4*inf],moth[inf],arr1[inf];
int ans[inf][2];        //初始化的时候都是零。 
int n,nn,n,k;               //确定n的值。
int now=0; 

void creatsegment()       //n是啥呢。                  
{
    n=1; while(n     for( int i=1;i<=n;i )
        arr[i n]=arr1[i];            //最大的数到了,n n，这应该是下一层的开始的那个数。 
    arr[n]=themax;
    nn=n<<1;
    for(int i=n n 1;i<=nn;i )        
        arr[i]=themax;                //这样进行的初始化。  
    for(int i=n-1;i>0;i--)            //但是这里应该是    
        arr[i]=arr[i<<1] < arr[i<<1|1]?arr[i<<1]:arr[i<<1|1];   //应该是这样的。 
}
int query()            //如何进行限定 。            
{
    int i=1;
    while( i     {
        if( arr[i<<1 ]<= now )   //通过顺序来操作罢了。zh            
        {
            i=i<<1;        
        }
        else
        {
            i=i<<1|1;
        }
    }             //说明下标是arr数组的下标。
    return i;
} 
void alter(int i)    //i应该是下标。 修改。 
{
    while(i!=1)
    {
        i=i>>1;        
        arr[i]=arr[i<<1]     }
}

int main()
{
    while(~scanf("%d %d",&n,&k))
    {
        memset(ans,0,sizeof(ans));
        now=0;
        for(int i=1;i<=n;i )
            scanf("%d",&arr1[i]);  //对arr建立线段树。 
        creatsegment();            //创建完成之后就是所谓的点修改了。 
        int mothnum;
        scanf("%d",&mothnum);    
        for(int i=1;i<=100000;i )  //就是这里的原因啊， 
        {
            if(ans[i-1][0]==n)       //这里看一下吧。 
            {
                ans[i][0]=ans[i-1][0];
                ans[i][1]=ans[i-1][1];
                continue;
            }
            now=now k;                //线段树创建完成之后。    
            if(now             {
                ans[i][0]=ans[i-1][0];     
                ans[i][1]=now;
            }
            else                    //这里是重点。点修改下的区间查询。 
            {
                int w=-1;            //从这里开始。 
                x:
                w ; 
                int flag=query();            //                                                                                
                // 之后就是进行判断是在左边还是在右边了。如果是偶数的话，
                now=now-arr[flag];
                if(w==0)           
                    ans[i][0]=ans[i-1][0] 1;
                else
                    ans[i][0]=ans[i][0] 1;
                ans[i][1]=now;                //进行更新。
                arr[flag]=themax;                          
                alter(flag);    
                 if( now>=arr[1] )                
                     goto x;                    //最后一点就是没有的时候如何退出吧。    
            }     
        }    
        for(int i=1;i<=mothnum;i )
        {
            int abc;
            scanf("%d",&abc);
            printf("%d %d\n",ans[abc][0],ans[abc][1]);        
        }        
    }
    return 0;
}

总结

以上是凯发ag旗舰厅登录网址下载为你收集整理的2018南京网络赛 g. lpl and energy-saving lamps （线段树非递归实现）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发ag旗舰厅登录网址下载网站内容还不错，欢迎将凯发ag旗舰厅登录网址下载推荐给好友。