QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#451515 | #7872. 崩坏天际线 | zqs | 0 | 1207ms | 16300kb | C++14 | 5.7kb | 2024-06-23 15:59:48 | 2024-06-23 15:59:48 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using std::min; using std::swap;
const int mod = 998244353, B = 200, N = 50005;
inline void add(int &x, const int y) {if ((x += y) >= mod) x -= mod;}
inline int plus(const int x, const int y) {return x + y < mod ? x + y : x + y - mod;}
int al[N], ar[N], op[N], p2[N], a[B + 5], tme[B + 5], n, q, ans;
int bl[B * B + 5], br[B * B + 5], bp[B * B + 5], cl[B + 5], cr[B + 5], stk[B + 5], cnt;
struct node {int ls, rs, sum, tag;} tr[2500005];
int id[N], pre[N], nxt[N], len[N];
bool vis[N], ban[N];
std::vector<int> vec[50005];
struct RMQ {
int st[17][50005], Log[50005];
void clear() {memset(st[0], 0x3f, sizeof st[0]);}
void set(int x, int v) {st[0][x] = v;}
void init() {
for (int i = 2; i <= n; ++ i) Log[i] = Log[i >> 1] + 1;
for (int i = 1; i <= 15; ++ i)
for (int j = 1; j + (1 << i) - 1 <= n; ++ j)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
int query(int l, int r) {
if (l > r) return q + 1;
int k = Log[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
} rmq;
int prob[N], rt1[N], rt2[N], tot;
void spread(int p) {
if (!tr[p].tag) return;
int ls = tr[p].ls, rs = tr[p].rs, tmp = tr[p].tag; tr[p].tag = 0;
if (ls) tr[ls].sum = 1ll * tr[ls].sum * p2[tmp] % mod, tr[ls].tag += tmp;
if (rs) tr[rs].sum = 1ll * tr[rs].sum * p2[tmp] % mod, tr[rs].tag += tmp;
}
void insert(int &p, int l, int r, int x, int v) {
if (!p) p = ++ tot, tr[p].ls = tr[p].rs = tr[p].sum = tr[p].tag = 0;
add(tr[p].sum, v); if (l == r) return;
int mid = l + r >> 1; spread(p);
x <= mid ? insert(tr[p].ls, l, mid, x, v) : insert(tr[p].rs, mid + 1, r, x, v);
}
void pushup(int p) {if (p) tr[p].sum = plus(tr[tr[p].ls].sum, tr[tr[p].rs].sum);}
void split(int &x, int &y, int l, int r, int k) {
if (!x || r <= k) return;
if (k < l) {y = x, x = 0; return;}
spread(x);
int mid = l + r >> 1, z = 0; tr[y = ++ tot].tag = 0;
if (k <= mid) {
split(tr[x].ls, z, l, mid, k), tr[y].ls = z, tr[y].rs = tr[x].rs, tr[x].rs = 0;
} else split(tr[x].rs, z, mid + 1, r, k), tr[y].ls = 0, tr[y].rs = z;
pushup(x), pushup(y);
}
void query(int p, int l, int r, int x) {
if (!p) return;
if (l == r) {ans = (ans + 1ll * abs(x - l) * tr[p].sum) % mod; return;}
spread(p);
query(tr[p].ls, l, l + r >> 1, x), query(tr[p].rs, (l + r >> 1) + 1, r, x);
}
void solve(int st) {
memset(pre, 0, sizeof pre), memset(nxt, 0, sizeof nxt);
memset(prob, 0, sizeof prob), memset(vis, 0, sizeof vis);
memset(ban, 0, sizeof ban), rmq.clear();
for (int i = q; i >= st; -- i) if (op[i] == 2) rmq.set(al[i], i);
rmq.init(), tot = 0;
for (int i = 1; i <= n; ++ i) vec[i].clear(), rt1[i] = rt2[i] = 0;
for (int i = 1; i <= cnt; ++ i) {
int fst = rmq.query(bl[i] + 1, br[i] - 1);
if (fst > q) ans = (ans + 1ll * bp[i] * (br[i] - bl[i])) % mod;
else vec[al[fst]].emplace_back(i), insert(rt1[al[fst]], 1, n, bl[i], bp[i]), insert(rt2[al[fst]], 1, n, br[i], bp[i]);
}
for (int i = st; i <= q; ++ i)
if (op[i] == 2) {if (vis[al[i]]) ban[i] = true; else vis[al[i]] = true;}
for (int i = 1, j = 0; i <= n; ++ i)
if (vis[i]) pre[i] = j, nxt[j] = i, len[j] = i - j, j = i;
pre[0] = nxt[0] = 0;
for (int i = q; i >= st; -- i) if (op[i] == 2 && !ban[i]) {
int x = al[i];
if (pre[x]) nxt[pre[x]] = nxt[x];
if (nxt[x]) pre[nxt[x]] = pre[x];
}
for (int i = st; i <= q; ++ i) if (op[i] == 2 && !ban[i]) {
int x = al[i], l = pre[x], r = nxt[x];
if (r) {
split(rt1[r], rt1[x], 1, n, x - 1), swap(rt1[r], rt1[x]);
if (rt1[x]) tr[rt1[x]].sum = 1ll * tr[rt1[x]].sum * p2[1] % mod, ++ tr[rt1[x]].tag;
}
if (l) {
split(rt2[l], rt2[x], 1, n, x);
if (rt2[x]) tr[rt2[x]].sum = 1ll * tr[rt2[x]].sum * p2[1] % mod, ++ tr[rt2[x]].tag;
}
prob[x] = (1ll * prob[l] * p2[1] + tr[rt1[x]].sum) % mod;
prob[l] = (1ll * prob[l] * p2[1] + tr[rt2[x]].sum) % mod;
for (int j : vec[x]) {
insert(rt1[x], 1, n, bl[j], 1ll * bp[j] * p2[1] % mod);
insert(rt2[x], 1, n, br[j], 1ll * bp[j] * p2[1] % mod);
}
}
for (int i = 1; i <= n; ++ i) {
if (prob[i]) ans = (ans + 1ll * len[i] * prob[i]) % mod;
if (rt1[i]) query(rt1[i], 1, n, i);
if (rt2[i]) query(rt2[i], 1, n, i);
}
}
int main() {
scanf("%d%d", &n, &q);
p2[0] = 1, p2[1] = mod + 1 >> 1;
for (int i = 1; i <= q; ++ i) {
scanf("%d%d", op + i, al + i); if (op[i] == 1) scanf("%d", ar + i);
}
for (int i = 2; i <= q; ++ i) p2[i] = 1ll * p2[1] * p2[i - 1] % mod;
for (int i = 1; i <= (q + B - 1) / B; ++ i) {
int st = (i - 1) * B + 1, ed = min(q, i * B), m = 0;
cnt = 0;
for (int j = ed; j >= st; -- j) {
if (op[j] == 2) {
int pos = m + 1;
for (int k = 1; k <= m; ++ k)
if (a[k] > al[j]) {pos = k; break;}
else if (a[k] == al[j]) {pos = 0, tme[k] = j; break;}
if (pos) {
++ m;
for (int k = m; k > pos; -- k) a[k] = a[k - 1], tme[k] = tme[k - 1];
a[pos] = al[j], tme[pos] = j;
}
} else {
int l = m + 1, r = 0;
for (int k = 1; k <= m; ++ k) if (a[k] > al[j]) {l = k; break;}
for (int k = m; k; -- k) if (a[k] < ar[j]) {r = k; break;}
if (l > r) {bl[++ cnt] = al[j], br[cnt] = ar[j], bp[cnt] = 1; continue;}
for (int k = l, top = 0; k <= r; ++ k) {
while (top && tme[stk[top]] > tme[k]) -- top;
stk[++ top] = k, cl[k] = top;
}
for (int k = r, top = 0; k >= l; -- k) {
while (top && tme[stk[top]] > tme[k]) -- top;
stk[++ top] = k, cr[k] = top;
}
for (int k = l; k < r; ++ k)
bl[++ cnt] = a[k], br[cnt] = a[k + 1], bp[cnt] = p2[cl[k] + cr[k + 1]];
bl[++ cnt] = al[j], br[cnt] = a[l], bp[cnt] = p2[cr[l]];
bl[++ cnt] = a[r], br[cnt] = ar[j], bp[cnt] = p2[cl[r]];
}
}
solve(ed + 1);
}
printf("%d", ans);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 8388kb
input:
500 500 1 119 258 2 134 2 417 2 176 2 61 2 60 2 110 1 335 336 1 96 111 2 202 1 138 344 2 358 2 134 1 29 54 1 73 381 1 179 495 2 490 2 418 2 186 2 183 1 168 340 2 78 1 15 27 2 373 1 245 498 1 372 495 2 244 2 63 1 174 490 2 282 2 417 1 272 408 1 109 134 2 303 2 345 1 238 401 1 36 480 1 21 483 2 10 1 3...
output:
940512851
result:
wrong answer 1st lines differ - expected: '855279801', found: '940512851'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 1207ms
memory: 16300kb
input:
50000 50000 1 24367 33007 1 14396 42256 1 6375 22327 1 7892 42501 1 10100 37998 1 6284 48524 1 7357 18164 1 16200 46424 1 18972 34131 1 16849 32591 1 1917 3018 1 19897 30272 1 45044 45753 1 18999 25448 1 5167 31033 1 6182 35335 1 7270 37270 1 12651 39965 1 28896 38022 1 13853 35426 1 35516 48244 1 1...
output:
531849550
result:
wrong answer 1st lines differ - expected: '733099543', found: '531849550'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%