shadowice1984 的博客

shadowice1984 的博客

segment tree beats 练习题

posted on 2019-04-18 15:33:57 | under 未分类 |

数据结构白学了

补习一下吉司机线段树

这是一道简单的segmenttreebeats入门题

区间加

区间对一个数字取max

求一个数字的值是多少以及历史上改变了多少次值

维护区间最小值和区间次小值,打一个神奇的标记表示这个区间的最小值曾经改变过多少次

做区间取max操作按照吉司机线段树的方式进行剪枝

注意一下几点

保证次小值和最小值是不同的

打两个标记,一个是加法标记另一个是取max标记,新增标记的时候不要偷懒

为了避免各种各样的故障,每个点保存一下区间的最小值来自左孩子还是右孩子,这样第3个标记才能下传

#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;typedef long long ll;
const ll inf=(1LL<<60);const ll low_inf=(1LL<<50);
int n;int m;ll cur;//int TOT;
struct linetree
{
    struct data
    {
        ll val;int fr;
        friend bool operator <(data a,data b){return a.val<b.val;}
        void operator +=(ll del){val+=del;}
    }mi[N<<2];ll nmi[N<<2];
    int v[N<<2];int splb[N<<2];ll to_mi[N<<2];ll add[N<<2];
    inline void appadd(int p,ll del)
    {
        add[p]+=del;mi[p]+=del;nmi[p]+=del;to_mi[p]+=del;
    }
    inline void appmx(int p,ll lim)
    {
        mi[p].val=max(lim,mi[p].val);
        nmi[p]=max(nmi[p],lim);to_mi[p]=max(to_mi[p],lim);
    }
    inline void ins(int p,ll val)
    {
    //  if(val!=0&&val<low_inf)printf("ins  %lld %lld %lld\n",val,mi[p].val,nmi[p]);
        if(mi[p].val>=val)
        {
            if(mi[p].val!=val)nmi[p]=mi[p].val;
            mi[p].val=val;
        }
        else if(nmi[p]>=val)nmi[p]=val;
    }
    inline void ud(int p,int p1,int p2)
    {
        mi[p].val=mi[p1].val;nmi[p]=nmi[p1];

    //  ll qu[4]={mi[p1].val,nmi[p1],mi[p2].val,nmi[p2]
    //  mi[p].val=qu[0];nmi[p]=qu[1];
        ins(p,mi[p2].val);ins(p,nmi[p2]);
    //  if(nmi[p]<low_inf)printf("mi=%lld,nmi=%lld\n",mi[p].val,nmi[p]);
        if(mi[p].val==mi[p1].val&&mi[p].val==mi[p2].val)
            mi[p].fr=2;
        else if(mi[p].val==mi[p1].val)mi[p].fr=0;
        else mi[p].fr=1;
    }
    inline void pd(int p,int p1,int p2)
    {
        if(splb[p])
        {
            switch(mi[p].fr)
            {
                case 0:{splb[p1]+=splb[p];break;}
                case 1:{splb[p2]+=splb[p];break;}
                case 2:{splb[p1]+=splb[p];splb[p2]+=splb[p];break;}
            }splb[p]=0;
        }
        if(add[p])
            appadd(p1,add[p]),appadd(p2,add[p]),add[p]=0;
        if(to_mi[p]>-low_inf)
            appmx(p1,to_mi[p]),appmx(p2,to_mi[p]),to_mi[p]=-inf;
    }
    inline void stadd(int p,int l,int r,int dl,int dr,ll del)
    {
        if(l==dl&&r==dr){appadd(p,del);v[p]++;return;}
        int mid=(l+r)>>1;pd(p,p<<1,p<<1|1);
        if(dl<mid)stadd(p<<1,l,mid,dl,min(dr,mid),del);
        if(mid<dr)stadd(p<<1|1,mid,r,max(dl,mid),dr,del);
        ud(p,p<<1,p<<1|1);
    }
    inline void stmx(int p,int l,int r,int dl,int dr,ll lim)
    {
        if(l==dl&&dr==r)
        {

        //  if(nmi[p]==54421679)printf("%d %d,mi=%lld,nmi=%lld,lim=%lld\n",l,r,mi[p].val,nmi[p],lim);
            if(lim<=mi[p].val)return;

            if(lim<nmi[p]){splb[p]++;appmx(p,lim);return;}
            //printf("mi=%lld,nmi=%lld,lim=%lld\n",mi[p].val,nmi[p],lim);
            //TOT++;
        }
        int mid=(l+r)>>1;pd(p,p<<1,p<<1|1);
        if(dl<mid)stmx(p<<1,l,mid,dl,min(dr,mid),lim);
        if(mid<dr)stmx(p<<1|1,mid,r,max(dl,mid),dr,lim);
        ud(p,p<<1,p<<1|1);
    }
    inline int qry(int p,int l,int r,int pos)
    {
        if(r-l==1)
        {
        //  printf("%lld ",mi[p].val);
            cur=mi[p].val;
            return v[p]+splb[p];
        }
        int mid=(l+r)>>1;pd(p,p<<1,p<<1|1);
        if(pos<=mid)return v[p]+qry(p<<1,l,mid,pos);
        else return v[p]+qry(p<<1|1,mid,r,pos);
    }
    inline void build(int p,int l,int r,ll* a)
    {
        to_mi[p]=-inf;
        if(r-l==1)
        {
            mi[p].val=a[r];nmi[p]=low_inf;return;
        }
        int mid=(l+r)>>1;
        build(p<<1,l,mid,a);build(p<<1|1,mid,r,a);
        ud(p,p<<1,p<<1|1);
    }
}lt;
ll a[N];char mde[N];
ll ans1[N];int ans2[N];int CNT;
int main()
{
    //freopen("tst","r",stdin);freopen("my","w",stdout);
//  freopen("seq3.out","r",stdin);
//  ++CNT;
//  while(scanf("%lld%d",&ans1[CNT],&ans2[CNT])!=-1)++CNT;
//  fclose(stdin);CNT=1;
//  freopen("seq3.in","r",stdin);
//freopen("mtst.txt","w",stdout);
    freopen("seq.in","r",stdin);freopen("seq.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    lt.build(1,0,n,a);
    scanf("%d",&m);
    for(int i=1,l,r,del;i<=m;i++)
    {
        //if(i%1000==0)printf("i=%d,ratio=%.3lf\n",i,(double)TOT/i);
        scanf("%s",mde+1);
        switch(mde[1])
        {
            case 'A':
            {
                scanf("%d%d%d",&l,&r,&del);
                if(del!=0)lt.stadd(1,0,n,l-1,r,del);
        //      if(i>=5700)printf("Add\n");
                break;
            }
            case 'M':
            {
                scanf("%d%d%d",&l,&r,&del);
                lt.stmx(1,0,n,l-1,r,del);
            //  if(i>=5700)printf("stmx %d %d %d\n",l,r,del);
                break;
            }
            case 'Q':
            {
                scanf("%d",&l);
                int cur2=lt.qry(1,0,n,l);
                printf("%lld %d\n",cur,cur2);
            //  if(cur!=ans1[CNT]||cur2!=ans2[CNT])
            //  {
            //      printf("%lld %d %lld %d\n",cur,cur2,ans1[CNT],ans2[CNT]);
            //      printf("i=%d,m=%d,l=%d,a[l]=%d,Wrong Answer\n",i,m,l,a[l]);
            ////    
            //  return 0;}//int k;while(1)k++;}
            //  ++CNT;
                break;
            }

        }
    //  if(i>=5700)
    //  {
    //      int cur2=lt.qry(1,0,n,7216);
    //      printf("%lld %d\n",cur,cur2);
    //  }   
    }
    return 0;
}