COJ 0359 xjrあなたのデータ構造(ルート番号2)の線分の木の区間を試験して増加します

xjrはあなたのデータ構造を試験します(ルート番号2)
難易度レベル:C;運転時間制限:3000 ms;運行スペース制限:51200 KB;コード長制限:200000 B
試験問題の説明
データ構造を作成して、次の機能を完了してください.
1)L個目からR個目までの最大、最小値および連続和を求める.
2)addLからaddRの個数をvだけ増やす.
 
入力
1行目:n、数を表す個数
2行目:各数Aiをスペースで区切る
3行目:Q、操作数を表す
後Q行:まずアルファベットを入力し、
アルファベットが「Q」の場合、後ろに2つの数が付いて、それぞれLとRです.
アルファベットが「A」の場合、後ろにaddL、addR、vの3つの数が続く.
しゅつりょく
各クエリー(Q)操作ごとに最大値、最小値、および連続和を順番に出力する複数のロー.各ローは、次のフォーマット(行の最後にスペースがありません)に従います.
MaxNum:整数、MinNum:整数、Sum:整数
入力例
51 2 3 4 53Q 1 4A 3 3 2Q 1 5
出力例
MaxNum: 4, MinNum: 1, Sum: 10MaxNum: 5, MinNum: 1, Sum: 17
その他の説明
0 < n, q < 100001
0 < Ai < 2001
0 < L, R < n + 1
标题:ははははははははははははははははははははははははははははははははははははははははははははははははははははははははははははは

  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('
')
  9 #define CH for(int d=0;d<=1;d++) if(ch[d])
 10 using namespace std;
 11 const int maxn=100000+10,maxnode=200000+10,inf=-1u>>1;
 12 struct node{
 13     node*ch[2];long long mi,mx,sm,add,siz;node(){mi=inf;mx=-inf;sm=add=0;}
 14     void sett(long long tag){mi=mx=sm=tag;return;}
 15     void addt(long long tag){add+=tag;mi+=tag;mx+=tag;sm+=tag*siz;return;}
 16     void down(){if(add){CH{ch[d]->addt(add);}add=0;}return;}
 17     void update(){
 18         mi=inf;mx=-inf;sm=0;
 19         CH{mi=min(mi,ch[d]->mi);mx=max(mx,ch[d]->mx);sm+=ch[d]->sm;}
 20         return;
 21     }
 22 }seg[maxnode],*nodecnt=seg,*root;
 23 int A[maxn],ql,qr,cv;
 24 void build(node*&x,int L,int R){
 25     x=nodecnt++;
 26     if(L==R) x->sett(A[L]);
 27     else{
 28         int M=L+R>>1;
 29         build(x->ch[0],L,M);
 30         build(x->ch[1],M+1,R);
 31         x->update();
 32     } 
 33     x->siz=R-L+1;return;
 34 }
 35 void update(node*&x,int L,int R){
 36     if(ql<=L&&R<=qr) x->addt(cv);
 37     else{
 38         int M=L+R>>1;
 39         x->down();
 40         if(ql<=M) update(x->ch[0],L,M);
 41         if(qr>M) update(x->ch[1],M+1,R);
 42         x->update();
 43     }
 44     return;
 45 }
 46 long long _mi,_mx,_sm;
 47 void query(node*x,int L,int R){
 48     if(ql<=L&&R<=qr){
 49         _mi=min(_mi,x->mi);
 50         _mx=max(_mx,x->mx);
 51         _sm+=x->sm;
 52     }
 53     else{
 54         int M=L+R>>1;
 55         x->down();
 56         if(ql<=M) query(x->ch[0],L,M);
 57         if(qr>M) query(x->ch[1],M+1,R);
 58     } return;
 59 }
 60 inline int read(){
 61     int x=0,sig=1;char ch=getchar();
 62     while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();}
 63     while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
 64     return x*=sig;
 65 }
 66 inline void write(int x){
 67     if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
 68     int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
 69     for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
 70 }
 71 inline char readc(){
 72     char ch=getchar();
 73     while(!isalpha(ch)) ch=getchar();
 74     return ch;
 75 }
 76 int n,Q;
 77 void init(){
 78     n=read();
 79     for(int i=1;i<=n;i++) A[i]=read();
 80     build(root,1,n);
 81     return;
 82 }
 83 void work(){
 84     Q=read();char tp;
 85     while(Q--){
 86         tp=readc();ql=read();qr=read();
 87         if(ql>qr) swap(ql,qr);
 88         if(tp=='A'){
 89             cv=read();
 90             update(root,1,n);
 91         }
 92         else{
 93             _mi=inf;_mx=-inf;_sm=0;
 94             query(root,1,n);
 95             printf("MaxNum: %lld, MinNum: %lld, Sum: %lld
",_mx,_mi,_sm);
 96         }
 97     }
 98     return;
 99 }
100 void print(){
101     return;
102 }
103 int main(){init();work();print();return 0;}