A 任意模数快速插值
题目大意 ： 求每个区间最大值与最小值乘积的和
-
线段树，每个叶子节点维护当前节点到i的最大值，最小值。发现最大值是不增，最小值是不降，所以区间覆盖一部分，实现的有点复杂
-
还可以分治求，代码短
Code
Show Code
#include <cstdio>
#include <algorithm>
#define ls (rt << 1)
#define rs (rt << 1| 1)
#define Add(x, y) ({int xx = x + y; xx < M ? xx : xx - M; })
using namespace std;
const int N = 5e5 + 5, M = 998244353;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
int n, ans;
struct Tree {
int s, d1, x1, d2, x2, s1, s2, t1, t2;
}t[N*4];
void Update1(int rt, int l, int r, int w) {
t[rt].d1 = t[rt].x1 = t[rt].t1 = w;
t[rt].s1 = 1ll * w * (r - l + 1) % M;
t[rt].s = 1ll * w * t[rt].s2 % M;
}
void Update2(int rt, int l, int r, int w) {
t[rt].d2 = t[rt].x2 = t[rt].t2 = w;
t[rt].s2 = 1ll * w * (r - l + 1) % M;
t[rt].s = 1ll * w * t[rt].s1 % M;
}
void Pushdown(int rt, int l, int r) {
int mid = l + r >> 1;
if (t[rt].t1 != -1) {
Update1(ls, l, mid, t[rt].t1);
Update1(rs, mid+1, r, t[rt].t1);
}
if (t[rt].t2 != -1) {
Update2(ls, l, mid, t[rt].t2);
Update2(rs, mid+1, r, t[rt].t2);
}
t[rt].t1 = t[rt].t2 = -1;
}
void Modify1(int rt, int l, int r, int x, int y, int w) {
if (t[rt].x1 >= w) return;
if (x <= l && r <= y && t[rt].d1 < w) return Update1(rt, l, r, w);
int mid = l + r >> 1; Pushdown(rt, l, r);
if (x <= mid) Modify1(ls, l, mid, x, y, w);
if (y > mid) Modify1(rs, mid+1, r, x, y, w);
t[rt].d1 = max(t[ls].d1, t[rs].d1);
t[rt].x1 = min(t[ls].x1, t[rs].x1);
t[rt].s1 = Add(t[ls].s1, t[rs].s1);
t[rt].s = Add(t[ls].s, t[rs].s);
}
void Modify2(int rt, int l, int r, int x, int y, int w) {
if (t[rt].d2 <= w) return;
if (x <= l && r <= y && t[rt].x2 > w) return Update2(rt, l, r, w);
int mid = l + r >> 1; Pushdown(rt, l, r);
if (x <= mid) Modify2(ls, l, mid, x, y, w);
if (y > mid) Modify2(rs, mid+1, r, x, y, w);
t[rt].d2 = max(t[ls].d2, t[rs].d2);
t[rt].x2 = min(t[ls].x2, t[rs].x2);
t[rt].s2 = Add(t[ls].s2, t[rs].s2);
t[rt].s = Add(t[ls].s, t[rs].s);
}
int Ask(int rt, int l, int r, int x, int y) {
if (x <= l && r <= y) return t[rt].s;
int mid = l + r >> 1, ans = 0; Pushdown(rt, l, r);
if (x <= mid) ans = Ask(ls, l, mid, x, y);
if (y > mid) ans = Add(ans, Ask(rs, mid + 1, r, x, y));
return ans;
}
int main() {
freopen("chazhi.in", "r", stdin);
freopen("chazhi.out", "w", stdout);
n = read();
for (int i = n * 4; i >= 1; --i)
t[i].d2 = t[i].x2 = 1e9, t[i].t1 = t[i].t2 = -1;
for (int i = 1; i <= n; ++i) {
int x = read();
Modify1(1, 1, n, 1, i, x);
Modify2(1, 1, n, 1, i, x);
if ((ans += Ask(1, 1, n, 1, i)) >= M) ans -= M;
}
printf("%d
", ans);
return 0;
}
B 斗转星移
题目大意 ： 坐标系上n个点，每次可以绕原点旋转或绕一直线对称，问一些点经过前几个操作后的坐标
- 真的挺简单，就记录一下怎么变就行
Code
Show Code
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
int n, m, x[N], y[N], z[N];
struct Node {
int a, b; ll c;
ll Cal(int i) {
return a * x[i] + b * y[i] + c;
}
}a[N], b[N];
Node Change(Node x) {
return (Node) {-x.a, -x.b, -x.c};
}
int main() {
freopen("passing.in", "r", stdin);
freopen("passing.out", "w", stdout);
n = read();
for (int i = 1; i <= n; ++i)
x[i] = read(), y[i] = read();
a[0].a = b[0].b = 1;
m = read();
for (int i = 1; i <= m; ++i) {
int op = read();
a[i] = a[i-1], b[i] = b[i-1];
if (op == 1) a[i] = Change(a[i]), swap(a[i], b[i]);
else if (op == 2) b[i] = Change(b[i]), swap(a[i], b[i]);
else if (op == 3) a[i] = Change(a[i]), a[i].c += read() * 2;
else if (op == 4) b[i] = Change(b[i]), b[i].c += read() * 2;
}
for (int q = read(); q; q--) {
int x1 = read(), x2 = read();
printf("%lld %lld
", a[x1].Cal(x2), b[x1].Cal(x2));
}
return 0;
}
C 如何更快出题 (Unaccepted)
题目大意 ：
Code
Show Code