題干：

給定一個(gè)有n個(gè)數(shù)的序列a1,a2,?...,?an

你每次可以將序列中一個(gè)數(shù)刪去，剩下的數(shù)會(huì)被分割為一段一段連續(xù)的數(shù)列

給定一個(gè)刪除數(shù)的順序，問在每次刪除之后，剩下的連續(xù)的數(shù)列中，數(shù)列和的最大值為多少

Input

第一行輸入僅有一個(gè)正整數(shù)n(1<=n<=100000)

第二行包括n個(gè)整數(shù)a1,a2,?...,?an(0<=ai<=1,000,000,000)

第三行為n個(gè)正整數(shù)的一個(gè)全排列，為刪除元素的順序。

Examples

Input

4 1 3 2 5 3 4 1 2

Output

5 4 3 0

Input

5 1 2 3 4 5 4 2 3 5 1

Output

6 5 5 1 0

Input

8 5 5 4 4 6 6 5 5 5 2 8 7 1 3 4 6

Output

18 16 11 8 8 6 6 0

Note

Consider the first sample:

Third element is destroyed. Array is now?1?3??*??5. Segment with maximum sum?5consists of one integer?5.

Fourth element is destroyed. Array is now?1?3??*???*?. Segment with maximum sum?4consists of two integers?1?3.

First element is destroyed. Array is now??*??3??*???*?. Segment with maximum sum?3consists of one integer?3.

Last element is destroyed. At this moment there are no valid nonempty segments left in this array, so the answer is equal to?0.

解題報(bào)告：

? 倒著考慮操作，并查集維護(hù)最大值即可。具體就是如果當(dāng)前操作位置idx，如果左邊已經(jīng)操作過，那就可以想做合并，同理可以向右合并，注意a[i]可以為0，所以不能用sum數(shù)組來判斷是否出現(xiàn)過，而應(yīng)該新開一個(gè)數(shù)組ok來記錄。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n,op[MAX],f[MAX]; ll a[MAX],sum[MAX],ans[MAX],mx; int getf(int v) {return f[v] == v ? v : f[v] = getf(f[v]); } void merge(int u,int v) {int t1 = getf(u),t2 = getf(v);if(t1 == t2) return;f[t2] = t1;sum[t1] += sum[t2];mx = max(mx,sum[t1]); } bool ok[MAX]; int main() {cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i),f[i] = i;for(int i = 1; i<=n; i++) scanf("%d",op+i);for(int i = n; i>=1; i--) {sum[op[i]] = a[op[i]];ok[op[i]]=1;mx = max(mx,sum[op[i]]);if(ok[op[i]+1] != 0) merge(op[i],op[i]+1);if(ok[op[i]-1] != 0) merge(op[i],op[i]-1);ans[i]=mx;}for(int i = 2; i<=n; i++) printf("%lld\n",ans[i]);puts("0");return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 722C】Destroying Array（并查集，时光倒流）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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