[BZOJ 1756]小白逛公园
这题是很经典的线段树题。
我们可以发现最长子序列或跨越中点，或不跨越中点。若不跨越则肯定在左子或右子中，跨越则是左子最大后缀和和右子最大前缀和之和。问题便迎刃而解。（当然，求区间最大前缀/后缀和要用上区间和）
需注意此题可能会出现a>b！
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | /************************************************************** Problem: 1756 User: danihao123 Language: C++ Result: Accepted Time:2604 ms Memory:49648 kb****************************************************************/ #include <cstdio>#include <algorithm>using namespace std;const int maxn=500001;struct Node{ int L,R; int maxP,maxS,ans,sum;};Node Tree[maxn*4];int A[maxn];void merge(Node& O,Node& LC,Node& RC){ O.sum=LC.sum+RC.sum; O.maxP=max(LC.maxP,LC.sum+RC.maxP); O.maxS=max(RC.maxS,RC.sum+LC.maxS); O.ans=max(max(LC.ans,RC.ans),LC.maxS+RC.maxP);}void maintain(int o){ Node& O=Tree[o],LC=Tree[o<<1],RC=Tree[o<<1|1]; merge(O,LC,RC);}void build_tree(int o,int L,int R){ Node& O=Tree[o]; O.L=L; O.R=R; if(L==R){ O.maxP=O.maxS=O.ans=O.sum=A[L]; }else{ int M=L+(R-L)/2; build_tree(o<<1,L,M); build_tree(o<<1|1,M+1,R); maintain(o); }}void update(int o,int p,int v){ Node& O=Tree[o]; int& L=O.L,R=O.R; if(L==R){ O.maxP=O.maxS=O.ans=O.sum=v; }else{ int M=L+(R-L)/2; if(p<=M) update(o<<1,p,v); else update(o<<1|1,p,v); maintain(o); }}int ql,qr;Node query(int o){ Node& O=Tree[o]; int& L=O.L,R=O.R; if(ql<=L && R<=qr){ return Tree[o]; } int M=L+(R-L)/2; Node ANS,LC,RC; if(ql<=M){ LC=query(o<<1); if(qr>M){ RC=query(o<<1|1); merge(ANS,LC,RC); return ANS; }else{ return LC; } }else{ RC=query(o<<1|1); return RC; }}int main(){ int n,m; register int i; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&A[i]); build_tree(1,1,n); int k,a,b; Node ans; for(i=1;i<=m;i++){ scanf("%d%d%d",&k,&a,&b); if(k&1){ if(a>b) swap(a,b); ql=a; qr=b; ans=query(1); printf("%d\n",ans.ans); }else{ update(1,a,b); } } return 0;} |
[BZOJ 3211]花神游历各国
这题和3038几乎一样啊……
但是注意有的喜欢度可能为0，这种情况不处理的话时间效率duangduangduang……
代码：
[BZOJ 3038]上帝造题的七分钟2
这题也真是的……
其实也不难，开多了就成1了，成1了再怎么开也是1……所以暴力单点修改+配合标记乱搞搞就行了
代码：
