牛客小白月赛15 部分题解（线段树
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);
}
}
}
查看10道真题和解析
网易公司福利 162人发布