线段树

    1. #include<bits/stdc++.h>
    2. #define ll long long
    3. #define dl double
    4. #define fo(i,a,b) for (int i=a;i<=b;i++)
    5. #define println(x){printf(":\n");for (int tmpi=1;tmpi<=n;tmpi++)printf("%d ",x[i]);printf("\n");}
    6. using namespace std;
    8. const int N=1e5+7;
    9. const int INF=0x3f3f3f3f;
    10. const int M=1e9+7;
    12. class poi{
    13. public:
    14.     ll l,r,sum,maxx,add,lc,rc;
    15. };
    17. class seg{
    18. public:
    19.     vector<poi> s;
    21.     void bulid(ll x){
    22.         if (s[x].lc) return;
    23.         ll l=s[x].l,r=s[x].r,mid=(l+r)>>1;
    24.         s.push_back((poi){l,mid,0,0,0,0,0});
    25.         s[x].lc=s.size()-1;
    26.         s.push_back((poi){mid+1,r,0,0,0,0,0});
    27.         s[x].rc=s.size()-1;
    28.     }
    30.     void pushdown(ll x){
    31.         bulid(x);
    32.         ll lc=s[x].lc,rc=s[x].rc;
    33.         s[lc].add+=s[x].add;
    34.         s[lc].sum+=s[x].add*(s[lc].r-s[lc].l+1);
    35.         s[rc].add+=s[x].add;
    36.         s[rc].sum+=s[x].add*(s[rc].r-s[rc].l+1);
    37.         updata(x);
    38.     }
    40.     void updata(ll x){
    41.         s[x].add=0;
    42.         s[x].sum=s[s[x].lc].sum+s[s[x].rc].sum;
    43.         s[x].maxx=max(s[s[x].lc].maxx,s[s[x].rc].maxx);
    44.     }
    46.     void add(ll x,ll l,ll r,ll t){
    47.         if (l<=s[x].l&&s[x].r<=r){
    48.             s[x].sum+=t*(s[x].r-s[x].l+1);
    49.             s[x].add+=t;
    50.             s[x].maxx+=t;
    51.             return;
    52.         }
    53.         else{
    54.             pushdown(x);
    55.             if (l<=s[s[x].lc].r){
    56.                 add(s[x].lc,l,r,t);
    57.             }
    58.             if (r>=s[s[x].rc].l){
    59.                 add(s[x].rc,l,r,t);
    60.             }
    61.             updata(x);
    62.         }
    63.     }
    65.     ll query_sum(ll x,ll l,ll r){
    66.         if (l<=s[x].l&&s[x].r<=r){
    67.             return s[x].sum; 
    68.         }
    69.         else{
    70.             pushdown(x);
    71.             ll tmp=0;
    72.             if (l<=s[s[x].lc].r){
    73.                 tmp+=query_sum(s[x].lc,l,r);
    74.             }
    75.             if (r>=s[s[x].rc].l){
    76.                     tmp+=query_sum(s[x].rc,l,r);
    77.             }
    78.             return tmp;
    79.         }
    80.     }
    82.     ll query_max(ll x,ll l,ll r){
    83.         if (l<=s[x].l&&s[x].r<=r){
    84.             return s[x].maxx; 
    85.         }
    86.         else{
    87.             pushdown(x);
    88.             ll tmp=0;
    89.             if (l<=s[s[x].lc].r){
    90.                 tmp=max(tmp,query_max(s[x].lc,l,r));
    91.             }
    92.             if (r>=s[s[x].rc].l){
    93.                 tmp=max(tmp,query_max(s[x].rc,l,r));
    94.             }
    95.             return tmp;
    96.         }
    97.     }
    99. }tree;
    101. int n;
    102. int m;
    103. ll l,r,t;
    104. ll a;
    106. void read(){
    107.     scanf("%d",&n);
    108.     tree.s.push_back((poi){1,n,0,0,0,0,0});
    109.     for (int i=1;i<=n;i++){
    110.         scanf("%lld",&a);
    111.         tree.add(0,i,i,a);
    112.     }
    113.     tree.add(0,1,2,4);
    114.     cout<<tree.query_max(0,1,4);
    116.     /*scanf("%d",&m);
    117.     char ch[5];
    118.     for (int i=1;i<=m;i++){
    119.         scanf("%s",ch);
    120.         if (ch[0]=='S'){
    121.             scanf("%lld%lld",&l,&r);
    122.             printf("%lld\n",tree.sum(0,l,r));
    123.         }
    124.         if (ch[0]=='A'){
    125.             scanf("%lld%lld%lld",&l,&r,&t);
    126.             tree.add(0,l,r,t);
    127.         }
    128.     }*/
    129. }
    131. int main(){
    132.     read();
    133.     return 0;
    134. }

    快读

    
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}