CodeForces722C数组破坏算法解析与优化策略

离线处理&＃xff0c;维护新区间首尾位置的起点和终点&＃xff0c;倒着处理&＃xff1b;

#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pairPII;
const double eps&＃61;1e-5;
const double pi&＃61;acos(-1.0);
//const int mod&＃61;1e9&＃43;7;
const int INF&＃61;0x3f3f3f3f;const int N&＃61;1e5&＃43;10;
struct asd{int s,t;
};
asd q[N];LL a[N];
LL ans[N],sum[N];
int sp[N],temp[N];int main()
{int n;scanf("%d",&n);sum[0]&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%lld",&a[i]);sum[i]&＃61;sum[i-1]&＃43;a[i];}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&sp[i]);memset(temp,0,sizeof(temp));for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)q[i].s&＃61;q[i].t&＃61;i;ans[n]&＃61;0;LL TMAX&＃61;0;for(int i&＃61;n;i>&＃61;2;i--){temp[sp[i]]&＃61;1;if(temp[sp[i]-1])q[sp[i]].s&＃61;q[sp[i]-1].s;if(temp[sp[i]&＃43;1])q[sp[i]].t&＃61;q[sp[i]&＃43;1].t;q[q[sp[i]].t].s&＃61;q[sp[i]].s;q[q[sp[i]].s].t&＃61;q[sp[i]].t;TMAX&＃61;max(TMAX,sum[q[sp[i]].t] - sum[q[sp[i]].s-1]);ans[i-1]&＃61;TMAX;
// printf("%d %d\n",q[sp[i]].s,q[sp[i]].t);}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)printf("%lld\n",ans[i]);return 0;
}