网站开发的逻辑,免费小程序制作软件,建设厅资质管理网站,公司网站建设会计处理试题链接
题目描述 题意#xff1a;
有两个序列#xff0c; 操作1是将a序列的第x位改成y 操作2是将b序列的第x位改成y 操作3是找到一个cx#xff0c;满足递推式c00#xff0c;ci max(ci-1bi#xff0c;ai)
题解#xff1a; 官方题解 说实话我没大看懂。。。 题是我同…试题链接
题目描述 题意
有两个序列 操作1是将a序列的第x位改成y 操作2是将b序列的第x位改成y 操作3是找到一个cx满足递推式c00ci max(ci-1biai)
题解 官方题解 说实话我没大看懂。。。 题是我同学做的他的思路是通过这个递推式可以推导出一个式子 然后用两个线段树来维护一个用来维护ai-si的差值一个用来维护b的前缀和 u1s1码风不错直接学习
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;//simplify long long
typedef unsigned long long ull;
#define inf 2147483647
#define pi 3.14159265358979
#define rep(i, l, r) for(int i l; i r; i )
#define lop(i, r, l) for(int i r; i l; i --)
#define step(i, l, r, __step) for(int i l; i r; i __step)
#define revp(i, r, l, __step) for(int i r; i l; i - __step)
#define regsiter reg
#define regsiter int RI
#define regsiter long long RL
inline ll read()//fast read
{ll ret 0, sgn 1;char chr getchar();while(chr 0 || chr 9){if(chr -) sgn -1; chr getchar();}while(chr 0 chr 9){ret ret * 10 chr - 0; chr getchar();}return ret * sgn;
}
const int N 2e5 5;
int n, m;
struct seg{int l, r;ll sum, maxw, add;
}tr[N 2][2];
#define ls p 1
#define rs p 1 | 1
ll A[N], B[N], S[N], E[N];
inline void update(int p, int t)
{tr[p][t].sum tr[ls][t].sum tr[rs][t].sum;tr[p][t].maxw max(tr[ls][t].maxw, tr[rs][t].maxw);
}
void build(int p, int l, int r, int t)
{tr[p][t].l l;tr[p][t].r r;tr[p][t].add 0;if(l r){if(!t){tr[p][t].sum S[l];tr[p][t].maxw S[l];}else{tr[p][t].sum E[l];tr[p][t].maxw E[l];}return;}int mid l r 1;build(ls, l, mid, t);build(rs, mid 1, r, t);update(p, t);
}
void pushdown(int p, int t)
{if(tr[p][t].add){ll v tr[p][t].add;tr[p][t].add 0;tr[ls][t].add v;tr[ls][t].sum v * (tr[ls][t].r - tr[ls][t].l 1);tr[ls][t].maxw v;tr[rs][t].add v;tr[rs][t].sum v * (tr[rs][t].r - tr[rs][t].l 1);tr[rs][t].maxw v;}
}
void modify_add(int p, int l, int r, ll v, int t)
{if(l tr[p][t].l r tr[p][t].r){tr[p][t].add v;tr[p][t].sum v * (tr[p][t].r - tr[p][t].l 1);tr[p][t].maxw v;return;}pushdown(p, t);int mid tr[p][t].l tr[p][t].r 1;if(l mid) modify_add(ls, l, r, v, t);if(r mid) modify_add(rs, l, r, v, t);update(p, t);
}
ll ask_sum(int p, int l, int r, int t)
{if(l tr[p][t].l r tr[p][t].r){return tr[p][t].sum;}pushdown(p, t);int mid tr[p][t].l tr[p][t].r 1;ll ret 0;if(l mid) ret ask_sum(ls, l, r, t);if(r mid) ret ask_sum(rs, l, r, t);return ret;
}
ll ask_maxw(int p, int l, int r, int t)
{if(l tr[p][t].l r tr[p][t].r){return tr[p][t].maxw;}pushdown(p, t);int mid tr[p][t].l tr[p][t].r 1;ll ret -inf;if(l mid) ret max(ret, ask_maxw(ls, l, r, t));if(r mid) ret max(ret, ask_maxw(rs, l, r, t));return ret;
}
int main()
{while(~scanf(%d%d, n, m)){rep(i, 1, n) A[i] read();rep(i, 1, n) B[i] read();rep(i, 1, n) S[i] S[i - 1] B[i];rep(i, 1, n) E[i] A[i] - S[i];int op, a;ll b;build(1, 1, n, 0);build(1, 1, n, 1);while(m --){scanf(%d, op);if(op 1){scanf(%d%lld, a, b);ll v b - A[a];A[a] b;modify_add(1, a, a, v, 1);}else if(op 2){scanf(%d%lld, a, b);ll v b - B[a];B[a] b;modify_add(1, a, n, v, 0);modify_add(1, a, n, -v, 1);}else{scanf(%d, a);ll ans max(ask_maxw(1, 1, a, 1), 0ll) ask_sum(1, a, a, 0);printf(%lld\n, ans);}}}return 0;
}
