coj--1532: JuQueen+线段树

很久没写线段树了，没想到这两场比赛都遇到了线段树的题目。看来是有必要重新复习一下了。。。。。
对于这道题的话其实就是线段树，我们只需要维护一下区间的最小值和最大值就可以应对题目的问题了。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define maxn 5000000
#define INF 0x3f3f3f3f

int a[maxn],_max,_min,lazy[maxn*4];
int minv[maxn*4],maxv[maxn*4];

void maintain(int o,int L,int R)
{
    int lc=2*o,rc=2*o+1;
    minv[o]=min(minv[lc],minv[rc]);
    maxv[o]=max(maxv[lc],maxv[rc]);
}

void pushdown(int o,int L,int R)
{
    int lc=2*o,rc=2*o+1,M=(R+L)/2;
    if(lazy[o]!=INF)
    {
        minv[lc]+=lazy[o];
        maxv[lc]+=lazy[o];
        minv[rc]+=lazy[o];
        maxv[rc]+=lazy[o];
        if(lazy[lc]==INF)
            lazy[lc]=lazy[o];
        else
            lazy[lc]+=lazy[o];
        if(lazy[rc]==INF)
            lazy[rc]=lazy[o];
        else
            lazy[rc]+=lazy[o];
        lazy[o]=INF;
    }
}

void update(int o,int L,int R,int ql,int qr,int v)
{
    int M=L+(R-L)/2;
    if(ql<=L&&qr>=R)
    {
        minv[o]+=v;
        maxv[o]+=v;
        if(lazy[o]==INF)
            lazy[o]=v;
        else
            lazy[o]+=v;
        return ;
    }
    pushdown(o,L,R);
    if(ql<=M)
        update(o*2,L,M,ql,qr,v);
    if(qr>M)
        update(o*2+1,M+1,R,ql,qr,v);
    maintain(o,L,R);
}

void query(int o,int L,int R,int ql,int qr)
{
    int M=L+(R-L)/2;
    if(ql<=L&&qr>=R)
    {
        _max=max(_max,maxv[o]);
        _min=min(_min,minv[o]);
        return ;
    }
    pushdown(o,L,R);
    if(ql<=M)
        query(o*2,L,M,ql,qr);
    if(qr>M)
        query(2*o+1,M+1,R,ql,qr);
}

void Init()
{
    _max=0; _min=INF;
}

int main()
{
    int n,top,Q;
    while(scanf("%d%d%d",&n,&top,&Q)!=EOF)
    {
         memset(lazy,0x3f,sizeof(lazy));
         memset(maxv,0,sizeof(maxv));
         memset(minv,0,sizeof(minv));
         while(Q--)
         {
             char str[100];
             int A,B,S;
             scanf("%s",str);
             if(str[0]==‘s‘)  ///state
             {
                 scanf("%d",&A);
                 A++;
                 Init();
                 query(1,1,n,A,A);
                 printf("%d\n",_min);
             }
             if(str[0]==‘g‘) ///group change
             {
                 scanf("%d%d%d",&A,&B,&S);
                 A++;B++;
                 Init();
                 query(1,1,n,A,B);
                 if(S<=0)
                 {
                    if(S+_min<0)
                    {
                        int t=_min*-1;
                        update(1,1,n,A,B,t);
                        printf("%d\n",t);
                    }
                    else
                    {
                        update(1,1,n,A,B,S);
                        printf("%d\n",S);
                    }
                 }
                 else
                 {
                     if(_max+S>top)
                     {
                         int t=top-_max;
                         update(1,1,n,A,B,t);
                         printf("%d\n",t);
                     }
                     else
                     {
                         update(1,1,n,A,B,S);
                         printf("%d\n",S);
                     }
                 }
             }
             if(str[0]==‘c‘)  ///change
             {
                 scanf("%d%d",&A,&S);
                 A++;
                 Init();
                 query(1,1,n,A,A);
                 if(S<=0)
                 {
                     if(S+_min<0)
                     {
                         int t=-1*_min;
                         update(1,1,n,A,A,t);
                         printf("%d\n",t);
                     }
                     else
                     {
                         update(1,1,n,A,A,S);
                         printf("%d\n",S);
                     }
                 }
                 else
                 {
                     if(S+_max>top)
                     {
                         int t=top-_max;
                         update(1,1,n,A,A,t);
                         printf("%d\n",t);
                     }
                     else
                     {
                         update(1,1,n,A,A,S);
                         printf("%d\n",S);
                     }
                 }
             }
         }
    }
 return 0;
}