没睡醒的时候做这个题是最致命的 看上去能做 但是没有仔细分析就会掉进坑里 言归正传
题解: 这个题 很明显离线做 对于每个位置由线段树维护以x做起点[x,n]位置上的历史最大值 似乎吉利爷论文上有写 我们可以通过维护两个push操作直接的历史增量的峰值 来维护答案 我们可以这样分析 我们知道了rt的历史增量的峰值 那么rt<<1和rt<<1|1历史增量的峰值可以维护 然后我们可以通过增量维护历史最大值即可
#include <bits/stdc++.h>
const int MAXN=1e5+10;
#define ll long long
const ll inf=1e18;
using namespace std;
typedef struct node{
ll ans,sum,vtag,tag;
}node;
node d[MAXN<<2];
vector<int>vec;
int n,m;
int a[MAXN],b[MAXN];
void push(int rt){
d[rt<<1].ans=max(d[rt<<1].ans,d[rt<<1].sum+d[rt].vtag);
d[rt<<1|1].ans=max(d[rt<<1|1].ans,d[rt<<1|1].sum+d[rt].vtag);
d[rt<<1].sum+=d[rt].tag;d[rt<<1|1].sum+=d[rt].tag;
d[rt<<1].vtag=max(d[rt<<1].vtag,d[rt<<1].tag+d[rt].vtag);
d[rt<<1|1].vtag=max(d[rt<<1|1].vtag,d[rt<<1|1].tag+d[rt].vtag);
d[rt<<1].tag+=d[rt].tag;d[rt<<1|1].tag+=d[rt].tag;
d[rt].vtag=0;d[rt].tag=0;
}
void up(int x){
d[x].sum=max(d[x<<1].sum,d[x<<1|1].sum);
d[x].ans=max(d[x<<1].ans,d[x<<1|1].ans);
}
void update(int rt,int l,int r,int ql,int qr,int vul){
if(ql<=l&&r<=qr){
d[rt].sum+=vul;d[rt].tag+=vul;
d[rt].vtag=max(d[rt].vtag,d[rt].tag);
d[rt].ans=max(d[rt].ans,d[rt].sum);
return ;
}
int mid=(l+r)>>1;
push(rt);
if(ql<=mid)update(rt<<1,l,mid,ql,qr,vul);
if(qr>mid)update(rt<<1|1,mid+1,r,ql,qr,vul);
up(rt);
}
ll ans;
void querty(int rt,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){ans=max(ans,d[rt].ans);return ;}
int mid=(l+r)>>1;
push(rt);
if(ql<=mid)querty(rt<<1,l,mid,ql,qr);
if(qr>mid)querty(rt<<1|1,mid+1,r,ql,qr);
up(rt);
}
typedef struct Node{
int l,r,id;
friend bool operator<(Node aa,Node bb){return aa.r<bb.r;}
}Node;
Node que[MAXN];int pre[MAXN],vis[MAXN];
ll ans1[MAXN];
int main(){
scanf("%d",&n);
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++)scanf("%d",&a[i]),vec.push_back(a[i]);
sort(vec.begin(),vec.end());
int sz=unique(vec.begin(),vec.end())-vec.begin();
for(int i=1;i<=n;i++)b[i]=lower_bound(vec.begin(),vec.begin()+sz,a[i])-vec.begin()+1;
for(int i=1;i<=n;i++){vis[i]=pre[b[i]]+1;pre[b[i]]=i;}
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d%d",&que[i].l,&que[i].r),que[i].id=i;
sort(que+1,que+m+1);int k=1;
for(int i=1;i<=m;i++){
while(k<=n&&que[i].r>=k){update(1,1,n,vis[k],k,a[k]);k++;}
//cout<<d[1].ans<<" "<<d[1].sum<<endl;
ans=0;querty(1,1,n,que[i].l,que[i].r);ans1[que[i].id]=ans;
}
for(int i=1;i<=m;i++)printf("%lld
",ans1[i]);
return 0;
}
2482: [Spoj1557] Can you answer these queries II
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 280 Solved: 149
[Submit][Status][Discuss]
Description
给定n个元素的序列。
给出m个询问：求l[i]~r[i]的最大子段和（可选空子段）。
这个最大子段和有点特殊：一个数字在一段中出现了两次只算一次。
比如：1，2，3，2，2，2出现了3次，但只算一次，于是这个序列的和是1+2+3=6。
Input
第一行一个数n。
第二行n个数，为给定的序列，这些数的绝对值小于等于100000。
第三行一个数m。
接下来m行，每行两个数，l[i]，r[i]。
Output
M行，每行一个数，为每个询问的答案。
Sample Input
9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9
Sample Output
4
5
3
HINT
【数据说明】
30%：1 <= n, m <= 100
100%：1 <= n, m <= 100000