首页 > 代码库 > Can you answer these queries II

Can you answer these queries II

2024-09-07 22:38:55   220人阅读

题意：

给一长度为n的序列，有m组询问，每一组询问给出[l,r]询问区间内的最大去重连续子段和。

 

解法：

考虑一下简化后的问题：如果题目要求询问查询以$r$为右端点且$l$大于等于给定值的去重连续子段和，

那么我们显然可以预处理出$pre(i)$表示$i$位置出现的数字上一次出现的位置。

那么我们可以从小到大枚举$r$，

线段树维护$[i,r]$的去重子段和，区间加+维护最大值进而求出$[i,r]$的去重子段和的最大值。

现在考虑r小于等于给定值的做法，

注意到r是从1开始到n枚举的，进而保证了线段树里出现过的值都是$[l_i,r_i],r_i<=r$的去重子段和。

所以我们只要维护一下历史上线段树$i$位置出现过的历史最大值即可。

注意区间加的$add$标记不可以简单的合并，

因为我们要求的是历史上出现过的最大值，有可能$add 2, add -2$两个标记合并为$add 0$，进而错过最优答案。

对于一个点的$add$操作可以认为是一个$add$的序列，

我们要维护$add$序列中出现过的最大的前缀和，类比经典的处理方法最大子段和。

注意到线段树要维护4个标记：

历史最大值

当前最大值

当前$add$

$add$序列里的最大前缀和

总效率$O(nlogn)$

 

技术分享 
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <map>
  5 #include <algorithm>
  6 
  7 #define N 100010
  8 #define l(x) ch[x][0]
  9 #define r(x) ch[x][1]
 10 #define LL long long
 11 #define INF 0x3f3f3f3f
 12 
 13 using namespace std;
 14 
 15 struct node
 16 {
 17     int l,r,id;
 18 }b[N];
 19 
 20 int n,totn,m;
 21 int a[N],pre[N],a0[N];
 22 int ch[N<<1][2];
 23 LL max_all[N<<1],maxv[N<<1];
 24 LL add_all[N<<1],addv[N<<1];
 25 LL ansv[N];
 26 map<int,int> pos;
 27 
 28 bool cmp(node a,node b)
 29 {
 30     return a.r<b.r;
 31 }
 32 
 33 void push(int x)
 34 {
 35     if(!addv[x] && !add_all[x]) return;
 36     add_all[l(x)]=max(add_all[l(x)],addv[l(x)]+max(add_all[x],0LL));
 37     max_all[l(x)]=max(max_all[l(x)],maxv[l(x)]-addv[l(x)]+max(add_all[l(x)],0LL));
 38     addv[l(x)]+=addv[x];
 39     maxv[l(x)]+=addv[x];
 40     
 41     add_all[r(x)]=max(add_all[r(x)],addv[r(x)]+max(add_all[x],0LL));
 42     max_all[r(x)]=max(max_all[r(x)],maxv[r(x)]-addv[r(x)]+max(add_all[r(x)],0LL));
 43     addv[r(x)]+=addv[x];
 44     maxv[r(x)]+=addv[x];
 45     addv[x]=0;
 46     add_all[x]=0;
 47 }
 48 
 49 void update(int x)
 50 {
 51     maxv[x]=max(maxv[l(x)],    maxv[r(x)]);
 52     max_all[x]=max(max_all[x],max_all[l(x)]);
 53     max_all[x]=max(max_all[x],max_all[r(x)]);
 54 }
 55 
 56 LL ask(int x,int l,int r,int ql,int qr)
 57 {
 58     push(x);
 59     if(ql<=l && r<=qr) return max_all[x];
 60     int mid=(l+r)>>1;
 61     LL ans=0;
 62     if(ql<=mid) ans = max(ans, ask(l(x),l,mid,ql,qr));
 63     if(mid<qr)  ans = max(ans, ask(r(x),mid+1,r,ql,qr));
 64     update(x);
 65     return ans;
 66 }
 67 
 68 void add(int x,int l,int r,int ql,int qr,LL qv)
 69 {
 70     push(x);
 71     if(ql<=l && r<=qr)
 72     {
 73         addv[x]=qv;
 74         add_all[x]=max(qv,0LL);
 75         maxv[x]+=qv;
 76         max_all[x]=max(max_all[x],maxv[x]);
 77         return;
 78     }
 79     int mid=(l+r)>>1;
 80     if(ql<=mid) add(l(x),l,mid,ql,qr,qv);
 81     if(mid<qr) add(r(x),mid+1,r,ql,qr,qv);
 82     update(x);
 83 }
 84 
 85 int build(int l,int r)
 86 {
 87     int x=++totn;
 88     max_all[x]=maxv[x]=0;
 89     add_all[x]=0;
 90     addv[x]=0;
 91     if(l==r) return x;
 92     int mid=(l+r)>>1;
 93     l(x)=build(l,mid);
 94     r(x)=build(mid+1,r);
 95     return x;
 96 }
 97 
 98 int main()
 99 {
100     while(~scanf("%d",&n))
101     {
102         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
103         scanf("%d",&m);
104         for(int i=1;i<=m;i++)
105         {
106             scanf("%d%d",&b[i].l,&b[i].r);
107             b[i].id=i;
108         }
109         sort(b+1,b+m+1,cmp);
110         totn=0;
111         pos.clear();
112         for(int i=1;i<=n;i++)
113         {
114             if(pos.count(a[i])) pre[i]=pos[a[i]];
115             else pre[i]=0,a0[i]=a[i];
116             pos[a[i]]=i;
117         }
118         build(1,n);
119         int j=1;
120         for(int i=1;i<=n;i++)
121         {
122             add(1,1,n,pre[i]+1,i,a[i]);
123             while(j<=m && b[j].r==i)
124             {
125                 ansv[b[j].id]=ask(1,1,n,b[j].l,b[j].r);
126                 j++;
127             }
128         }
129         for(int i=1;i<=m;i++)
130             printf("%lld\n",ansv[i]);
131     }
132     return 0;
133 }
View Code

 

Can you answer these queries II


联系
我们