RT
本来想锻炼一下码力和处理细节的能力的,结果写挂了,已经调了2个月了。。。
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N = 2e6 + 5;
int mod = 1e18 + 3;
const int inf = 2e18;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
{
f = -1;
}
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
struct Node
{
int l, r;
long long w;//区间左端点、区间右端点、区间和
int tag, tag2, tag3;//加法标记、乘法标记、赋值标记
int maxx, minn;//最大、最小
} t[N << 2];
int a[N];
void push_up(int p)
{
t[p].w = (t[ls].w + t[rs].w);
t[p].minn = min(t[ls].minn, t[rs].minn);
t[p].maxx = max(t[ls].maxx, t[rs].maxx);
}
void build(int p, int l, int r)//建树
{
t[p].l = l, t[p].r = r;
t[p].tag = 0, t[p].tag2 = 1, t[p].tag3 = -inf;
if (l == r)
{
t[p].w = a[l], t[p].minn = a[l], t[p].maxx = a[l];
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(p);
}
void cover_down(int p)//赋值标记下传
{
if (t[p].tag3 != -inf)
{
t[ls].w = t[p].tag3, t[rs].w = t[p].tag3;
t[ls].tag = 0, t[rs].tag = 0;
t[ls].tag2 = 1, t[rs].tag2 = 1;
t[ls].maxx = t[rs].maxx = t[p].tag3;
t[ls].minn = t[rs].minn = t[p].tag3;
t[ls].tag3 = t[p].tag3;
t[rs].tag3 = t[p].tag3;
t[p].tag3 = -inf;
}
}
void sum_down(int p)//加法、乘法标记下传
{
t[ls].w = (t[ls].w * t[p].tag2 + t[p].tag * (t[ls].r - t[ls].l + 1));
t[rs].w = (t[rs].w * t[p].tag2 + t[p].tag * (t[rs].r - t[rs].l + 1));
t[ls].tag2 = t[ls].tag2 * t[p].tag2;
t[rs].tag2 = t[rs].tag2 * t[p].tag2;
t[ls].tag = (t[ls].tag * t[p].tag2 + t[p].tag);
t[rs].tag = (t[rs].tag * t[p].tag2 + t[p].tag);
t[ls].minn = (t[p].tag2 * t[ls].minn + t[p].tag);
t[rs].minn = (t[p].tag2 * t[rs].minn + t[p].tag);
t[ls].maxx = (t[p].tag2 * t[ls].maxx + t[p].tag);
t[rs].maxx = (t[p].tag2 * t[rs].maxx + t[p].tag);
t[p].tag = 0, t[p].tag2 = 1;
}
void push_down(int p)
{
cover_down(p), sum_down(p);
}
void mul(int p, int l, int r, int k)//区间乘
{
if (l <= t[p].l && r >= t[p].r)
{
cover_down(p);
t[p].maxx = t[p].maxx * k ;
t[p].minn = t[p].minn * k;
t[p].w = t[p].w * k;
t[p].tag = t[p].tag * k;
t[p].tag2 = t[p].tag2 * k;
return;
}
push_down(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
{
mul(ls, l, r, k);
}
if (r > mid)
{
mul(rs, l, r, k);
}
push_up(p);
}
void add(int p, int l, int r, int k)//区间加
{
if (l <= t[p].l && r >= t[p].r)
{
t[p].tag = (t[p].tag + k);
t[p].maxx = (t[p].maxx + k);
t[p].minn = (t[p].minn + k);
t[p].w = (t[p].w + k * (t[p].r - t[p].l + 1));
return;
}
push_down(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
{
add(ls, l, r, k);
}
if (r > mid)
{
add(rs, l, r, k);
}
push_up(p);
}
int ask(int p, int l, int r)//区间求和
{
if (l <= t[p].l && r >= t[p].r)
{
return t[p].w;
}
push_down(p);
int mid = (t[p].l + t[p].r) >> 1, ans = 0;
if (l <= mid)
{
ans = (ans + ask(ls, l, r));
}
if (r > mid)
{
ans = (ans + ask(rs, l, r));
}
return ans;
}
void add2(int p, int idx, int v)//单点加
{
if (t[p].l == t[p].r && t[p].l == idx)
{
t[p].w = (t[p].w + v) ;
return;
}
push_down(p);
int mid = (t[p].l + t[p].r) >> 1;
if (idx <= mid)
{
add2(ls, idx, v);
}
else
{
add2(rs, idx, v);
}
push_up(p);
}
int ask2(int p, int idx)//单点查询
{
if (t[p].l == t[p].r)
{
return t[p].w;
}
push_down(p);
int mid = (t[p].l + t[p].r) >> 1;
if (idx <= mid)
{
return ask2(ls, idx);
}
else
{
return ask2(rs, idx);
}
}
int askmin(int p, int l, int r)//区间min
{
if (l <= t[p].l && r >= t[p].r)
{
return t[p].minn;
}
push_down(p);
int mid = (t[p].l + t[p].r) >> 1, minnn = inf;
if (l <= mid)
{
minnn = min(minnn, askmin(ls, l, r));
}
if (r > mid)
{
minnn = min(minnn, askmin(rs, l, r));
}
return minnn;
}
int askmax(int p, int l, int r)//区间max
{
if (l <= t[p].l && r >= t[p].r)
{
return t[p].maxx;
}
push_down(p);
int mid = (t[p].l + t[p].r) >> 1, maxxx = -inf;
if (l <= mid)
{
maxxx = max(maxxx, askmax(ls, l, r));
}
if (r > mid)
{
maxxx = max(maxxx, askmax(rs, l, r));
}
return maxxx;
}
void modify(int p, int l, int r, int k)//区间赋值
{
if (l <= t[p].l && r >= t[p].r)
{
t[p].w = k * (t[p].r - t[p].l + 1);
t[p].tag = 0, t[p].tag2 = 1;
t[p].maxx = k, t[p].minn = k;
t[p].tag3 = k;
return;
}
push_down(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
{
modify(ls, l, r, k);
}
if (r > mid)
{
modify(rs, l, r, k);
}
push_up(p);
}
signed main()
{
ios;
int n = read(), m = read();
// mod = read();
for (int i = 1; i <= n; i++)
{
a[i] = read();
}
build(1, 1, n);
for (int i = 1; i <= m; i++)
{
int op = read();
if (op == 1) //区间加
{
int l = read(), r = read(), k = read();
add(1, l, r, k);
}
if (op == 2) //区间乘
{
int l = read(), r = read(), k = read();
mul(1, l, r, k);
}
if (op == 3) //区间查询
{
int l = read(), r = read();
cout << ask(1, l, r) << '\n';
}
if (op == 4) //区间max
{
int l = read(), r = read();
cout << askmax(1, l, r) << '\n';
}
if (op == 5) //区间min
{
int l = read(), r = read();
cout << askmin(1, l, r) << '\n';
}
if (op == 6) //单点加
{
int x = read(), k = read();
add2(1, x, k);
}
if (op == 7) //单点查询
{
int x = read();
cout << ask2(1, x) << '\n';
}
if (op == 8) //区间修改
{
int l = read(), r = read(), x = read();
modify(1, l, r, x);
}
}
return 0;
}
现在已经通过了P3372,P3373,P3374,P3368,P1253啦!!!
但是在ask与modify函数兼容的时候好像有点问题。。。
hack:
6 6
1 1 4 5 1 4
3 1 4
8 1 6 10
3 1 2
7 2
7 1
3 3 6
期望输出:
11
20
10
10
40
实际输出:
11
10
10
10
20
救救孩子吧。。。