__QingYu @ 2022-01-03 15:02:26
这道题开O2可以用线段树吗
by Tom俩 @ 2022-01-03 15:03:03
NOPE
by Ruiqun2009 @ 2022-05-13 19:36:46
#include <cstdio>
#include <cmath>
#include <ctime>
#include <sys/mman.h>
using namespace std;
#define int long long
int n, m, a[1000001], check[1000001], nowu;
long long cnt1, cnt2;
struct judge
{
int op, x, y, w, belong;
} s[1000001];
char* sb;
inline int qread()
{
register int u = 0, f = 1;
while (*sb < 48)
f = (*sb == 45 ? -1 : f), sb++;
while (*sb > 32)
u = (u << 1) + (u << 3) + *sb++ - 48;
return u * f;
}
int c[1000005], qf[1000005];
bool check1;
inline void add(int now, int v)
{
for (; now <= n; now += now & -now)
{
c[now] += v;
}
}
inline int sum(int tmp)
{
register int s = 0;
for (; tmp > 0; tmp -= tmp & -tmp)
{
s += c[tmp];
}
return s;
}
inline void getmid(int pos, int l, int r, bool vis);
inline void getmid1(int pos, int l, int r, bool vis);
inline void getmid2(int pos, int l, int r, bool vis);
inline void getmn(int pos, int l, int r);
namespace io
{
const int size = (1 << 15) + 1;
char buf[size], * p1 = buf, * p2 = buf;
char buffer[size];
int op1 = -1;
const int op2 = size - 1;
struct FastIO
{
inline char readchar()
{
return p1 != p2 ? *p1++ : p1 == (p2 = (p1 = buf) + fread(buf, 1, size - 1, stdin)) ? EOF
: *p1++;
}
inline void flush()
{
fwrite(buffer, 1, op1 + 1, stdout), op1 = -1;
}
inline void writechar(const char& x)
{
if (op1 == op2)
flush();
buffer[++op1] = x;
}
#ifndef ONLINE_JUDGE
#define readchar getchar
#endif
inline int readint()
{
int s = 1, x = 0;
char c = readchar();
while (c <= 32)
{
c = readchar();
}
if (c == '-')
{
s = -1, c = readchar();
}
while ('0' <= c && c <= '9')
{
x = x * 10 + c - '0';
c = readchar();
}
return x * s;
}
inline int readuint()
{
int x = 0;
char c = readchar();
while (c <= 32)
{
c = readchar();
}
while ('0' <= c && c <= '9')
{
x = x * 10 + c - '0';
c = readchar();
}
return x;
}
inline void writeint(int x)
{
if (x < 0)
{
writechar('-'), x = -x;
}
char s[24];
int n = 0;
while (x || !n)
{
s[n++] = '0' + x % 10, x /= 10;
}
while (n--)
{
writechar(s[n]);
}
}
inline long long readlonglong()
{
long long x = 0, s = 1;
char c = readchar();
while (c <= 32)
{
c = readchar();
}
if (c == '-')
{
s = -1, c = readchar();
}
while ('0' <= c && c <= '9')
{
x = x * 10 + c - '0';
c = readchar();
}
return x * s;
}
inline unsigned long long readulonglong()
{
unsigned long long x = 0;
char c = readchar();
while (c <= 32)
{
c = readchar();
}
while ('0' <= c && c <= '9')
{
x = x * 10 + c - '0';
c = readchar();
}
return x;
}
inline void writelonglong(long long x)
{
if (x < 0)
{
writechar('-'), x = -x;
}
char s[25];
int n = 0;
while (x || !n)
{
s[n++] = '0' + x % 10, x /= 10;
}
while (n--)
{
writechar(s[n]);
}
}
inline int readstring(char* s)
{
int cnt = 0;
char c = readchar();
while (c <= 32)
{
c = readchar();
}
while (c > 32)
{
*s++ = c, ++cnt;
c = readchar();
}
return *s = 0, cnt;
}
inline void writestring(const char* s)
{
while (*s)
{
writechar(*s++);
}
}
inline int readdouble()
{
int zheng = 0, fuhao = 1;
double xiao = 0, chushu = 10;
char c;
while ((c = readchar()) < '0' || c > '9')
{
if (c == '-')
{
fuhao = -1;
}
}
while (c >= '0' && c <= '9')
{
zheng = zheng * 10 + c - '0';
c = readchar();
}
if (c != '.')
{
return fuhao * zheng;
}
while ((c = readchar()) >= '0' && c <= '9')
{
xiao += (c - '0') / chushu;
chushu *= 10;
}
return fuhao * (zheng + xiao);
}
} io;
#define readc io::io.readchar
#define writec io::io.writechar
#define read io::io.readint
#define readu io::io.readuint
#define write io::io.writeint
#define readl io::io.readlonglong
#define readlu io::io.readulonglong
#define writel io::io.writelonglong
#define reads io::io.readstring
#define writes io::io.writestring
#define readd io::io.readdouble
#define readchar io::io.readchar
#define writechar io::io.writechar
#define getchar readchar
#define putchar writechar
#define flush io::io.flush
}
using namespace io;
namespace work1
{
struct node
{
long long l, r, mid, sum;
int maxx, minn;
long long tag;
bool need;
node() {}
node(int _l, int _r, int _mid, int _sum, int _maxx, int _minn, int _tag) { l = _l, r = _r, mid = _mid, sum = _sum, maxx = _maxx, minn = _minn, tag = _tag, need = 0; }
} tree[5000005];
inline long long max(long long x, long long y)
{
return x > y ? x : y;
}
inline node merge(node x, node y)
{
return node(max(x.l, x.sum + y.l), max(y.r, y.sum + x.r), max(max(x.mid, y.mid), x.r + y.l), x.sum + y.sum, max(x.maxx, y.maxx), min(x.minn, y.minn), 0ll);
}
inline void push_down(int now, int l, int r)
{
int mid = (l + r) >> 1;
if (tree[now].tag != 0)
{
int mid = (l + r) >> 1;
tree[now << 1].sum += (mid - l + 1) * tree[now].tag;
tree[now << 1 | 1].sum += (r - mid) * tree[now].tag;
tree[now << 1].tag += tree[now].tag;
tree[now << 1 | 1].tag += tree[now].tag;
tree[now << 1].maxx += tree[now].tag;
tree[now << 1 | 1].maxx += tree[now].tag;
tree[now << 1].minn += tree[now].tag;
tree[now << 1 | 1].minn += tree[now].tag;
tree[now << 1].l = tree[now << 1].r = tree[now << 1].mid = max(tree[now << 1].sum, 0ll);
tree[now << 1 | 1].l = tree[now << 1 | 1].r = tree[now << 1 | 1].mid = max(tree[now << 1 | 1].sum, 0ll);
tree[now].tag = 0;
}
if (tree[now].need && l != r)
{
tree[now << 1].need = true;
tree[now << 1 | 1].need = true;
getmid(now << 1, l, mid, true);
getmid(now << 1 | 1, mid + 1, r, true);
tree[now].need = false;
}
}
inline void build(int now, int l, int r)
{
if (l == r)
{
tree[now].need = false;
tree[now].l = tree[now].r = tree[now].mid = max(a[l], 0ll);
tree[now].sum = tree[now].minn = tree[now].maxx = a[l];
tree[now].tag = 0;
return;
}
tree[now].need = false;
int mid = (l + r) >> 1;
build(now << 1, l, mid);
build(now << 1 | 1, mid + 1, r);
tree[now] = merge(tree[now << 1], tree[now << 1 | 1]);
}
inline void update(int now, int l, int r, int x, int y, int w)
{
if (l > y || r < x)
return;
if (x <= l && r <= y)
{
if (tree[now].maxx + w <= 0 || tree[now].minn + w >= 0)
{
tree[now].sum += (r - l + 1) * w;
tree[now].tag += w;
tree[now].l = tree[now].r = tree[now].mid = max(tree[now].sum, 0ll);
tree[now].maxx += w;
tree[now].minn += w;
tree[now].need = false;
return;
}
else if ((!check1 && r - l + 1 <= 500) || (check1 && r - l + 1 <= 5000))
{
tree[now].sum += (r - l + 1) * w;
tree[now].tag += w;
tree[now].maxx += w;
tree[now].minn += w;
tree[now].need = true;
getmid(now, l, r, true);
return;
}
}
if (r - l + 1 <= 500)
{
getmn(now, l, r);
if (tree[now].maxx <= 0 || tree[now].minn >= 0)
tree[now].mid = tree[now].l = tree[now].r = max(0ll, tree[now].sum);
else
getmid(now, l, r, true);
return;
}
push_down(now, l, r);
int mid = (l + r) >> 1;
update(now << 1, l, mid, x, y, w);
update(now << 1 | 1, mid + 1, r, x, y, w);
tree[now] = merge(tree[now << 1], tree[now << 1 | 1]);
}
inline node query(int now, int l, int r, int x, int y)
{
if (x <= l && r <= y)
return tree[now];
if (l <= x && r <= y && (r - x + 1) <= 700 && (tree[now].need || r - x <= 500))
{
getmid(0, x, r, true);
return tree[0];
}
if (l >= x && r >= y && (y - l + 1) <= 700 && (tree[now].need || y - l <= 500))
{
getmid(0, l, y, true);
return tree[0];
}
int mid = (l + r) >> 1;
push_down(now, l, r);
node ans;
if (x > mid)
ans = query(now << 1 | 1, mid + 1, r, x, y);
else if (y <= mid)
ans = query(now << 1, l, mid, x, y);
else
{
node resa = query(now << 1, l, mid, x, y), resb = query(now << 1 | 1, mid + 1, r, x, y);
ans = node(max(resa.l, resa.sum + resb.l), max(resb.r, resb.sum + resa.r), max(resa.mid, max(resb.mid, resa.r + resb.l)), resa.sum + resb.sum, 0ll, 0ll, 0ll);
}
tree[now] = merge(tree[now << 1], tree[now << 1 | 1]);
return ans;
}
}
namespace work2
{
int eps;
struct node
{
int l, r, mid, sum, maxx, minn;
bool check;
int tag;
}tree[1000005];
inline bool get(node now, int len)
{
return (now.maxx <= 0 || now.minn >= 0);
}
inline void push_down(int now, int l, int r)
{
int mid = (l + r) >> 1;
tree[now << 1].sum += (mid - l + 1) * tree[now].tag;
tree[now << 1 | 1].sum += (r - mid) * tree[now].tag;
tree[now << 1].tag += tree[now].tag;
tree[now << 1 | 1].tag += tree[now].tag;
tree[now << 1].maxx += tree[now].tag;
tree[now << 1 | 1].maxx += tree[now].tag;
tree[now << 1].minn += tree[now].tag;
tree[now << 1 | 1].minn += tree[now].tag;
tree[now << 1].check = get(tree[now << 1], mid - l + 1);
tree[now << 1 | 1].check = get(tree[now << 1 | 1], r - mid);
tree[now].tag = 0;
}
node merge(node x, node y, int len)
{
node ans = { max(x.l,x.sum + y.l),max(y.r,y.sum + x.r),max(max(x.mid,y.mid),x.r + y.l),x.sum + y.sum,max(x.maxx,y.maxx),min(x.minn,y.minn) };
if (x.check || y.check)
ans.check = true;
else
ans.check = false;
return ans;
}
void build(int now, int l, int r)
{
tree[now].tag = 0;
tree[now].check = false;
if (l == r)
{
tree[now].maxx = tree[now].minn = tree[now].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(now << 1, l, mid);
build(now << 1 | 1, mid + 1, r);
tree[now] = merge(tree[now << 1], tree[now << 1 | 1], r - l + 1);
}
void update(int now, int l, int r, int x, int y, int w)
{
if (l > y || r < x)
return;
if (x <= l && r <= y)
{
tree[now].sum += (r - l + 1) * w;
tree[now].maxx += w;
tree[now].minn += w;
tree[now].tag += w;
if ((tree[now].maxx <= 0 || tree[now].minn >= 0) && r - l + 1 >= eps)
tree[now].check = true;
else
tree[now].check = false;
return;
}
push_down(now, l, r);
int mid = (l + r) >> 1;
update(now << 1, l, mid, x, y, w);
update(now << 1 | 1, mid + 1, r, x, y, w);
tree[now] = merge(tree[now << 1], tree[now << 1 | 1], r - l + 1);
}
node query(int now, int l, int r, int x, int y)
{
tree[now].check = get(tree[now], r - l + 1);
if (l > y || r < x)
return node{ -10000000,-10000000,-10000000,0,0,0,0,0 };
if (x <= l && r <= y)
{
if (tree[now].maxx <= 0 || tree[now].minn >= 0)
{
tree[now].l = tree[now].r = tree[now].mid = max(tree[now].sum, 0ll);
return tree[now];
}
else if (r - l + 1 <= 300)
{
getmid(now, l, r, false);
return tree[now];
}
}
node ans;
push_down(now, l, r);
int mid = (l + r) >> 1;
if (l > mid)
ans = query(now << 1, l, mid, x, y);
else if (r <= mid)
ans = query(now << 1 | 1, mid + 1, r, x, y);
else
{
node a = query(now << 1, l, mid, x, y), b = query(now << 1 | 1, mid + 1, r, x, y);
ans = { max(a.l,a.sum + b.l),max(b.r,b.sum + a.r),max(max(a.mid,b.mid),a.r + b.l),a.sum + b.sum,max(a.maxx,b.maxx),min(a.minn,b.minn) };
}
tree[now] = merge(tree[now << 1], tree[now << 1 | 1], r - l + 1);
return ans;
}
}
signed main()
{
register int l, r, w;
srand(time(NULL));
sb = (char*)mmap(0, 900 << 20, PROT_READ, MAP_PRIVATE, fileno(stdin), 0);
n = qread(), m = qread();
for (register int i = 1; i <= n; ++i)
a[i] = qread();
for (register int i = 1; i <= m; ++i)
{
s[i].op = qread(), s[i].x = qread(), s[i].y = qread();
if (s[i].op == 1)
s[i].w = qread();
else cnt1 += s[i].y - s[i].x + 1;
}
double p = cnt1 * 1.0 / 1e10;
check1 = (p < 0.8 && p >= 0.7);
work2::eps = n / 100;
for (register int i = 1; i <= n; ++i)
qf[i] = a[i] - a[i - 1], add(i, qf[i]);
bool hmz = (cnt1 <= 2e9);
if (hmz)
work2::build(1, 1, n);
else
work1::build(1, 1, n);
for (register int k = 1; k <= m; ++k)
{
l = s[k].x, r = s[k].y, w = s[k].w;
if (!l) ++l;
nowu = l;
if (!hmz)
{
if (s[k].op == 1)
{
qf[l] += w, qf[r + 1] -= w;
add(l, w), add(r + 1, -w);
work1::update(1, 1, n, s[k].x, s[k].y, s[k].w);
}
else
{
if (r - l + 1 <= 20000)
{
register int ans = 0, now = 0, ql = sum(l), i;
for (i = l; i <= r - 11; i += 12)
{
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 1],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 2],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 3],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 4],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 5],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 6],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 7],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 8],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 9],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 10],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 11],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 12];
}
while (i <= r)
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[++i];
writel(ans), putchar('\n');
}
else
writel(work1::query(1, 1, n, s[k].x, s[k].y).mid), putchar('\n');
}
}
else
{
if (s[k].op == 1)
{
qf[l] += w, qf[r + 1] -= w;
add(l, w), add(r + 1, -w);
work2::update(1, 1, n, l, r, w);
}
else
{
if (r - l + 1 <= 80000)
{
register int ans = 0, now = 0, ql = sum(l), i;
for (i = l; i <= r - 11; i += 12)
{
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 1],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 2],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 3],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 4],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 5],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 6],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 7],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 8],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 9],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 10],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 11],
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 12];
}
while (i <= r)
now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[++i];
writel(ans), putchar('\n');
}
else
writel(work2::query(1, 1, n, l, r).mid), putchar('\n');
}
}
}
flush();
return 0;
}
inline void getmid(int pos, int l, int r, bool vis)
{
if (!pos || !vis || !check1 || (l != nowu && work1::tree[pos].maxx >= 4e9))
getmid1(pos, l, r, vis);
else
getmid2(pos, l, r, vis);
}
inline void getmid1(int pos, int l, int r, bool vis)
{
register int ans[3] = { 0,0,0 }, now[3] = { 0,0,0 }, ql = sum(l), i;
for (i = l; i <= r - 3; i += 4)
{
now[1] += ql, ans[1] = (ans[1] > now[1] ? ans[1] : now[1]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 1], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[1] += ql, ans[1] = (ans[1] > now[1] ? ans[1] : now[1]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 2], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[1] += ql, ans[1] = (ans[1] > now[1] ? ans[1] : now[1]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 3], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[1] += ql, ans[1] = (ans[1] > now[1] ? ans[1] : now[1]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 4], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]);
}
while (i <= r)
now[1] += ql, ans[1] = (ans[1] > now[1] ? ans[1] : now[1]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 1], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
++i;
if (vis)
work1::tree[pos].l = ans[1], work1::tree[pos].r = now[2], work1::tree[pos].mid = ans[2];
else
work2::tree[pos].l = ans[1], work2::tree[pos].r = now[2], work2::tree[pos].mid = ans[2];
}
inline void getmid2(int pos, int l, int r, bool vis)
{
register int now[3] = { 0,0,0 }, ql = sum(l), i, ans[3] = { 0,0,0 };
for (i = l; i <= r - 12; i += 13)
{
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 1], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 2], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 3], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 4], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 5], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 6], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 7], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 8], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 9], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 10], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 11], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 12], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 13], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]);
}
while (i <= r)
now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 1], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
++i;
if (vis)
work1::tree[pos].l = ans[1], work1::tree[pos].r = now[2], work1::tree[pos].mid = ans[2];
else
work2::tree[pos].l = ans[1], work2::tree[pos].r = now[2], work2::tree[pos].mid = ans[2];
}
inline void getmn(int pos, int l, int r)
{
register int i, su = 0, maxx = -1e10, minn = 1e10, ql = sum(l);
for (i = l; i <= r - 11; i += 12)
{
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 1],
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 2],
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 3],
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 4],
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 5],
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 6],
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 7],
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 8],
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 9],
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 10],
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 11],
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 12];
}
while (i <= r)
su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[++i];
work1::tree[pos].sum = su, work1::tree[pos].maxx = maxx, work1::tree[pos].minn = minn;
}记录
by MysteriousProgrammer @ 2022-05-24 22:20:30
@卍两袖清风卍 这道题时限1.00s就是为了不让用线段树做， 得用分块做(瞎猜的)
不会的话可以问问@Dyd本人
这位大佬成功AC了(每个测试点用时均在1s以内)
by __QingYu @ 2022-05-25 22:31:53
@_aa 谢谢啦
by MysteriousProgrammer @ 2022-05-26 08:17:33
@卍两袖清风卍 不用谢
by Ruiqun2009 @ 2022-05-27 11:15:15
这道题可以用珂朵莉树做吗
by Ruiqun2009 @ 2022-11-20 21:54:15
不行。这题没有区间赋值操作。
我只会这题的计算几何做法。有没有人用的是分段函数做法
by 添哥 @ 2023-07-12 14:28:42
在题解区有我写的分段函数做法哦
by MaskedFools_Sparkle @ 2024-08-07 19:42:27
@Ruiqun2009 亿点小把戏