Can you answer these queries II

?

這是一道線段樹的題目，維護歷史版本，給出N(<=100000)個數字(-100000<=x<=100000),要求求出在[l,r]區間里面的連續序列的最大值，并且重復的數字可以加入序列但是值不能再計算。

?

本題明顯使用線段樹,它只存在詢問而沒有修改操作,離線相對于在線更好維護。

定義s[i] = ai + ai+1 + ai+2 + ... an，以ai開頭的數列的和,那么每次加入更新ai 那么s1,s2,...si都會相應的加一個ai,s[1~i]中出現過a[i]是不能重復加值的,那么為了避免重復加值,用pre[a[i]]表示a[i]上一次出現的位置,那么也就是s[pre[ai]+1]~s[i]這一個區間加上a[i]，每一次更新a[i]都要記錄歷史版本的最大值和懶惰標記的最大值。

?

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std;const int N = 100010; const int M = 100010; const int C = 100001; long long res[N]; int a[N],pre[N<<1],n,m;struct Que{int l,r,ID;bool operator < (const Que &rhs)const{return r < rhs.r;} }question[M];struct Tree{long long s,ms,d,md;}tree[N<<2];#define lson k<<1,l,mid #define rson k<<1|1,mid+1,rvoid processup(int k){tree[k].s = max(tree[k<<1].s,tree[k<<1|1].s);tree[k].ms = max(tree[k<<1].ms,tree[k<<1|1].ms); }void processdown(int k){if(!tree[k].d && !tree[k].md)return;tree[k<<1].ms = max(tree[k<<1].ms,tree[k<<1].s+tree[k].md);tree[k<<1].md = max(tree[k<<1].md,tree[k<<1].d+tree[k].md);tree[k<<1].s += tree[k].d,tree[k<<1].d += tree[k].d;tree[k<<1|1].ms = max(tree[k<<1|1].ms,tree[k<<1|1].s+tree[k].md);tree[k<<1|1].md = max(tree[k<<1|1].md,tree[k<<1|1].d+tree[k].md);tree[k<<1|1].s += tree[k].d,tree[k<<1|1].d += tree[k].d;tree[k].d = tree[k].md = 0; }long long query(int k,int l,int r,int xl,int xr){if(l == xl && r == xr)return tree[k].ms;processdown(k);int mid = (l+r)>>1;if(xr <= mid)return query(lson,xl,xr);else if(xl > mid)return query(rson,xl,xr);else return max(query(lson,xl,mid),query(rson,mid+1,xr));processup(k); }void update(int k,int l,int r,int xl,int xr,long long x){if(l == xl && r == xr){tree[k].s += x;tree[k].d += x;tree[k].ms = max(tree[k].ms,tree[k].s);tree[k].md = max(tree[k].md,tree[k].d);return;}processdown(k);int mid = (l+r)>>1;if(xr <= mid)update(lson,xl,xr,x);else if(xl > mid)update(rson,xl,xr,x);else update(lson,xl,mid,x),update(rson,mid+1,xr,x);processup(k); }#define clr(a,b) memset(a,b,sizeof(a))int main(){while(scanf("%d",&n) == 1){clr(tree,0),clr(pre,0);for(int i = 1;i <= n;++i)scanf("%d",&a[i]);scanf("%d",&m);for(int i = 1;i <= m;++i){scanf("%d%d",&question[i].l,&question[i].r);question[i].ID = i;}sort(question+1,question+m+1);int ID = 1;for(int i = 1;i <= n;++i){update(1,1,n,pre[a[i]+C]+1,i,a[i]);pre[a[i]+C] = i;while(ID <= m && question[ID].r == i){res[question[ID].ID] = query(1,1,n,question[ID].l,question[ID].r);ID++;}}for(int i = 1;i <= m;++i)printf("%lld\n",res[i]);}return 0; }

　　

　　

轉載于:https://www.cnblogs.com/xgtao984/p/5721033.html

總結

以上是生活随笔為你收集整理的SPOJ GSS2 Can you answer these queries II (线段树离线) - xgtao -的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。