$\href{https://www.acwing.com/blog/content/14829/}{个人主页}$但是我真的没被封号！别去问y总了！y总都快被你们烦死了……！！六年级同学

3.8万

Kx233

AcWing2AK
ydl
2010
Ll10nG2h0u
SeanLu
124Kk
max2021
acwing_693
heruimiao123456
NO.1-Finn

FFT 基本看不懂wtcl

#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;
}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];
}
}

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;
}
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;
}



#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; }