E. Permutation Separation 2200 （线段树裸题，前缀和，通过n2延伸到nlogn神仙题）

建树时下标都从1开始。

理解题意很重要

本板子线段树查询时右坐标需要严格不小于左坐标

本题连接

题意：

给定一个序列p(为1~n的排列)，和这个序列每一个数所对应的花费a以及序列的长度n。

取一数1≤k

将两个序列的某些数移到另一个序列使得第一个序列的所有数小于第二个序列的所有数，注意如果其中一组为空，则满足此条件，移动pi的花费是ai

求最小花费

思路：考虑维护前缀和，我们发现在最坏的条件下是把第一序列都移到第二序列去，做sum【i】为前缀和，到n-1就可以了，因为我们保证分的不为空，考虑（n2）做法，o（n）时间枚举分的位置，o（n）时间修改前后的数值，用线段树做区间修改，每次修改之后sum【i】的最小值就是在当前位置分的最小值，

当k>=posi时，p[posi]在第一序列，那么不需要费用

当k

题意不太好理解，做题优先考虑暴力做法，在暴力做法的基础上做数据结构进行优化。

/** 有 n 个数和 5 种操作
add a b c：把区间[a,b]内的所有数都增加 c
set a b c：把区间[a,b]内的所有数都设为 c
sum a b：查询区间[a,b]的区间和
max a b：查询区间[a,b]的最大值
min a b：查询区间[a,b]的最小值
*/
#include 
using namespace std;
const int maxn = 2e5 + 7;
const long long INF = 1LL << 62;
int qwe[1200000];
int pos[maxn];
struct Segment_tree {struct Node {int l, r;long long sum, max, min, set_lazy, add_lazy;} tre[maxn << 2];long long arr[maxn];//需要输入的数组inline void push_up(int rt) {if(tre[rt].l == tre[rt].r) {return ;}tre[rt].sum = tre[rt<<1].sum + tre[rt<<1|1].sum;tre[rt].max = max(tre[rt<<1].max, tre[rt<<1|1].max);tre[rt].min = min(tre[rt<<1].min, tre[rt<<1|1].min);}inline void push_down(int rt) {if(tre[rt].set_lazy) {///if set_lazy add_lazy = 0tre[rt<<1].set_lazy = tre[rt].set_lazy;tre[rt<<1].sum = (tre[rt<<1].r - tre[rt<<1].l + 1) * tre[rt].set_lazy;tre[rt<<1].max = tre[rt].set_lazy;tre[rt<<1].min = tre[rt].set_lazy;tre[rt<<1|1].set_lazy = tre[rt].set_lazy;tre[rt<<1|1].sum = (tre[rt<<1|1].r - tre[rt<<1|1].l + 1) * tre[rt].set_lazy;tre[rt<<1|1].max = tre[rt].set_lazy;tre[rt<<1|1].min = tre[rt].set_lazy;tre[rt].add_lazy = 0;tre[rt<<1].add_lazy = tre[rt<<1|1].add_lazy = 0;tre[rt].set_lazy = 0;return ;}if(tre[rt].add_lazy) {tre[rt<<1].add_lazy += tre[rt].add_lazy;tre[rt<<1].sum += (tre[rt<<1].r - tre[rt<<1].l + 1) * tre[rt].add_lazy;tre[rt<<1].max += tre[rt].add_lazy;tre[rt<<1].min += tre[rt].add_lazy;tre[rt<<1|1].add_lazy += tre[rt].add_lazy;tre[rt<<1|1].sum += (tre[rt<<1|1].r - tre[rt<<1|1].l + 1) *tre[rt].add_lazy;tre[rt<<1|1].max += tre[rt].add_lazy;tre[rt<<1|1].min += tre[rt].add_lazy;tre[rt].add_lazy = 0;}}void build(int rt,int l,int r) {tre[rt].l = l;tre[rt].r = r;tre[rt].set_lazy = 0;tre[rt].add_lazy = 0;if(l == r) {tre[rt].sum = tre[rt].max = tre[rt].min = arr[l];return ;}int mid = (l + r) >> 1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);push_up(rt);}void update1(int rt,int l,int r,long long val) { ///addpush_down(rt);if(l == tre[rt].l && tre[rt].r == r) {tre[rt].add_lazy = val;tre[rt].sum += (tre[rt].r - tre[rt].l + 1) * val;tre[rt].max += val;tre[rt].min += val;return ;}int mid = (tre[rt].l + tre[rt].r) >> 1;if(r <= mid) {update1(rt<<1,l,r,val);} else if(l > mid) {update1(rt<<1|1,l,r,val);} else {update1(rt<<1,l,mid,val);update1(rt<<1|1,mid+1,r,val);}push_up(rt);}void update2(int rt,int l,int r,long long val) { ///setpush_down(rt);if(l == tre[rt].l && tre[rt].r == r) {tre[rt].set_lazy = val;tre[rt].sum = (tre[rt].r - tre[rt].l + 1) * val;tre[rt].max = val;tre[rt].min = val;tre[rt].add_lazy = 0;return ;}int mid = (tre[rt].l + tre[rt].r) >> 1;if(r <= mid) {update2(rt<<1,l,r,val);} else if(l > mid) {update2(rt<<1|1,l,r,val);} else {update2(rt<<1,l,mid,val);update2(rt<<1|1,mid+1,r,val);}push_up(rt);}long long query1(int rt,int l,int r) { ///sumpush_down(rt);if(l == tre[rt].l && tre[rt].r == r) {return tre[rt].sum;}int mid = (tre[rt].l + tre[rt].r) >> 1;if(r <= mid) {return query1(rt<<1,l,r);} else if(l > mid) {return query1(rt<<1|1,l,r);} else {return query1(rt<<1,l,mid) + query1(rt<<1|1,mid+1,r);}}long long query2(int rt,int l,int r) { ///maxpush_down(rt);if(l == tre[rt].l && tre[rt].r == r) {return tre[rt].max;}int mid = (tre[rt].l + tre[rt].r) >> 1;if(r <= mid) {return query2(rt<<1,l,r);} else if(l > mid) {return query2(rt<<1|1,l,r);} else {return max(query2(rt<<1,l,mid), query2(rt<<1|1,mid+1,r));}}long long query3(int rt,int l,int r) { ///minpush_down(rt);if(l == tre[rt].l && tre[rt].r == r) {return tre[rt].min;}int mid = (tre[rt].l + tre[rt].r) >> 1;if(r <= mid) {return query3(rt<<1,l,r);} else if(l > mid) {return query3(rt<<1|1,l,r);} else {return min(query3(rt<<1,l,mid), query3(rt<<1|1,mid+1,r));}}
} s[5];
int main() {int n,t=0;cin>>n;for(int i=1; i<=n; i++) {scanf("%d",&t);pos[t]=i;}long long int sum=0;for(int i=1; i<=n; i++) {scanf("%d",&qwe[i]);s[1].arr[i]=s[1].arr[i-1]+1ll*qwe[i];}s[1].build(1,1,n);long long int ans=s[1].query3(1,1,n-1);for(int i=1; i<=n; i++) {if(pos[i]-1>=1)s[1].update1(1,1,pos[i]-1,qwe[pos[i]]);if(pos[i]<=n-1)s[1].update1(1,pos[i],n-1,-1*qwe[pos[i]]);ans=min(ans,s[1].query3(1,1,n-1));}printf("%lld\n",ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！