#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n, m;
int w[N];
struct Node{
int l, r;
LL sum, add;
}tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.add) {
left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;
right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;
root.add = 0;
}
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r], 0};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void update(int u, int l, int r, int d)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
tr[u].add += d;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) update(u << 1, l, r, d);
if (r > mid) update(u << 1 | 1, l, r, d);
pushup(u);
}
}
LL query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
{
return tr[u].sum;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL res = 0;
if (l <= mid) res = query(u << 1, l, r);
if (r > mid) res += query(u << 1 | 1, l, r);
return res;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
build(1, 1, n);
while (m -- ) {
char c;
int l, r, a;
cin >> c;
if (c == 'C') {
scanf("%d%d%d", &l, &r, &a);
update(1, l, r, a);
}
else {
scanf("%d%d", &l, &r);
printf("%lld\n", query(1, l, r));
}
}
return 0;
}
活动打卡代码
AcWing 243. 一个简单的整数问题2
活动打卡代码
AcWing 300. 任务安排1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5010;
int n, m;
LL f[N], st[N], sc[N];
int main()
{
memset(f, 0x3f, sizeof f);
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
cin >> st[i] >> sc[i];
st[i] += st[i - 1], sc[i] += sc[i - 1];
}
f[0] = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < i; j ++ )
f[i] = min(f[i], f[j] + st[i] * (sc[i] - sc[j]) + m * (sc[n] - sc[j]));
cout << f[n] << endl;
return 0;
}
新鲜事
原文
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 1000010;
int n, m, ans;
int h[N], e[N], ne[N], idx;
int w[N], v[N];
char c[N];
int stk[N], top;
int f[N][2];
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs1(int u)
{
if (!c[u]) return v[u];
if (c[u] == '!') w[u] = !dfs1(e[h[u]]);
else
{
int a = e[h[u]], b = e[ne[h[u]]];
if (c[u] == '&') w[u] = dfs1(a) & dfs1(b);
else w[u] = dfs1(a) | dfs1(b);
}
return w[u];
}
void dfs2(int u) {
if (!c[u]) {
f[u][v[u]] = 0, f[u][v[u] ^ 1] = 1;
return;
}
f[u][w[u]] = 0;
int a = e[h[u]], b = e[ne[h[u]]];
dfs2(a), dfs2(b);
if (c[u] == '&') {
if (w[u] == 0)
f[u][w[u] ^ 1] = f[a][1] + f[b][1];
else
f[u][w[u] ^ 1] = min(f[a][0] + f[b][0], min(f[a][1] + f[b][0], f[a][0] + f[b][1]));
}
else {
if (w[u] == 0)
f[u][w[u] ^ 1] = min(f[a][1] + f[b][0], min(f[a][1] + f[b][1], f[a][0] + f[b][1]));
else
f[u][w[u] ^ 1] = f[a][0] + f[b][0];
}
}
int main()
{
int T;
cin >> T;
while (T -- ) {
memset(h, -1, sizeof h);
idx = 0, top = 0;
memset(f, 0, sizeof f);
cin >> n;
m = n;
string s;
getchar();
getline(cin, s);
for (int i = 1; i <= n; i ++ ) cin >> v[i];
for (int i = 0; i < s.size(); i ++ )
{
if (s[i] == ' ') continue;
if (s[i] == 'x')
{
int j = i + 1, x = 0;
while (j < s.size() && isdigit(s[j])) x = x * 10 + s[j ++ ] - '0';
stk[ ++ top] = x;
i = j;
}
else
{
c[ ++ m] = s[i];
add(m, stk[top -- ]);
add(m, stk[top -- ]);
stk[ ++ top] = m;
}
}
ans = dfs1(m);
dfs2(m);
cout << f[m][ans ^ 1] << endl;
}
return 0;
}
