试题链接

题目描述

题意：

有两个序列，
操作1是将a序列的第x位改成y
操作2是将b序列的第x位改成y
操作3是找到一个cx，满足递推式c0=0，ci = max(ci-1+bi，ai)

题解：


官方题解
说实话我没大看懂。。。
题是我同学做的，他的思路是通过这个递推式可以推导出一个式子
然后用两个线段树来维护，一个用来维护ai-si的差值，一个用来维护b的前缀和
u1s1，码风不错，直接学习

代码：

#include<bits/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;
}