UOJ #164 【清华集训2015】V (线段树)

题目链接

http://uoj.ac/problem/164

题解

神仙线段树题。
首先赋值操作可以等价于减掉正无穷再加上\(x\).
假设某个位置从前到后的操作序列是: \(x_1,x_2,...,x_k\)
那么则有: 当前值就是该序列的最大后缀和，历史最大值就是该序列的最大子段和！
然后如果把最大子段和定义加法，那么就变成了区间加单点查询。
直接线段树维护即可，时间复杂度\(O(n\log n)\).
（好吧，其实似乎把赋值看做减去正无穷再加\(x\)似乎是可以被卡爆long long的……）

代码

#include<bits/stdc++.h> #define llong long long using namespace std;const int N = 5e5; void updsum(llong &x,llong y) {x = x>=y?x:y;} struct Data {llong s,ls,rs,lrs;Data() {}Data(llong x) {lrs = x; x = x<0ll?0ll:x; s = ls = rs = x;}Data(llong _s,llong _ls,llong _rs,llong _lrs):s(_s),ls(_ls),rs(_rs),lrs(_lrs) {}bool operator ==(const Data &arg) const {return s==arg.s&&ls==arg.ls&&rs==arg.rs&&lrs==arg.lrs;} }; Data operator +(const Data &arg1,const Data &arg2) {Data ret(0,0,0,0);ret.lrs = arg1.lrs+arg2.lrs;ret.ls = max(arg1.ls,arg1.lrs+arg2.ls);ret.rs = max(arg1.rs+arg2.lrs,arg2.rs);ret.s = max(max(arg1.s,arg2.s),arg1.rs+arg2.ls);return ret; } llong a[N+3]; int n,q;struct SegmentTree {Data sgt[(N<<2)+3];void pushdown(int u){sgt[u<<1] = sgt[u<<1]+sgt[u];sgt[u<<1|1] = sgt[u<<1|1]+sgt[u];sgt[u] = Data(0);}void build(int u,int le,int ri,llong a[]){if(le==ri) {sgt[u] = Data(a[le]); return;}int mid = (le+ri)>>1;build(u<<1,le,mid,a); build(u<<1|1,mid+1,ri,a);}void add(int u,int le,int ri,int lb,int rb,llong x){if(le>=lb && ri<=rb) {sgt[u] = sgt[u]+Data(x); return;}pushdown(u);int mid = (le+ri)>>1;if(lb<=mid) add(u<<1,le,mid,lb,rb,x);if(rb>mid) add(u<<1|1,mid+1,ri,lb,rb,x);}llong query(int u,int le,int ri,int pos,int typ) //1:cur 2:hist{if(le==ri) {return typ==1?sgt[u].rs:sgt[u].s;}pushdown(u);int mid = (le+ri)>>1;if(pos<=mid) return query(u<<1,le,mid,pos,typ);else return query(u<<1|1,mid+1,ri,pos,typ);} } sgt;int main() {scanf("%d%d",&n,&q); llong cur = 0ll;for(int i=1; i<=n; i++) scanf("%lld",&a[i]),cur = max(cur,a[i]);sgt.build(1,1,n,a);while(q--){int opt; scanf("%d",&opt);if(opt==1||opt==2){int l,r; llong x; scanf("%d%d%lld",&l,&r,&x); if(opt==1) cur+=x; if(opt==2) x=-x;sgt.add(1,1,n,l,r,x);}else if(opt==3){int l,r; llong x; scanf("%d%d%lld",&l,&r,&x);sgt.add(1,1,n,l,r,-cur); sgt.add(1,1,n,l,r,x);}else if(opt==4||opt==5){int pos; scanf("%d",&pos);llong ans = sgt.query(1,1,n,pos,opt-3); printf("%lld\n",ans);}}return 0; }

总结

以上是生活随笔为你收集整理的UOJ #164 【清华集训2015】V (线段树)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。