SP1557 GSS2 - Can you answer these queries II(线段树)

nofind · 2019-08-05 21:30:21 · 个人记录

题意:https://www.luogu.org/problem/SP1557

这种与区间不相同的数的题根据经验是离线来做的

线段树：叶子节点：sum(a[i]~r(r见下面)的和) maxx(sum的历史最大值) tags(区间加的标记) tagm(tags的历史最大值)

按照r将Query排序,每次枚举右端点r并更新线段树后,查询[ql,qr]这段区间的历史最大值即可

个人感受:想到了离线按右端点排序了,没想到还有维护历史最大值的操作,学到了

code:

#include<bits/stdc++.h>
using namespace std;
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define sum(p) (tree[p].sum)
#define maxx(p) (tree[p].maxx)
#define tags(p) (tree[p].tags)
#define tagm(p) (tree[p].tagm)
const int maxn=100010;
const int inf=100000;
int n,m;
int a[maxn],last[maxn<<1],pre[maxn<<1],ans[maxn];
struct Query
{
    int l,r,id;
}qr[maxn];
struct seg
{
    int sum,maxx;
    int tags,tagm;
}tree[maxn<<2];
inline int read()
{
    char c=getchar();int res=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
bool cmp(Query a,Query b){return a.r==b.r?a.l<b.l:a.r<b.r;}
inline void up(int p)
{
    sum(p)=max(sum(ls(p)),sum(rs(p)));
    maxx(p)=max(maxx(ls(p)),maxx(rs(p)));
}
inline void down(int p)
{
    maxx(ls(p))=max(maxx(ls(p)),sum(ls(p))+tagm(p));
    maxx(rs(p))=max(maxx(rs(p)),sum(rs(p))+tagm(p));
    sum(ls(p))+=tags(p),sum(rs(p))+=tags(p);
    tagm(ls(p))=max(tagm(ls(p)),tags(ls(p))+tagm(p));
    tagm(rs(p))=max(tagm(rs(p)),tags(rs(p))+tagm(p));
    tags(ls(p))+=tags(p),tags(rs(p))+=tags(p);
    tags(p)=tagm(p)=0;
} 
void add(int p,int L,int R,int l,int r,int k)
{
    if(L>=l&&R<=r)
    {
        sum(p)+=k;maxx(p)=max(maxx(p),sum(p));
        tags(p)+=k;tagm(p)=max(tagm(p),tags(p));
        return;
    }
    down(p);
    int mid=(L+R)>>1;
    if(l<=mid)add(ls(p),L,mid,l,r,k);
    if(r>mid)add(rs(p),mid+1,R,l,r,k);
    up(p);
}
int query(int p,int L,int R,int l,int r)
{
    if(L>=l&&R<=r)return tree[p].maxx;
    down(p);
    int mid=(L+R)>>1,res=-inf;
    if(l<=mid)res=max(res,query(ls(p),L,mid,l,r));
    if(r>mid) res=max(res,query(rs(p),mid+1,R,l,r));
    return res;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        pre[i]=last[a[i]+maxn];
        last[a[i]+maxn]=i;
    }
    /*for(int i=1;i<=n;i++) printf("%d ",pre[i]);
    puts("");*/
    m=read();
    for(int i=1;i<=m;i++) qr[i].l=read(),qr[i].r=read(),qr[i].id=i;
    sort(qr+1,qr+m+1,cmp);
    int j=1;
    for(int i=1;i<=n;i++)
    {
        add(1,1,n,pre[i]+1,i,a[i]);//puts("!");
        while(j<=m&&qr[j].r<=i)ans[qr[j].id]=query(1,1,n,qr[j].l,qr[j].r),j++;
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}