网站建设图片怎么调,简单网站建设软件有哪些方面,杭州 网站建站,传统营销和网络营销的区别Can you answer these queries II 这是一道线段树的题目#xff0c;维护历史版本#xff0c;给出N(100000)个数字(-100000x100000),要求求出在[l,r]区间里面的连续序列的最大值#xff0c;并且重复的数字可以加入序列但是值不能再计算。 本题明显使用线段树,它只… Can you answer these queries II 这是一道线段树的题目维护历史版本给出N(100000)个数字(-100000x100000),要求求出在[l,r]区间里面的连续序列的最大值并且重复的数字可以加入序列但是值不能再计算。 本题明显使用线段树,它只存在询问而没有修改操作,离线相对于在线更好维护。 定义s[i] ai ai1 ai2 ... 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[N1],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[N2];#define lson k1,l,mid
#define rson k1|1,mid1,rvoid processup(int k){tree[k].s max(tree[k1].s,tree[k1|1].s);tree[k].ms max(tree[k1].ms,tree[k1|1].ms);
}void processdown(int k){if(!tree[k].d !tree[k].md)return;tree[k1].ms max(tree[k1].ms,tree[k1].stree[k].md);tree[k1].md max(tree[k1].md,tree[k1].dtree[k].md);tree[k1].s tree[k].d,tree[k1].d tree[k].d;tree[k1|1].ms max(tree[k1|1].ms,tree[k1|1].stree[k].md);tree[k1|1].md max(tree[k1|1].md,tree[k1|1].dtree[k].md);tree[k1|1].s tree[k].d,tree[k1|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 (lr)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,mid1,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 (lr)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,mid1,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(question1,questionm1);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
