結果
| 問題 |
No.3251 kthmex
|
| コンテスト | |
| ユーザー |
 jiangxinyang
|
| 提出日時 | 2025-08-07 12:05:26 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,614 ms / 2,500 ms |
| コード長 | 8,977 bytes |
| コンパイル時間 | 2,264 ms |
| コンパイル使用メモリ | 215,040 KB |
| 実行使用メモリ | 323,396 KB |
| 最終ジャッジ日時 | 2025-08-29 11:41:50 |
| 合計ジャッジ時間 | 22,136 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 32 |
コンパイルメッセージ
main.cpp:48:15: warning: extra tokens at end of #undef directive
48 | #undef getchar()
| ^
ソースコード
#include <bits/stdc++.h>
#define fp(i, a, b) for (int i(a), ed(b); i <= ed; ++i)
#define fb(i, a, b) for (int i(a), ed(b); i >= ed; --i)
#define go(u, i) for (int i(head[u]); i; i = e[i].nxt)
using namespace std;
typedef long long Int;
typedef pair<int, int> pii;
////////////////////////////////////////////////////////////////////////////////////////////////////
template <typename T1, typename T2>
inline void chkmin(T1& a, T2 b) {
if (a > b) a = b;
}
template <typename T1, typename T2>
inline void chkmax(T1& a, T2 b) {
if (a < b) a = b;
}
namespace FastIO {
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
template <typename T>
inline T read() {
T x = 0, w = 0;
char ch = getchar();
while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar();
while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();
return w ? -x : x;
}
template <typename T>
inline void write(T x) {
if (!x) return;
write<T>(x / 10), putchar((x % 10) ^ '0');
}
template <typename T>
inline void print(T x) {
if (x > 0)
write<T>(x);
else if (x < 0)
putchar('-'), write<T>(-x);
else
putchar('0');
}
template <typename T>
inline void print(T x, char en) {
print<T>(x), putchar(en);
}
}; // namespace FastIO
using namespace FastIO;
#undef getchar()
const int maxn = 1e5 + 10, maxm = 2e5 + 10, mod = 998244353;
const int Q = 100005;
const int P = 200005;
const int O = 62;
const int H = 62;
int n, m, a[maxn], b[maxm], Mx, B, T, bl[maxn], bx[maxm], cb, lp[maxn], rp[maxn];
struct oper {
int op, l, r, x, y;
oper() = default;
} q[maxn];
bool in[maxn];
std::map<int, bool> vst;
int ps[62][maxm], rt[62][62], pt[62][maxm];
namespace dsu {
int prt[maxn];
inline void init(const int n) {
fp(i, 1, n) prt[i] = i;
}
inline int Grt(const int x) {
if (x ^ prt[x]) return prt[x] = Grt(prt[x]);
return x;
}
} // namespace dsu
int sz[62], stk[maxn], tn;
unsigned short pool[maxn * 40 * 41], *cur = pool;
struct BIT {
unsigned short* c;
int lim;
inline void insert(const int x) {
for (int i = x; i; i -= i & -i) ++c[i];
}
inline void erase(const int x) {
for (int i = x; i; i -= i & -i) --c[i];
}
inline int qry(const int x) {
int res = 0;
for (int i = x; i <= lim; i += i & -i) res += c[i];
return res;
}
inline void bld() {
fp(i, 1, tn)++ c[stk[i]];
fb(i, lim, 1) c[i - (i & -i)] += c[i];
}
};
BIT rn[62][62];
int cc[62], st[maxn];
bool vs[maxm];
inline void rbd(const int l, const int r, const int x, const int y) {
const int o = bl[l], L = lp[o], R = rp[o], vx = bx[x], vy = bx[y];
const int tx = ps[o][x], ty = ps[o][y];
pt[o][x] = pt[o][y] = ps[o][x] = ps[o][y] = 0;
int top = 0;
fp(i, L, R) {
a[i] = a[dsu::Grt(i)];
if (a[i] == x || a[i] == y) st[++top] = i;
}
fp(i, l, r) if (a[i] == x) a[i] = y;
fp(i, 1, top) {
const int t = st[i], v = a[t];
ps[o][v] = t;
int& ro = pt[o][v];
if (!ro) ro = t;
dsu::prt[t] = ro;
}
if (!ps[o][x]) ps[o][x] = ps[o - 1][x];
if (!ps[o][y]) ps[o][y] = ps[o - 1][y];
if (tx ^ ps[o][x]) rn[o][vx].erase(tx), rn[o][vx].insert(ps[o][x]);
if (ty ^ ps[o][y]) rn[o][vy].erase(ty), rn[o][vy].insert(ps[o][y]);
}
inline void mdy(const int l, const int r, const int x, const int y) {
if (x == y) return;
const int lb = bl[l], rb = bl[r], vx = bx[x], vy = bx[y];
if (lb == rb) {
rbd(l, r, x, y);
const int px = ps[lb][x], py = ps[lb][y];
fp(i, lb + 1, cb - 1) {
if (ps[i][x] >= l && ps[i][x] <= r && (ps[i][x] != px)) {
rn[i][vx].erase(ps[i][x]);
ps[i][x] = px;
if (px) rn[i][vx].insert(px);
}
if (py && (!ps[i][y] || ps[i][y] < py)) {
if (ps[i][y]) rn[i][vy].erase(ps[i][y]);
ps[i][y] = py;
rn[i][vy].insert(py);
}
}
return;
}
rbd(l, rp[lb], x, y);
fp(i, lb + 1, rb - 1) {
if (!pt[i][x]) {
if (ps[i][x] ^ ps[i - 1][x]) {
if (ps[i][x]) rn[i][vx].erase(ps[i][x]);
ps[i][x] = ps[i - 1][x];
if (ps[i][x]) rn[i][vx].insert(ps[i][x]);
}
if (ps[i][y] ^ ps[i - 1][y]) {
if (!pt[i][y]) {
if (ps[i][y]) rn[i][vy].erase(ps[i][y]);
ps[i][y] = ps[i - 1][y];
if (ps[i][y]) rn[i][vy].insert(ps[i][y]);
}
}
continue;
}
if (!pt[i][y])
pt[i][y] = pt[i][x], a[pt[i][y]] = y;
else
dsu::prt[pt[i][x]] = dsu::prt[pt[i][y]];
if (ps[i][x]) rn[i][vx].erase(ps[i][x]);
if (!ps[i][y] || (ps[i][y] < ps[i][x])) {
if (ps[i][y]) rn[i][vy].erase(ps[i][y]);
ps[i][y] = ps[i][x];
if (ps[i][y]) rn[i][vy].insert(ps[i][y]);
}
ps[i][x] = ps[i - 1][x];
if (ps[i][x]) rn[i][vx].insert(ps[i][x]);
pt[i][x] = 0;
}
rbd(lp[rb], r, x, y);
const int px = ps[rb][x], py = ps[rb][y];
fp(i, rb + 1, cb - 1) {
if (ps[i][x] >= l && ps[i][x] <= r && (ps[i][x] != px)) {
rn[i][vx].erase(ps[i][x]);
ps[i][x] = px;
if (px) rn[i][vx].insert(px);
}
if (py && (!ps[i][y] || ps[i][y] < py)) {
if (ps[i][y]) rn[i][vy].erase(ps[i][y]);
ps[i][y] = py;
rn[i][vy].insert(py);
}
}
}
inline void qry(const int l, const int r, int k) {
const int o = bl[r] - 1, p = rp[o];
if (p < l) {
fp(i, l, r) {
const int o = a[dsu::Grt(i)];
if (!vs[o]) ++cc[bx[o]], vs[o] = 1;
}
int i = 1, j = 1;
for (; j <= Mx; ++i, j += T) {
const int t = sz[i] - cc[i];
if (t >= k) break;
k -= t;
}
j = min(j, Mx + 1);
for (; k && j <= i * T && j <= Mx; ++j) {
const int t = b[j] - b[j - 1] - vs[j];
if (t >= k) break;
k -= t;
}
FastIO::print(b[j - 1] + k, '\n');
fp(i, l, r) {
const int o = a[dsu::Grt(i)];
cc[bx[o]] = vs[o] = 0;
}
return;
}
fp(i, p + 1, r) {
const int v = a[dsu::Grt(i)];
if (!vs[v] && ps[o][v] < l) ++cc[bx[v]], vs[v] = 1;
}
int i = 1, j = 1;
for (; j <= Mx; ++i, j += T) {
const int t = sz[i] - rn[o][i].qry(l) - cc[i];
if (t >= k) break;
k -= t;
}
j = min(j, Mx + 1);
for (; k && j <= i * T && j <= Mx; ++j) {
const int t = b[j] - b[j - 1] - (vs[j] || ps[o][j] >= l);
if (t >= k) break;
k -= t;
}
FastIO::print(b[j - 1] + k, '\n');
fp(i, p + 1, r) {
const int v = a[dsu::Grt(i)];
cc[bx[v]] = vs[v] = 0;
}
}
int main() {
n = FastIO::read<int>(), m = FastIO::read<int>();
fp(i, 1, n) a[i] = FastIO::read<int>(), vst[a[i]] = 1;
fp(i, 1, m) {
q[i].op = FastIO::read<int>(), q[i].l = FastIO::read<int>(), q[i].r = FastIO::read<int>(), q[i].x = FastIO::read<int>();
if (q[i].op == 1)
q[i].y = FastIO::read<int>();
if (q[i].op == 1) {
if (vst.find(q[i].x) == vst.end())
in[i] = 1;
else
vst[q[i].y] = 1;
}
}
fp(i, 1, n) b[++Mx] = a[i];
fp(i, 1, m)(q[i].op == 1 && !in[i]) && (b[++Mx] = q[i].y);
sort(b + 1, b + 1 + Mx);
Mx = unique(b + 1, b + 1 + Mx) - b - 1;
B = (n - 1) / 60 + 1;
T = (Mx - 1) / 40 + 1;
fp(i, 1, n) bl[i] = (i - 1) / B + 1;
cb = bl[n];
fp(i, 1, cb) lp[i] = rp[i - 1] + 1, rp[i] = i * B;
rp[cb] = n;
fp(i, 1, Mx + T) bx[i] = (i - 1) / T + 1;
#define Gv(x) (lower_bound(b + 1, b + 1 + Mx, x) - b)
fp(i, 1, n) a[i] = Gv(a[i]);
for (int i = T, j = 1; i - T <= Mx; i += T, ++j) sz[j] = b[min(i, Mx)] - b[i - T];
dsu::init(n);
for (int i = B, o = 1; o <= cb; i += B, ++o) {
memcpy(ps[o], ps[o - 1], (Mx + 1) << 2);
fp(j, i - B + 1, min(i, n)) {
const int v = a[j];
ps[o][v] = j;
int& ro = pt[o][v];
if (!ro)
ro = j;
else
dsu::prt[j] = ro;
}
fp(j, 1, bx[Mx + T]) rn[o][j].c = cur, rn[o][j].lim = min(i, n), cur += rn[o][j].lim + 1;
for (int j = T, p = 1; j - T <= Mx; j += T, ++p) {
tn = 0;
fp(k, j - T + 1, j) if (ps[o][k]) stk[++tn] = ps[o][k];
rn[o][p].bld();
}
}
fp(i, 1, m) {
if (q[i].op == 1) {
if (!in[i]) mdy(q[i].l, q[i].r, Gv(q[i].x), Gv(q[i].y));
} else
qry(q[i].l, q[i].r, q[i].x);
}
return 0;
}