題意：

給一長度為n的序列，有m組詢問，每一組詢問給出[l,r]詢問區(qū)間內(nèi)的最大去重連續(xù)子段和。

?

解法：

考慮一下簡化后的問題：如果題目要求詢問查詢以$r$為右端點(diǎn)且$l$大于等于給定值的去重連續(xù)子段和，

那么我們顯然可以預(yù)處理出$pre(i)$表示$i$位置出現(xiàn)的數(shù)字上一次出現(xiàn)的位置。

那么我們可以從小到大枚舉$r$，

線段樹維護(hù)$[i,r]$的去重子段和，區(qū)間加+維護(hù)最大值進(jìn)而求出$[i,r]$的去重子段和的最大值。

現(xiàn)在考慮r小于等于給定值的做法，

注意到r是從1開始到n枚舉的，進(jìn)而保證了線段樹里出現(xiàn)過的值都是$[l_i,r_i],r_i<=r$的去重子段和。

所以我們只要維護(hù)一下歷史上線段樹$i$位置出現(xiàn)過的歷史最大值即可。

注意區(qū)間加的$add$標(biāo)記不可以簡單的合并，

因?yàn)槲覀円蟮氖菤v史上出現(xiàn)過的最大值，有可能$add 2, add -2$兩個(gè)標(biāo)記合并為$add 0$，進(jìn)而錯(cuò)過最優(yōu)答案。

對(duì)于一個(gè)點(diǎn)的$add$操作可以認(rèn)為是一個(gè)$add$的序列，

我們要維護(hù)$add$序列中出現(xiàn)過的最大的前綴和，類比經(jīng)典的處理方法最大子段和。

注意到線段樹要維護(hù)4個(gè)標(biāo)記：

歷史最大值

當(dāng)前最大值

當(dāng)前$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

?

轉(zhuǎn)載于:https://www.cnblogs.com/lawyer/p/6530517.html

總結(jié)

以上是生活随笔為你收集整理的Can you answer these queries II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。