POJ-3468-A Simple Problem with Integers(区间更新，求和)-splay或线段树-白红宇

POJ-3468-A Simple Problem with Integers(区间更新，求和)-splay或线段树

阅读量：5132 次

发布时间：2019-06-13

本文共 3984 字，大约阅读时间需要 13 分钟。

区间更新求和

主要用来练习splay树区间更新问题

//splay树的题解

// File Name: 3468-splay.cpp// Author: Zlbing// Created Time: 2013年08月09日 星期五 16时30分32秒#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define CL(x,v); memset(x,v,sizeof(x));#define INF 0x3f3f3f3f#define LL long long#define REP(i,r,n) for(int i=r;i<=n;i++)#define RREP(i,n,r) for(int i=n;i>=r;i--)#define L ch[x][0]#define R ch[x][1]#define KT (ch[ch[rt][1]][0])const int MAXN=2e5+100;struct SplayTree{ int ch[MAXN][2]; int pre[MAXN],sz[MAXN],val[MAXN]; int rt,top; void Rotate(int x,int f) { int y=pre[x]; down(y);down(x); ch[y][!f]=ch[x][f]; pre[ch[x][f]]=y; pre[x]=pre[y]; if(pre[x]) ch[pre[y]][ch[pre[y]][1]==y]=x; ch[x][f]=y; pre[y]=x; up(y); } void Splay(int x,int goal) { down(x); while(pre[x]!=goal) { down(pre[pre[x]]); down(pre[x]); down(x); if(pre[pre[x]]==goal) Rotate(x,ch[pre[x]][0]==x); else { int y=pre[x],z=pre[y]; int f=(ch[z][0]==y); if(ch[y][f]==x) Rotate(x,!f),Rotate(x,f); else Rotate(y,f),Rotate(x,f); } } up(x); if(goal==0)rt=x; } void RTO(int k,int goal) { int x=rt; down(x); while(sz[L]+1!=k) { if(k
                 
                  r)return; int m=(l+r)>>1; Newnode(x,num[m],f); build(L,l,m-1,x); build(R,m+1,r,x); up(x); } void init(int n) { ch[0][0]=ch[0][1]=pre[0]=0; sz[0]=rt=top=0; add[0]=sum[0]=0; Newnode(rt,-1,0); Newnode(ch[rt][1],-1,rt); sz[rt]=2; for(int i=1;i<=n;i++) scanf("%d",&num[i]); build(KT,1,n,ch[rt][1]); up(ch[rt][1]);up(rt); } void update() { int l,r,c; scanf("%d%d%d",&l,&r,&c); RTO(l,0); RTO(r+2,rt); add[KT]+=c; val[KT]+=c; sum[KT]+=(LL)c*sz[KT]; } void query() { int l,r; scanf("%d%d",&l,&r); RTO(l,0); RTO(r+2,rt); printf("%lld\n",sum[KT]); } LL sum[MAXN]; int add[MAXN]; int num[MAXN];}spt;int main(){ int m,n; char op[5]; while(~scanf("%d%d",&n,&m)) { spt.init(n); while(m--) { scanf("%s",op); if(op[0]=='Q')spt.query(); else spt.update(); } } return 0;}

线段树的题解

// File Name: /home/neuacm/ACM/POJ/3468.cpp// Author: Zlbing// Created Time: 2013年08月09日 星期五 14时35分11秒#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define CL(x,v); memset(x,v,sizeof(x));#define INF 0x3f3f3f3f#define LL long long#define REP(i,r,n) for(int i=r;i<=n;i++)#define RREP(i,n,r) for(int i=n;i>=r;i--)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int MAXN=1e5+100;LL col[MAXN<<2];LL sum[MAXN<<2];void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void pushdown(int rt,int l,int r){ if(col[rt]) { col[rt<<1]+=col[rt]; col[rt<<1|1]+=col[rt]; int m=(l+r)>>1; sum[rt<<1]+=(m-l+1)*col[rt]; sum[rt<<1|1]+=(r-m)*col[rt]; col[rt]=0; }}void build(int l,int r,int rt){ col[rt]=0; if(l==r) { //scanf("%I64d",&sum[rt]); cin>>sum[rt]; return ; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt);}LL query(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r) { return sum[rt]; } pushdown(rt,l,r); int m=(l+r)>>1; LL ret=0; if(L<=m)ret+=query(L,R,lson); if(R>m)ret+=query(L,R,rson); return ret;}void update(int L,int R,int p,int l,int r,int rt){ if(L<=l&&R>=r) { col[rt]+=p; sum[rt]+=(r-l+1)*p; return; } pushdown(rt,l,r); int m=(l+r)>>1; if(L<=m)update(L,R,p,lson); if(R>m)update(L,R,p,rson); pushup(rt);}void debug(int l,int r,int rt){ if(l==r) { printf("l==%d r==%d rt=%d sum[rt]=%lld col[rt]=%lld\n",l,r,rt,sum[rt],col[rt]); return ; } printf("l==%d r==%d rt=%d sum[rt]=%lld col[rt]=%lld\n",l,r,rt,sum[rt],col[rt]); int m=(l+r)>>1; debug(lson); debug(rson);}int main(){ int n,m; //std::ios::sync_with_stdio(false); while(~scanf("%d%d",&n,&m)) { build(1,n,1); char ch[5]; int a,b,c; REP(i,1,m) { scanf("%s",ch); if(ch[0]=='Q') { scanf("%d%d",&a,&b); LL ans=query(a,b,1,n,1); //debug(1,n,1); cout<
                 
                  <