指针版线段树

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<cstring>
  7 #define PAU putchar(‘ ‘)
  8 #define ENT putchar(‘\n‘)
  9 #define CH for(int d=0;d<=1;d++) if(ch[d])
 10 using namespace std;
 11 const int maxn=1000000+10,maxnode=1080000+10,inf=-1u>>1;
 12 struct node{
 13     node*ch[2];int mi,mx,sm;
 14     void sett(int tag){mi=mx=sm=tag;return;}
 15     void update(){
 16         mi=inf;mx=-inf;sm=0;
 17         CH{mi=min(mi,ch[d]->mi);mx=max(mx,ch[d]->mx);sm+=ch[d]->sm;}
 18         return;
 19     }
 20 }seg[maxnode],*root,*nodecnt=seg;
 21 int A[maxn],n,Q;
 22 void build(node*&x,int L,int R){
 23     x=nodecnt++;
 24     if(L==R) x->sett(A[L]);
 25     else{
 26         int M=L+R>>1;
 27         build(x->ch[0],L,M);
 28         build(x->ch[1],M+1,R);
 29         x->update();
 30     } return;
 31 }
 32 int _mi,_mx,_sm,pos,cv,ql,qr;
 33 void query(node*x,int L,int R){
 34     if(ql<=L&&R<=qr){
 35         _mi=min(_mi,x->mi);
 36         _mx=max(_mx,x->mx);
 37         _sm+=x->sm;
 38     }
 39     else{
 40         int M=L+R>>1;
 41         if(ql<=M) query(x->ch[0],L,M);
 42         if(qr>M) query(x->ch[1],M+1,R);
 43     }
 44 }
 45 void update(node*&x,int L,int R){
 46     if(L==R) x->sett(cv);
 47     else{
 48         int M=L+R>>1;
 49         if(pos<=M) update(x->ch[0],L,M);
 50         else update(x->ch[1],M+1,R);
 51         x->update();
 52     }
 53 }
 54 inline int read(){
 55     int x=0,sig=1;char ch=getchar();
 56     while(!isdigit(ch)){if(ch==‘-‘)sig=-1;ch=getchar();}
 57     while(isdigit(ch))x=10*x+ch-‘0‘,ch=getchar();
 58     return x*=sig;
 59 }
 60 inline void write(int x){
 61     if(x==0){putchar(‘0‘);return;}if(x<0)putchar(‘-‘),x=-x;
 62     int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
 63     for(int i=len-1;i>=0;i--)putchar(buf[i]+‘0‘);return;
 64 }
 65 inline char readc(){
 66     char x=getchar();
 67     while(!isalpha(x)) x=getchar();
 68     return x;
 69 }
 70 void init(){
 71     n=read();
 72     for(int i=1;i<=n;i++) A[i]=read();
 73     build(root,1,n);
 74     return;
 75 }
 76 void work(){
 77     Q=read();char tp;
 78     while(Q--){
 79         tp=readc();ql=read();qr=read();
 80         if(tp==‘Q‘){
 81             _sm=0;_mx=-inf;_mi=inf;
 82             query(root,1,n);
 83             putchar(‘M‘);
 84             putchar(‘a‘);
 85             putchar(‘x‘);
 86             putchar(‘N‘);
 87             putchar(‘u‘);
 88             putchar(‘m‘);
 89             putchar(‘:‘);
 90             putchar(‘ ‘);
 91             write(_mx);
 92             putchar(‘,‘);
 93             putchar(‘ ‘);
 94             putchar(‘M‘);
 95             putchar(‘i‘);
 96             putchar(‘n‘);
 97             putchar(‘N‘);
 98             putchar(‘u‘);
 99             putchar(‘m‘);
100             putchar(‘:‘);
101             putchar(‘ ‘);
102             write(_mi);
103             putchar(‘,‘);
104             putchar(‘ ‘);
105             putchar(‘S‘);
106             putchar(‘u‘);
107             putchar(‘m‘);
108             putchar(‘:‘);
109             putchar(‘ ‘);
110             write(_sm);
111             ENT;
112         }
113         else{
114             pos=ql;cv=qr;
115             update(root,1,n);
116         }
117     }
118     return;
119 }
120 void print(){
121     return;
122 }
123 int main(){init();work();print();return 0;}