E、希望

线段树维护区间最小值，计算出数组中小于0的元素删除所需要的代价和删除后对答案的贡献，然后做一次01背包， 就是最后可以获得的值。

#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
const int MAXN = 1e5 + 5;
const int inf = 1e7;
struct node
{
	int l;
	int r;
	int set;
	int minn;
}que[MAXN * 4];
int n, m, k, ql, qr;
ll a[MAXN];
int val;
void up(int k)
{
	que[k].minn = min(que[k << 1].minn, que[k << 1 | 1].minn);
}
void down(int k)
{
	if (que[k].set != inf)
	{
		que[k << 1].set = min(que[k].set, que[k << 1].set);
		que[k << 1 | 1].set = min(que[k].set, que[k << 1 | 1].set);
		que[k << 1].minn = min(que[k].set, que[k << 1].minn);
		que[k << 1 | 1].minn = min(que[k].set, que[k << 1 | 1].minn);
		que[k].set = inf;
	}
}
void build(int left = 1, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	que[k].minn = inf;
	que[k].set = inf;
	if (left == right)
		return;
	imid;
	build(lson);
	build(rson);
}
void update(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].minn = min(que[k].minn, val);
		que[k].set = min(que[k].set, val);
		return;
	}
	down(k);
	imid;
	update(lson);
	update(rson);
	up(k);
}
int query(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return inf;
	if (ql <= left && right <= qr)
		return que[k].minn;
	down(k);
	imid;
	return min(query(lson), query(rson));
}
ll dp[505];
int main()
{
	ll sum = 0;
	scanf("%d%d%d", &n, &k, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		sum += a[i];
	}
	build();
	while (m--)
	{
		scanf("%d%d%d", &ql, &qr, &val);
		update();
	}
	for (int i = 1; i <= n; i++)
	{
		if (a[i] < 0)
		{
			ql = i, qr = i;
			int val = -a[i], w = query();
			for (int j = 504; j >= w; j--)
				dp[j] = max(dp[j], dp[j - w] + val);
		}
	}
	printf("%lld\n", sum + dp[k]);
}

J、外挂

通过观察操作2的计算方法，容易发现，然后维护区间和和区间平方和。

传递标记的时候，发现区间和和区间平方和存在关系式 

然后每次先维护区间平方和再维护区间和就可以啦

#include <bits/stdc++.h>
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
struct node
{
	int l;
	int r;
	ll mark;
	ll sum;
	ll sum2;
}que[MAXN * 4];
int n, m, q, ql, qr;
ll val, a[MAXN];
void up(int k)
{
	que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
	que[k].sum2 = que[k << 1].sum2 + que[k << 1 | 1].sum2;
}
void down(int k)
{
	if (que[k].mark)
	{
		que[k << 1].sum2 += 2 * que[k << 1].sum * que[k].mark + (que[k << 1].r - que[k << 1].l + 1) * que[k].mark * que[k].mark;
		que[k << 1 | 1].sum2 += 2 * que[k << 1 | 1].sum * que[k].mark + (que[k << 1 | 1].r - que[k << 1 | 1].l + 1) * que[k].mark * que[k].mark;

		que[k << 1].sum += que[k].mark * (que[k << 1].r - que[k << 1].l + 1);
		que[k << 1 | 1].sum += que[k].mark * (que[k << 1 | 1].r - que[k << 1 | 1].l + 1);

		que[k << 1].mark += que[k].mark;
		que[k << 1 | 1].mark += que[k].mark;
		que[k].mark = 0;
	}
}
void build(int left = 1, int right = n, int  k = 1)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = 0;
	if (left == right)
	{
		que[k].sum = a[left];
		que[k].sum2 = a[left] * a[left];
		return;
	}
	imid;
	build(lson);
	build(rson);
	up(k);
}
void update(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].mark += val;
		que[k].sum2 += 2 * que[k].sum * val + (right - left + 1) * val * val;
		que[k].sum += (right - left + 1) * val;
		return;
	}
	down(k);
	imid;
	update(lson);
	update(rson);
	up(k);
}
ll query1(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].sum;
	down(k);
	imid;
	return query1(lson) + query1(rson);
}
ll query2(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].sum2;
	down(k);
	imid;
	return query2(lson) + query2(rson);
}
int main()
{
	int op;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	build();
	while (m--)
	{
		scanf("%d%d%d", &op, &ql, &qr);
		if (op == 1)
		{
			scanf("%lld", &val);
			update();
		}
		else
		{
			ll ans1 = query1();
			ll ans2 = query2();
			printf("%lld\n", (ans1 * ans1 - ans2) / 2);
		}
	}
}