1 #include <cstdio>  2 const int sizeOfNumber=50005;  3 const int sizeOfSeg=200002;  4   5 inline int max(int, int);  6 inline int getint();  7 inline void putint(int);  8   9 struct node 10 { 11     int lmax, rmax, smax, ssum; 12     inline node(int=0); 13 }; 14 inline node merge(node, node); 15  16 struct seg 17 { 18     node data; 19     seg * l, * r; 20     inline void maintain(); 21 }; 22 seg memory[sizeOfSeg], * port=memory; 23 inline seg * newseg(); 24 seg * build(int, int); 25 node query(seg * , int, int, int, int); 26  27 int n, m; 28 int a[sizeOfNumber]; 29 seg * t; 30  31 int main() 32 { 33     n=getint(); 34     for (int i=1;i<=n;i++) 35         a[i]=getint(); 36     t=build(1, n); 37  38     m=getint(); 39     for (int i=1;i<=m;i++) 40     { 41         int x=getint(), y=getint(); 42         putint(query(t, 1, n, x, y).smax); 43     } 44  45     return 0; 46 } 47  48 inline int max(int x, int y) 49 { 50     return x>y?x:y; 51 } 52 inline int getint() 53 { 54     register int num=0; 55     register char ch=0, last; 56     do last=ch, ch=getchar(); while (ch<‘0‘ || ch>‘9‘); 57     do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘); 58     if (last==‘-‘) num=-num; 59     return num; 60 } 61 inline void putint(int num) 62 { 63     char stack[11]; 64     register int top=0; 65     if (num==0) stack[top=1]=‘0‘; 66     if (num<0) putchar(‘-‘), num=-num; 67     for ( ;num;num/=10) stack[++top]=num%10+‘0‘; 68     for ( ;top;top--) putchar(stack[top]); 69     putchar(‘\n‘); 70 } 71  72 inline node::node(int x) 73 { 74     lmax=rmax=smax=ssum=x; 75 } 76 inline node merge(node a, node b) 77 { 78     node c; 79     c.ssum=a.ssum+b.ssum; 80     c.lmax=max(a.lmax, a.ssum+b.lmax); 81     c.rmax=max(a.rmax+b.ssum, b.rmax); 82     c.smax=max(a.smax, b.smax); 83     c.smax=max(c.smax, a.rmax+b.lmax); 84     return c; 85 } 86  87 inline seg * newseg() 88 { 89     seg * ret=port++; 90     return ret; 91 } 92 inline void seg::maintain() 93 { 94     this->data=http://www.mamicode.com/merge(this->l->data, this->r->data); 95 } 96 inline seg * build(int l, int r) 97 { 98     seg * t=newseg(); 99     int m=(l+r)>>1;100 101     if (l==r)102         t->data=http://www.mamicode.com/node(a[m]);103     else104     {105         t->l=build(l, m);106         t->r=build(m+1, r);107         t->maintain();108     }109 110     return t;111 }112 node query(seg * t, int l, int r, int ql, int qr)113 {114     node ret;115     int m=(l+r)>>1;116 117     if (l==ql && r==qr) ret=t->data;118     else119     {120         if (qr<=m) ret=query(t->l, l, m, ql, qr);121         else if (ql>m) ret=query(t->r, m+1, r, ql, qr);122         else ret=merge(query(t->l, l, m, ql, m), query(t->r, m+1, r, m+1, qr));123     }124 125     return ret;126 }

  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 const int sizeOfNumber=100001;  5 const int sizeOfQuestion=100001;  6 const int sizeOfSeg=400004;  7   8 inline int max(int, int);  9 inline int getint(); 10 inline void putint(int); 11  12 struct seg 13 { 14     int ssum, lmax; 15     int flag, maxflag; 16     seg * l, * r; 17     inline void pushdown(); 18     inline void maintain(); 19 }; 20 seg memory[sizeOfSeg], * port=memory; 21 inline seg * newseg(); 22 seg * build(int, int); 23 void update(seg * , int, int, int, int, int); 24 int query(seg * , int, int, int, int); 25  26 int n, q; 27 int a[sizeOfNumber], p[sizeOfNumber]; 28 int d[sizeOfQuestion], l[sizeOfQuestion], r[sizeOfQuestion]; 29 int ans[sizeOfQuestion]; 30 seg * t; 31 inline bool cmpForQuestion(int, int); 32 inline bool cmpForDiscrete(int, int); 33 inline void prepare(); 34  35 int main() 36 { 37     n=getint(); 38     for (int i=1;i<=n;i++) 39         a[i]=getint(); 40     prepare(); 41     t=build(1, n); 42     q=getint(); 43     for (int i=1;i<=q;i++) 44         l[i]=getint(), r[i]=getint(); 45     for (int i=1;i<=q;i++) 46         d[i]=i; 47     std::sort(d+1, d+q+1, cmpForQuestion); 48  49     int j=1; 50     for (int i=1;i<=n;i++) 51     { 52         update(t, 1, n, p[i]+1, i, a[i]); 53         for ( ;j<=q && r[d[j]]==i;j++) 54             ans[d[j]]=query(t, 1, n, l[d[j]], r[d[j]]); 55     } 56  57     for (int i=1;i<=q;i++) 58         putint(ans[i]); 59  60     return 0; 61 } 62  63 inline int max(int x, int y) 64 { 65     return x>y?x:y; 66 } 67 inline int getint() 68 { 69     register int num=0; 70     register char ch=0, last; 71     do last=ch, ch=getchar(); while (ch<‘0‘ || ch>‘9‘); 72     do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘); 73     if (last==‘-‘) num=-num; 74     return num; 75 } 76 inline void putint(int num) 77 { 78     char stack[11]; 79     register int top=0; 80     if (num==0) stack[top=1]=‘0‘; 81     if (num<0) putchar(‘-‘), num=-num; 82     for ( ;num;num/=10) stack[++top]=num%10+‘0‘; 83     for ( ;top;top--) putchar(stack[top]); 84     putchar(‘\n‘); 85 } 86  87 inline void seg::pushdown() 88 { 89     this->l->maxflag=max(this->l->maxflag, this->l->flag+this->maxflag); 90     this->r->maxflag=max(this->r->maxflag, this->r->flag+this->maxflag); 91     this->l->flag+=this->flag; 92     this->r->flag+=this->flag; 93     this->l->lmax=max(this->l->lmax, this->l->ssum+this->maxflag); 94     this->r->lmax=max(this->r->lmax, this->r->ssum+this->maxflag); 95     this->l->ssum+=this->flag; 96     this->r->ssum+=this->flag; 97     this->flag=0; 98     this->maxflag=0; 99 }100 inline void seg::maintain()101 {102     this->ssum=max(this->l->ssum, this->r->ssum);103     this->lmax=max(this->l->lmax, this->r->lmax);104 }105 inline seg * newseg()106 {107     seg * ret=port++;108     return ret;109 }110 seg * build(int l, int r)111 {112     seg * t=newseg();113     int m=(l+r)>>1;114     if (l==r) return t;115     t->l=build(l, m);116     t->r=build(m+1, r);117     return t;118 }119 void update(seg * t, int l, int r, int ql, int qr, int v)120 {121     if (l==ql && r==qr)122     {123         t->ssum+=v;124         t->lmax=max(t->lmax, t->ssum);125         t->flag+=v;126         t->maxflag=max(t->maxflag, t->flag);127     }128     else129     {130         int m=(l+r)>>1;131         t->pushdown();132         if (qr<=m) update(t->l, l, m, ql, qr, v);133         else if (ql>m) update(t->r, m+1, r, ql, qr, v);134         else update(t->l, l, m, ql, m, v), update(t->r, m+1, r, m+1, qr, v);135         t->maintain();136     }137 }138 int query(seg * t, int l, int r, int ql, int qr)139 {140     int ret=0;141 142     if (l==ql && r==qr)143         ret=t->lmax;144     else145     {146         int m=(l+r)>>1;147         t->pushdown();148         if (qr<=m) ret=query(t->l, l, m, ql, qr);149         else if (ql>m) ret=query(t->r, m+1, r, ql, qr);150         else ret=max(query(t->l, l, m, ql, m), query(t->r, m+1, r, m+1, qr));151         t->maintain();152     }153 154     return ret;155 }156 157 inline bool cmpForQuestion(int i, int j)158 {159     return r[i]<r[j];160 }161 inline bool cmpForDiscrete(int i, int j)162 {163     return a[i]<a[j];164 }165 inline void prepare()166 {167     static int d[sizeOfNumber], l[sizeOfNumber];168     int m, t;169 170     for (int i=1;i<=n;i++)171         l[i]=i;172     std::sort(l+1, l+n+1, cmpForDiscrete);173 174     m=1, t=a[l[m]];175     d[l[1]]=1;176     for (int i=2;i<=n;i++)177     {178         if (a[l[i]]>t)179             ++m, t=a[l[i]];180         d[l[i]]=m;181     }182 183     memset(l, 0, sizeof(l));184     for (int i=1;i<=n;i++)185     {186         p[i]=l[d[i]];187         l[d[i]]=i;188     }189 }

  1 #include <cstdio>  2 const int sizeOfNumber=50005;  3 const int sizeOfSeg=200002;  4   5 inline int max(int, int);  6 inline int getint();  7 inline void putint(int);  8   9 struct node 10 { 11     int lmax, rmax, smax, ssum; 12     inline node(int=0); 13 }; 14 inline node merge(node, node); 15  16 struct seg 17 { 18     node data; 19     seg * l, * r; 20     inline void maintain(); 21 }; 22 seg memory[sizeOfSeg], * port=memory; 23 inline seg * newseg(); 24 seg * build(int, int); 25 void update(seg * , int, int, int); 26 node query(seg * , int, int, int, int); 27  28 int n, m; 29 int a[sizeOfNumber]; 30 seg * t; 31  32 int main() 33 { 34     n=getint(); 35     for (int i=1;i<=n;i++) 36         a[i]=getint(); 37     t=build(1, n); 38  39     m=getint(); 40     for (int i=1;i<=m;i++) 41     { 42         int k=getint(), x=getint(), y=getint(); 43         if (k==1) 44             putint(query(t, 1, n, x, y).smax); 45         else 46         { 47             a[x]=y; 48             update(t, 1, n, x); 49         } 50     } 51  52     return 0; 53 } 54  55 inline int max(int x, int y) 56 { 57     return x>y?x:y; 58 } 59 inline int getint() 60 { 61     register int num=0; 62     register char ch=0, last; 63     do last=ch, ch=getchar(); while (ch<‘0‘ || ch>‘9‘); 64     do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘); 65     if (last==‘-‘) num=-num; 66     return num; 67 } 68 inline void putint(int num) 69 { 70     char stack[11]; 71     register int top=0; 72     if (num==0) stack[top=1]=‘0‘; 73     if (num<0) putchar(‘-‘), num=-num; 74     for ( ;num;num/=10) stack[++top]=num%10+‘0‘; 75     for ( ;top;top--) putchar(stack[top]); 76     putchar(‘\n‘); 77 } 78  79 inline node::node(int x) 80 { 81     lmax=rmax=smax=ssum=x; 82 } 83 inline node merge(node a, node b) 84 { 85     node c; 86     c.ssum=a.ssum+b.ssum; 87     c.lmax=max(a.lmax, a.ssum+b.lmax); 88     c.rmax=max(a.rmax+b.ssum, b.rmax); 89     c.smax=max(a.smax, b.smax); 90     c.smax=max(c.smax, a.rmax+b.lmax); 91     return c; 92 } 93  94 inline seg * newseg() 95 { 96     seg * ret=port++; 97     return ret; 98 } 99 inline void seg::maintain()100 {101     this->data=http://www.mamicode.com/merge(this->l->data, this->r->data);102 }103 inline seg * build(int l, int r)104 {105     seg * t=newseg();106     int m=(l+r)>>1;107 108     if (l==r)109         t->data=http://www.mamicode.com/node(a[m]);110     else111     {112         t->l=build(l, m);113         t->r=build(m+1, r);114         t->maintain();115     }116 117     return t;118 }119 void update(seg * t, int l, int r, int k)120 {121     int m=(l+r)>>1;122 123     if (l==r)124         t->data=http://www.mamicode.com/node(a[m]);125     else126     {127         if (k<=m) update(t->l, l, m, k);128         else update(t->r, m+1, r, k);129         t->maintain();130     }131 }132 node query(seg * t, int l, int r, int ql, int qr)133 {134     node ret;135     int m=(l+r)>>1;136 137     if (l==ql && r==qr) ret=t->data;138     else139     {140         if (qr<=m) ret=query(t->l, l, m, ql, qr);141         else if (ql>m) ret=query(t->r, m+1, r, ql, qr);142         else ret=merge(query(t->l, l, m, ql, m), query(t->r, m+1, r, m+1, qr));143     }144 145     return ret;146 }