网站开发参考书籍,网站开发那种语言,微信商城小程序平台,免费服务器申请SP1557 GSS2 - Can you answer these queries II \(\bigstar\texttt{Hint}\)#xff1a;遇到去重的问题#xff0c;我们通常考虑离线询问后处理。 可以枚举右端点#xff0c;将询问存储在右端点#xff0c;考虑用数据结构记录左端点的信息。 那么我们如果用线段树维护左端点… SP1557 GSS2 - Can you answer these queries II \(\bigstar\texttt{Hint}\)遇到去重的问题我们通常考虑离线询问后处理。 可以枚举右端点将询问存储在右端点考虑用数据结构记录左端点的信息。 那么我们如果用线段树维护左端点为它时的答案需要维护一下几种信息 历史最大值 \(hismax\)下传标记的增加值 \(lazadd\)当前的区间最大值 \(maxx\) WA 了捏啊标记没有及时下传可能有中间过程中的最大值没有统计到。 那就再记下一个 tag 表示历史最大 \(lazaddmax\) 对 \(lazadd\) 取最大值。 #define Maxn 400005
int n,m;
int a[Maxn],pre[Maxn1];
ll ans[Maxn];
vectorpa q[Maxn];
/*
由于下面标价下传时变量名称容易引起误导下次写的时候不妨这样写
struct TREE
{// Allpushedunpushedll maxAll,All,maxUnpused,UnpushedTREE(int _maxAll0,int _All0,int _maxUnpushed0,int _Unpushed0):maxAll(_maxAll),All(_All),maxUnpushed(_maxUnpushed),Unpushed(_Unpushed){}inline void Push(ll New,ll maxNew){maxAllmax(maxAll,AllmaxNew);AllNew;maxUnpushedmax(maxUnpushed,maxNew);UnpushedNew;}
}tree[Maxn2];
*/
struct TREE
{ll hismax,lazadd,maxx,lazaddmax;TREE(int H0,int La0,int M0,int Lam0):hismax(H),lazadd(La),maxx(M),lazaddmax(Lam){}inline void Push(ll x,ll addmax){lazaddmaxmax(lazaddmax,lazaddaddmax);lazaddx;hismaxmax(hismax,maxxaddmax);maxxx;}
}tree[Maxn2];
inline void pushdown(int p)
{tree[p1].Push(tree[p].lazadd,tree[p].lazaddmax);tree[p1|1].Push(tree[p].lazadd,tree[p].lazaddmax);tree[p].lazaddtree[p].lazaddmax0;
}
inline void pushup(int p)
{tree[p].maxxmax(tree[p1].maxx,tree[p1|1].maxx);tree[p].hismaxmax(tree[p].hismax,tree[p].maxx);
}
void add(int p,int nl,int nr,int l,int r,ll x)
{if(nll nrr) { tree[p].Push(x,x); return; }pushdown(p);int mid(nlnr)1;if(midl) add(p1,nl,mid,l,r,x);if(midr) add(p1|1,mid1,nr,l,r,x);pushup(p);
}
ll query(int p,int nl,int nr,int l,int r)
{if(nll nrr) return tree[p].hismax;pushdown(p);int mid(nlnr)1; ll ret0;if(midl) retmax(ret,query(p1,nl,mid,l,r));if(midr) retmax(ret,query(p1|1,mid1,nr,l,r));pushup(p);return ret;
}
int main()
{nrd();for(int i1;in;i) a[i]rd();mrd();for(int i1,l,r;im;i) lrd(),rrd(),q[r].eb(l,i);for(int r1;rn;r)// attention !! a_i\in[-100000,100000]{int Lastpre[a[r]100000];add(1,1,n,Last1,r,a[r]),pre[a[r]100000]r;for(pa v:q[r]) ans[v.se]query(1,1,n,v.fi,r);}for(int i1;im;i) printf(%lld\n,ans[i]);return 0;
}
