結果
| 問題 |
No.3251 kthmex
|
| コンテスト | |
| ユーザー |
 jiangxinyang
|
| 提出日時 | 2025-08-07 00:19:46 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 9,574 bytes |
| コンパイル時間 | 4,177 ms |
| コンパイル使用メモリ | 254,280 KB |
| 実行使用メモリ | 80,460 KB |
| 最終ジャッジ日時 | 2025-08-07 00:32:53 |
| 合計ジャッジ時間 | 31,957 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 29 TLE * 1 -- * 2 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:250:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
250 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:251:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
251 | fp(i, 1, n) scanf("%d", &a[i]), vst[a[i]] = 1;
| ~~~~~^~~~~~~~~~~~~
main.cpp:253:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
253 | scanf("%d%d%d%d", &q[i].op, &q[i].l, &q[i].r, &q[i].x);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:255:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
255 | scanf("%d", &q[i].y);
| ~~~~~^~~~~~~~~~~~~~~
ソースコード
#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;
}
const int maxn = 1e5 + 10, maxm = 2e5 + 10, mod = 998244353;
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];
map<int, bool> vst;
int ps[35][maxm], rt[35][55], pt[35][maxm];
namespace dsu {
int prt[maxn];
inline void init(int n) {
fp(i, 1, n) prt[i] = i;
}
inline int Grt(int x) {
if (x ^ prt[x]) return prt[x] = Grt(prt[x]);
return x;
}
} // namespace dsu
int ft[maxn << 1], ct, sz[55], stk[maxn], tn;
constexpr double alp = 0.7;
constexpr int G = (1 << 30) - 1;
struct Scpt {
struct scpt {
int ls, rs, sz, rz, v;
} t[maxn << 1];
int rb[maxn << 1], rc, tot;
inline void New(int& x, const int y) {
t[x = rc ? rb[rc--] : ++tot] = (scpt){0, 0, 1, 1, y | (1 << 30)};
}
inline void upd(const int x) {
t[x].sz = t[t[x].ls].sz + t[t[x].rs].sz + 1;
t[x].rz = t[t[x].ls].rz + t[t[x].rs].rz + (t[x].v >> 30);
}
inline void flt(const int x) {
if (!x) return;
flt(t[x].ls);
if (t[x].v >> 30)
ft[++ct] = x;
else
rb[++rc] = x;
flt(t[x].rs);
}
inline int rbd(const int l, const int r) {
if (l == r) return 0;
int mid = l + r >> 1, x = ft[mid];
t[x].ls = rbd(l, mid);
t[x].rs = rbd(mid + 1, r);
return upd(x), x;
}
inline void rbd(int& x) {
ct = 0;
flt(x);
x = rbd(1, ct + 1);
}
inline bool nbd(const int x) {
return (t[x].v >> 30) &&
((t[x].sz * alp < max(t[t[x].ls].sz, t[t[x].rs].sz)) || t[x].rz < t[x].sz * alp);
}
inline void insert(int& x, const int y) {
if (!x) return New(x, y);
const int o = t[x].v & G;
if (o == y)
t[x].v |= 1 << 30;
else
insert(o < y ? t[x].rs : t[x].ls, y);
upd(x);
if (nbd(x)) rbd(x);
}
inline void erase(int& x, const int y) {
if (!x) return;
--t[x].rz;
const int o = t[x].v & G;
if (o == y)
t[x].v -= 1 << 30;
else
erase(o < y ? t[x].rs : t[x].ls, y);
upd(x);
if (nbd(x)) rbd(x);
}
inline int qry(const int x, const int y) {
if (!x) return 0;
const int o = (t[x].v & G);
if (o == y) return t[t[x].rs].rz + (t[x].v >> 30);
return o > y ? ((t[x].rz - t[t[x].ls].rz) + qry(t[x].ls, y)) : qry(t[x].rs, y);
}
inline void bld(int& x) {
sort(stk + 1, stk + 1 + tn);
ct = tn;
fp(i, 1, tn) New(ft[i], stk[i]);
x = rbd(1, ct + 1);
}
};
Scpt rn[35];
int cc[55], 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].erase(rt[o][vx], tx), rn[o].insert(rt[o][vx], ps[o][x]);
if (ty ^ ps[o][y]) rn[o].erase(rt[o][vy], ty), rn[o].insert(rt[o][vy], 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].erase(rt[i][vx], ps[i][x]);
ps[i][x] = px;
if (px) rn[i].insert(rt[i][vx], px);
}
if (py && (!ps[i][y] || ps[i][y] < py)) {
if (ps[i][y]) rn[i].erase(rt[i][vy], ps[i][y]);
ps[i][y] = py;
rn[i].insert(rt[i][vy], 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].erase(rt[i][vx], ps[i][x]);
ps[i][x] = ps[i - 1][x];
if (ps[i][x]) rn[i].insert(rt[i][vx], ps[i][x]);
}
if (ps[i][y] ^ ps[i - 1][y]) {
if (!pt[i][y]) {
if (ps[i][y]) rn[i].erase(rt[i][vy], ps[i][y]);
ps[i][y] = ps[i - 1][y];
if (ps[i][y]) rn[i].insert(rt[i][vy], 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].erase(rt[i][vx], ps[i][x]);
if (!ps[i][y] || (ps[i][y] < ps[i][x])) {
if (ps[i][y]) rn[i].erase(rt[i][vy], ps[i][y]);
ps[i][y] = ps[i][x];
if (ps[i][y]) rn[i].insert(rt[i][vy], ps[i][y]);
}
ps[i][x] = ps[i - 1][x];
if (ps[i][x]) rn[i].insert(rt[i][vx], 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].erase(rt[i][vx], ps[i][x]);
ps[i][x] = px;
if (px) rn[i].insert(rt[i][vx], px);
}
if (py && (!ps[i][y] || ps[i][y] < py)) {
if (ps[i][y]) rn[i].erase(rt[i][vy], ps[i][y]);
ps[i][y] = py;
if (py) rn[i].insert(rt[i][vy], 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;
}
printf("%d\n", b[j - 1] + k);
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].qry(rt[o][i], 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;
}
printf("%d\n", b[j - 1] + k);
fp(i, p + 1, r) {
const int v = a[dsu::Grt(i)];
cc[bx[v]] = vs[v] = 0;
}
}
int main() {
scanf("%d%d", &n, &m);
fp(i, 1, n) scanf("%d", &a[i]), vst[a[i]] = 1;
fp(i, 1, m) {
scanf("%d%d%d%d", &q[i].op, &q[i].l, &q[i].r, &q[i].x);
if (q[i].op == 1)
scanf("%d", &q[i].y);
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) / 20 + 1;
T = (Mx - 1) / 20 + 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;
}
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].bld(rt[o][p]);
}
}
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;
}