WA on Test3,提交记录,报错信息为 Too short on line 676
,马蜂清奇,见谅
#include<bits/stdc++.h>
using namespace std;
static int T;
#define reg register
#define _ 7
#define __ 2000007
#define ___ 0x3f3f3f3f
#define pb emplace_back
#define sz(x) ((int)(x.size()))
#define mem(a,x) memset(a,x,sizeof(a))
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define endl '\n'
#define debug cerr<<"LINE: "<<__LINE__<<endl
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
#define int long long
const int M = 998244353, M1 = 1e9 + 7, M2 = 1e9 + 9, N = (1 << 21) + 7, inf = 0x3f3f3f3f;
using ll = long long;
using ull = unsigned long long;
using vt = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tll = __int128_t;
using db = double;
struct dat {
int l, r, val, id, t;
} q[__], qr[__];
int n, m, bl[__], siz, tot[__], pos[__], curq, curr, nx, ans[__];
unordered_map<int, int>mp;
inline bool cmp(dat a, dat b) {
return (bl[a.l] == bl[b.l] ? (bl[a.r] == bl[b.r] ? (bl[a.r] & 1 ? a.t > b.t : a.t < b.t) : (bl[a.l] & 1 ? bl[a.r] > bl[b.r] : bl[a.r] < bl[b.r])) : a.l < b.l);
}
inline void update(int x, int y) {
if (q[x].l <= qr[y].l && qr[y].l <= q[x].r) ++tot[qr[y].r], --tot[pos[qr[y].l]];
swap(pos[qr[y].l], qr[y].r);
}
signed main() {
#ifdef Zyhx
freopen("hack.in", "r", stdin);
#endif
ios::sync_with_stdio(0), cin.tie(0);
int i, j, k, l, r, x, y, z, t;
cin >> n >> m;
siz = pow(n, 0.666666);
for (i = 1; i <= n; ++i) {
cin >> pos[i];
if (!mp[pos[i]]) mp[pos[i]] = ++nx;
pos[i] = mp[pos[i]], bl[i] = (i - 1) / siz + 1;
}
for (i = 1; i <= n; ++i) {
char opt;
cin >> opt;
if (opt == 'Q') {
cin >> x >> y >> z;
if (!mp[z]) mp[z] = ++nx;
q[++curq].l = x, q[curq].r = y, q[curq].val = mp[z], q[curq].id = curq, q[curq].t = curr;
} else {
cin >> x >> y;
if (!mp[y]) mp[y] = ++nx;
qr[++curr].l = x, qr[curr].r = mp[y];
}
}
stable_sort(q + 1, q + curq + 1, cmp);
for (i = l = 1, r = t = 0; i <= curq; ++i) {
for (; r < q[i].r; tot[pos[++r]]++);
for (; r > q[i].r; --tot[pos[r--]]);
for (; l < q[i].l; --tot[pos[l++]]);
for (; l > q[i].l; tot[pos[--l]]++);
for (; t < q[i].t; update(i, ++t));
for (; t > q[i].t; update(i, t--));
ans[q[i].id] = tot[q[i].val];
}
for (i = 1; i <= curq; ++i) cout << ans[i] << endl;
return 0;
}