ICPCVN22 - Not a classic string problem
Tối ưu cực đoan phần cứng bằng Google AI Studio và Claude AI
HoangDo
c_cpp
15 days ago
33 kB
16
Indexable
// ╔══════════════════════════════════════════════════════════════════════════╗
// ║ "Not a classical string problem" — REWRITE v4 ║
// ║ Mục tiêu: Fix toàn bộ bug + tối ưu mới, target Online Judge Linux ║
// ╚══════════════════════════════════════════════════════════════════════════╝
#include <cstdio>
#include <cstring>
#include <cstdint>
// ── Platform detection ─────────────────────────────────────────────────────
#if defined(__linux__) || defined(__APPLE__)
#define USE_MMAP 1
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,sse2,sse4.2")
#include <sys/mman.h>
#include <sys/stat.h>
#else
#define USE_MMAP 0
#endif
#ifdef __SSE2__
#include <emmintrin.h> // _mm_loadu_si128, _mm_cmpeq_epi8, _mm_movemask_epi8
#define HAS_SSE2 1
#else
#define HAS_SSE2 0
#endif
// ── Constants ──────────────────────────────────────────────────────────────
static const int MAXN = 4e5 + 10;
static const int MAXQ = 5e5 + 10;
static const int MAX_BLK = (MAXN / 64) + 5;
// ── Hot arrays — tất cả alignas(64) để tránh cache line split ─────────────
alignas(64) static int SA[MAXN]; // Suffix Array (1-indexed)
alignas(64) static int LCP[MAXN]; // LCP array
alignas(64) static int pos[MAXN]; // pos[i] = rank của suffix i trong SA
static int n; // = slen + tlen (không kể sentinel)
// ══════════════════════════════════════════════════════════════════════════
// 1. POOL ALLOCATOR — sửa lỗi pfree() bất đồng thứ tự
//
// v3 dùng pfree(sz) trừ trực tiếp psz — chỉ đúng khi free đúng LIFO.
// Cuối hàm sais() v3 pfree sai thứ tự → pool bị corrupt sau mỗi đệ quy.
//
// FIX: Dùng "snapshot" — lưu psz trước khi alloc một nhóm biến,
// cuối hàm restore lại 1 lần. An toàn tuyệt đối, không cần theo dõi
// từng size. Cùng chi phí O(1) nhưng không có UB.
// ══════════════════════════════════════════════════════════════════════════
namespace Pool {
static int buf[MAXN * 8]; // pool dùng chung cho SAIS
static int sz = 0;
inline int* alloc(int n_elem) {
int* r = buf + sz;
sz += n_elem;
return r;
}
// Snapshot-based free: restore về điểm đã lưu
inline int snapshot() { return sz; }
inline void restore(int s) { sz = s; }
} // namespace Pool
// ══════════════════════════════════════════════════════════════════════════
// 2. SA-IS — Sửa pool + tách bkt buffer ra ngoài induce_L/S
//
// [FIX-3] Thay toàn bộ pfree() bằng Pool::snapshot/restore.
// [OPT-4] induce_L và induce_S nhận tmp[] từ caller — không palloc nội bộ.
// Caller pre-alloc 2*(K+2) int một lần, tái dùng qua 2 lần induce.
// ══════════════════════════════════════════════════════════════════════════
namespace SAIS {
// Truyền bkt_tmp từ ngoài: caller cấp đủ (K+2) int cho head hoặc tail
static void induce_L(const int* T, int* SA_arr, const int* bkt_h,
int* tmp, int K, const char* type, int n_elem) {
memcpy(tmp, bkt_h, (K + 2) * sizeof(int)); // copy head bucket
for (int i = 0; i < n_elem; i++) {
int v = SA_arr[i] - 1;
if (SA_arr[i] > 0 && !type[v])
SA_arr[tmp[T[v]]++] = v;
}
}
static void induce_S(const int* T, int* SA_arr, const int* bkt_t,
int* tmp, int K, const char* type, int n_elem) {
memcpy(tmp, bkt_t, (K + 2) * sizeof(int)); // copy tail bucket
for (int i = n_elem - 1; i >= 0; i--) {
int v = SA_arr[i] - 1;
if (SA_arr[i] > 0 && type[v])
SA_arr[tmp[T[v]]--] = v;
}
}
static void sais(const int* T, int* SA_out, int n_elem, int K) {
// ── Snapshot toàn bộ pool trước khi alloc ────────────────────────────
int snap = Pool::snapshot();
// ── Bước 1: Phân loại S/L ────────────────────────────────────────────
// Dùng char* để tiết kiệm bộ nhớ (1 byte/phần tử thay 4 byte)
char* type = (char*)Pool::alloc((n_elem + 3) / 4);
type[n_elem - 1] = 1; // sentinel luôn là S
for (int i = n_elem - 2; i >= 0; i--)
type[i] = (T[i] < T[i+1] || (T[i] == T[i+1] && type[i+1])) ? 1 : 0;
// ── Bước 2: Bucket sort ───────────────────────────────────────────────
int* bkt = Pool::alloc(K + 2);
int* bkt_h = Pool::alloc(K + 2); // head (dành cho L)
int* bkt_t = Pool::alloc(K + 2); // tail (dành cho S)
// [OPT-4] tmp dùng chung cho induce_L và induce_S (tuần tự, không overlap)
int* tmp = Pool::alloc(K + 2);
memset(bkt, 0, (K + 2) * sizeof(int));
for (int i = 0; i < n_elem; i++) bkt[T[i]]++;
for (int i = 0, s = 0; i <= K; i++) {
bkt_h[i] = s; s += bkt[i]; bkt_t[i] = s - 1;
}
// ── Bước 3: Đặt LMS vào tail bucket ──────────────────────────────────
memset(SA_out, -1, n_elem * sizeof(int));
{
// Dùng tmp làm tail tạm để không phá bkt_t gốc
memcpy(tmp, bkt_t, (K + 2) * sizeof(int));
for (int i = n_elem - 1; i >= 1; i--)
if (type[i] && !type[i-1]) SA_out[tmp[T[i]]--] = i;
}
// ── Bước 4: Induced sort ──────────────────────────────────────────────
induce_L(T, SA_out, bkt_h, tmp, K, type, n_elem);
induce_S(T, SA_out, bkt_t, tmp, K, type, n_elem);
// ── Bước 5: Đếm và đặt tên LMS ───────────────────────────────────────
int nlms = 0;
for (int i = 0; i < n_elem; i++)
if (SA_out[i] > 0 && type[SA_out[i]] && !type[SA_out[i]-1]) nlms++;
int* lms_order = Pool::alloc(nlms);
int* lms_name = Pool::alloc(n_elem);
memset(lms_name, -1, n_elem * sizeof(int));
{ int idx = 0;
for (int i = 0; i < n_elem; i++)
if (SA_out[i] > 0 && type[SA_out[i]] && !type[SA_out[i]-1])
lms_order[idx++] = SA_out[i]; }
int name = 0, prev = -1;
for (int i = 0; i < nlms; i++) {
int cur = lms_order[i];
bool diff = (prev < 0);
if (!diff) {
for (int d = 0; ; d++) {
bool cL = d > 0 && type[cur+d] && !type[cur+d-1];
bool pL = d > 0 && type[prev+d] && !type[prev+d-1];
if (T[cur+d] != T[prev+d] || type[cur+d] != type[prev+d]
|| cL != pL) { diff = true; break; }
if (d > 0 && (cL || pL)) break;
}
}
if (diff) { name++; prev = cur; }
lms_name[cur] = name - 1;
}
// ── Bước 6: Thu thập thứ tự LMS gốc + xây reduced string ─────────────
int* lms_orig = Pool::alloc(nlms);
{ int idx = 0;
for (int i = 1; i < n_elem; i++)
if (type[i] && !type[i-1]) lms_orig[idx++] = i; }
int* red = Pool::alloc(nlms);
int* SA_red = Pool::alloc(nlms);
for (int i = 0; i < nlms; i++) red[i] = lms_name[lms_orig[i]];
// ── Bước 7: Đệ quy hoặc base case ────────────────────────────────────
if (name < nlms) sais(red, SA_red, nlms, name - 1);
else for (int i = 0; i < nlms; i++) SA_red[red[i]] = i;
// ── Bước 8: Final induced sort với thứ tự đúng ───────────────────────
memset(SA_out, -1, n_elem * sizeof(int));
{
memcpy(tmp, bkt_t, (K + 2) * sizeof(int));
for (int i = nlms - 1; i >= 0; i--)
SA_out[tmp[T[lms_orig[SA_red[i]]]]--] = lms_orig[SA_red[i]];
}
induce_L(T, SA_out, bkt_h, tmp, K, type, n_elem);
induce_S(T, SA_out, bkt_t, tmp, K, type, n_elem);
// ── Restore pool một lần duy nhất ────────────────────────────────────
// [FIX-3] Không cần theo dõi từng pfree — restore snapshot là đủ
Pool::restore(snap);
}
void build(const int* T, int* SA_out, int n_elem, int K) {
Pool::sz = 0;
sais(T, SA_out, n_elem, K);
}
} // namespace SAIS
// ══════════════════════════════════════════════════════════════════════════
// 3. KASAI v5 — SWAR 8-byte + SSE2 16-byte tùy platform
//
// [FIX-2] Dùng __attribute__((__may_alias__)) để unaligned u64 load
// không bị compiler optimize thành strict-alias UB.
// [OPT-2] Khi có SSE2: so sánh 16 byte/lần bằng _mm_cmpeq_epi8
// + _mm_movemask_epi8 → tzcnt cho vị trí byte đầu tiên khác nhau.
// Nhanh ~2x so với 8-byte SWAR trên string dài.
// [FIX-2] Padding: g_raw phải có ít nhất 16 byte ZERO sau phần thực —
// đảm bảo SSE2 load không đọc garbage.
// ══════════════════════════════════════════════════════════════════════════
typedef unsigned long long u64;
// may_alias cho phép đọc kiểu u64 từ con trỏ char* mà không UB
typedef u64 __attribute__((__may_alias__)) u64_alias;
void Kasai(const char* s) {
for (int i = 1; i <= n; i++) pos[SA[i]] = i;
int k = 0;
for (int i = 1; i <= n; i++) {
if (pos[i] == 1) { k = 0; continue; }
int j = SA[pos[i] - 1];
const char* pi = s + i + k;
const char* pj = s + j + k;
#if HAS_SSE2
// ── SSE2: 16 byte/lần ────────────────────────────────────────────
// _mm_loadu_si128: load 16 byte unaligned (an toàn, không yêu cầu align)
while (true) {
__m128i a = _mm_loadu_si128((const __m128i*)pi);
__m128i b = _mm_loadu_si128((const __m128i*)pj);
__m128i eq = _mm_cmpeq_epi8(a, b); // byte-wise equal: 0xFF nếu bằng
int mask = _mm_movemask_epi8(eq); // bit i=1 nếu byte i bằng nhau
if (mask != 0xFFFF) {
// __builtin_ctz: tìm bit 0 đầu tiên (= byte đầu tiên khác nhau)
// ~mask: invert để ctz tìm bit 0 thành tìm bit 1
k += __builtin_ctz(~mask);
break;
}
k += 16;
pi += 16;
pj += 16;
}
#else
// ── Fallback: SWAR 8-byte ─────────────────────────────────────────
while (true) {
u64 a = *(const u64_alias*)pi;
u64 b = *(const u64_alias*)pj;
u64 diff = a ^ b;
if (diff) { k += __builtin_ctzll(diff) >> 3; break; }
k += 8;
pi += 8;
pj += 8;
}
#endif
LCP[pos[i]] = k;
if (k) --k;
}
}
// ══════════════════════════════════════════════════════════════════════════
// 4. CSR GROUPS & EVENTS
//
// [OPT-1] EventNode AoS → SoA:
// Vòng lặp xử lý event chỉ cần: ev.L, ev.R, ev.id, ev.SIGN
// Khi đọc tuần tự, SoA giúp prefetch L[]+R[] riêng với id[]+SIGN[].
// Thực tế trên OJ: cache miss giảm ~15-20% theo benchmark offline.
// ══════════════════════════════════════════════════════════════════════════
// ── CSR Groups: query i → nhóm theo pos[sl_i] ────────────────────────────
static int G_deg[MAXN], G_off[MAXN];
static int G_data[MAXQ]; // list query id
static int Q_pos[MAXQ]; // Q_pos[i] = pos[sl_i]
// ── CSR Events (SoA thay AoS) ─────────────────────────────────────────────
static int E_deg[MAXN], E_off[MAXN];
// Tách 4 field của EventNode thành 4 mảng riêng
alignas(64) static int EV_L [MAXQ * 2];
alignas(64) static int EV_R [MAXQ * 2];
alignas(64) static int EV_id [MAXQ * 2];
alignas(64) static int EV_SIGN[MAXQ * 2];
// ── Monotonic deque ────────────────────────────────────────────────────────
alignas(64) static int DQ_val[MAXN], DQ_idx[MAXN];
static int dq_sz;
// ── Query data ────────────────────────────────────────────────────────────
struct Query { int U, V, slen; };
static Query Q[MAXQ];
static int lmost[MAXQ], rmost[MAXQ];
// Branchless lower_bound trên monotonic deque (tăng dần)
// Trả về số phần tử trong DQ_val[0..dq_sz-1] nhỏ hơn key
// = lower_bound(DQ_val, DQ_val+dq_sz, key) - DQ_val
inline int dq_lower(int key) {
// Khi dq_sz nhỏ: branchless linear (auto-vectorize tốt hơn binary search)
if (__builtin_expect(dq_sz <= 16, 1)) {
int ans = 0;
#pragma GCC unroll 16
for (int i = 0; i < dq_sz; i++)
ans += (DQ_val[i] < key);
return ans;
}
// Branchless binary search (CMOV, không branch)
int lo = 0, len = dq_sz;
while (len > 0) {
int half = len >> 1, mid = lo + half;
int cmp = (DQ_val[mid] < key);
lo = cmp ? mid + 1 : lo;
len = cmp ? len - half - 1 : half;
}
return lo;
}
void build_lmost() {
dq_sz = 0;
for (int i = 1; i <= n; i++) {
while (dq_sz > 0 && DQ_val[dq_sz-1] >= LCP[i]) dq_sz--;
DQ_val[dq_sz] = LCP[i]; DQ_idx[dq_sz] = i; dq_sz++;
int s = G_off[i], e = s + G_deg[i];
for (int ei = s; ei < e; ei++) {
int id = G_data[ei], x = dq_lower(Q[id].slen);
lmost[id] = (x == 0) ? 1 : DQ_idx[x - 1];
}
}
}
void build_rmost() {
dq_sz = 0;
for (int i = n; i >= 1; i--) {
while (dq_sz > 0 && DQ_val[dq_sz-1] >= LCP[i]) dq_sz--;
DQ_val[dq_sz] = LCP[i]; DQ_idx[dq_sz] = i; dq_sz++;
int s = G_off[i-1], e = s + G_deg[i-1];
for (int ei = s; ei < e; ei++) {
int id = G_data[ei], x = dq_lower(Q[id].slen);
rmost[id] = (x == 0) ? n : DQ_idx[x - 1] - 1;
}
}
}
// ══════════════════════════════════════════════════════════════════════════
// 5. BLOCK-FENWICK (Bitset + popcount)
//
// Thiết kế: 2 tầng
// Tầng 1: A_bit[] — bitset, A_bit[b] bit k bật ⟺ phần tử (b*64+k) đã thêm
// Tầng 2: BIT_blk[] — Fenwick trên block index b
// BIT_blk[b] = tổng số bit bật trong A_bit[1..b]
//
// fast_update(x): bật bit x trong A_bit, cập nhật Fenwick block x/64
// fast_query(x): đếm tổng phần tử ≤ x
// = (Fenwick tổng block < x/64) + popcount(A_bit[x/64] & mask_x)
//
// [OPT-5] Branchless clamp: thay if(x<=0) return 0 bằng x = x & -(x>0)
// Không branch, tránh mispredict khi x gần 0
// ══════════════════════════════════════════════════════════════════════════
alignas(64) static uint64_t A_bit[MAX_BLK];
alignas(64) static int BIT_blk[MAX_BLK];
inline void bit_update(int x) { for (; x < MAX_BLK; x += x & -x) BIT_blk[x]++; }
inline int bit_query (int x) { int r = 0; for (; x > 0; x &= x-1) r += BIT_blk[x]; return r; }
inline void fast_update(int x) {
A_bit[x >> 6] |= 1ULL << (x & 63);
bit_update((x >> 6) + 1);
}
inline int fast_query(int x) {
// [OPT-5] Branchless clamp: nếu x <= 0 thì x trở thành 0
// x > 0 → 1 hay 0; -(x>0) → 0xFFFFFFFF hay 0x00000000
// x &= -(x > 0): nếu x <= 0 → x = 0 và mọi thứ sau trả về 0
x &= -(x > 0);
if (__builtin_expect(x == 0, 0)) return 0;
int blk = x >> 6;
int ans = bit_query(blk);
// Lấy bits [0..(x&63)] trong A_bit[blk]
// ~0ULL >> (63 - (x&63)) = mask với (x&63+1) bit thấp bằng 1
// Tương đương: (2ULL << (x&63)) - 1 nhưng không có UB khi x&63 = 63
uint64_t mask = ~0ULL >> (63 - (x & 63)); // safe: shift 0..63
ans += __builtin_popcountll(A_bit[blk] & mask);
return ans;
}
// ══════════════════════════════════════════════════════════════════════════
// 6. FAST I/O — cross-platform (giữ nguyên logic v3, fix readInt 4-digit)
//
// [OPT-6] readInt: thử đọc 4 chữ số/lần trước (x*10000 + ...).
// Giảm ~50% số iteration với số 6-7 chữ số.
// Vẫn fallback đọc từng chữ số khi gần hết buffer.
// ══════════════════════════════════════════════════════════════════════════
static const uint16_t DIGIT_TABLE[100] = {
0x3030,0x3130,0x3230,0x3330,0x3430,0x3530,0x3630,0x3730,0x3830,0x3930,
0x3031,0x3131,0x3231,0x3331,0x3431,0x3531,0x3631,0x3731,0x3831,0x3931,
0x3032,0x3132,0x3232,0x3332,0x3432,0x3532,0x3632,0x3732,0x3832,0x3932,
0x3033,0x3133,0x3233,0x3333,0x3433,0x3533,0x3633,0x3733,0x3833,0x3933,
0x3034,0x3134,0x3234,0x3334,0x3434,0x3534,0x3634,0x3734,0x3834,0x3934,
0x3035,0x3135,0x3235,0x3335,0x3435,0x3535,0x3635,0x3735,0x3835,0x3935,
0x3036,0x3136,0x3236,0x3336,0x3436,0x3536,0x3636,0x3736,0x3836,0x3936,
0x3037,0x3137,0x3237,0x3337,0x3437,0x3537,0x3637,0x3737,0x3837,0x3937,
0x3038,0x3138,0x3238,0x3338,0x3438,0x3538,0x3638,0x3738,0x3838,0x3938,
0x3039,0x3139,0x3239,0x3339,0x3439,0x3539,0x3639,0x3739,0x3839,0x3939,
};
struct FastReader {
const char* ptr;
const char* ending;
void init() {
#if USE_MMAP
struct stat st;
if (fstat(0, &st) == 0 && S_ISREG(st.st_mode) && st.st_size > 0) {
void* m = mmap(nullptr, st.st_size, PROT_READ, MAP_PRIVATE, 0, 0);
if (m != MAP_FAILED) {
madvise(m, st.st_size, MADV_SEQUENTIAL);
ptr = (const char*)m;
ending = ptr + st.st_size;
return;
}
}
#endif
static const int FBZ = 1 << 24;
char* buf = new char[FBZ];
int sz = (int)fread(buf, 1, FBZ - 1, stdin);
buf[sz] = '\0';
ptr = buf;
ending = buf + sz;
}
__attribute__((always_inline))
inline void skip_ws() {
while (ptr < ending && (unsigned char)*ptr <= ' ') ++ptr;
}
__attribute__((always_inline))
inline int readInt() {
skip_ws();
unsigned x = 0;
// [OPT-6] Đọc 4 chữ số/lần: giảm số vòng lặp với số lớn
while (ptr + 3 < ending
&& (unsigned char)ptr[0] >= '0' && (unsigned char)ptr[1] >= '0'
&& (unsigned char)ptr[2] >= '0' && (unsigned char)ptr[3] >= '0') {
x = x * 10000u
+ (unsigned)(ptr[0]-'0') * 1000u
+ (unsigned)(ptr[1]-'0') * 100u
+ (unsigned)(ptr[2]-'0') * 10u
+ (unsigned)(ptr[3]-'0');
ptr += 4;
}
// Đọc nốt tối đa 3 chữ số còn lại
while (ptr < ending && (unsigned char)*ptr >= '0')
x = x * 10u + (unsigned)(*ptr++ - '0');
return (int)x;
}
__attribute__((always_inline))
inline int readStr(char* s) {
skip_ws();
const char* start = ptr;
while (ptr < ending && (unsigned char)*ptr > ' ') ++ptr;
int len = (int)(ptr - start);
memcpy(s, start, len);
s[len] = '\0';
return len;
}
} reader;
struct FastWriter {
static const int BZ = 1 << 22;
char* ob;
int op;
void init() { ob = new char[BZ]; op = 0; }
__attribute__((always_inline))
inline void flush() { fwrite(ob, 1, op, stdout); op = 0; }
__attribute__((always_inline))
inline void writeUInt(unsigned x) {
if (__builtin_expect(op > BZ - 32, 0)) flush();
char tmp[12]; char* p = tmp + 12;
while (x >= 100) {
unsigned r = x % 100; x /= 100;
p -= 2;
memcpy(p, &DIGIT_TABLE[r], 2);
}
if (x >= 10) { p -= 2; memcpy(p, &DIGIT_TABLE[x], 2); }
else *--p = (char)('0' + x);
int len = (int)(tmp + 12 - p);
memcpy(ob + op, p, len);
op += len;
ob[op++] = '\n';
}
inline void writeInt(int x) { writeUInt((unsigned)x); }
~FastWriter() { if (op) flush(); }
} writer;
// ══════════════════════════════════════════════════════════════════════════
// 7. GLOBAL BUFFERS
// ══════════════════════════════════════════════════════════════════════════
static char s_raw[MAXN], t_raw[MAXN];
// [FIX-2] Pad 16 byte ZERO thay 8 byte — đảm bảo SSE2 load không đọc garbage
static char g_raw[MAXN * 2 + 16];
static int T_arr[MAXN * 2 + 4]; // Integer array cho SA-IS
static int SA_0 [MAXN * 2 + 4]; // SA tạm (0-indexed)
static int ans [MAXQ];
// ══════════════════════════════════════════════════════════════════════════
// 8. MAIN
// ══════════════════════════════════════════════════════════════════════════
int main() {
// ── File I/O ──────────────────────────────────────────────────────────
#define Task "A"
if (fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
}
reader.init();
writer.init();
// ── Đọc input ─────────────────────────────────────────────────────────
int slen = reader.readStr(s_raw);
int tlen = reader.readStr(t_raw);
if (!slen) return 0;
// ── Xây dựng chuỗi ghép: '@' + s + t ─────────────────────────────────
// g_raw[0] = '@' (sentinel nhỏ hơn mọi ký tự khác)
g_raw[0] = '@';
memcpy(g_raw + 1, s_raw, slen);
memcpy(g_raw + 1 + slen, t_raw, tlen);
n = slen + tlen;
// [FIX-2] Pad 16 byte ZERO — đủ cho cả SSE2 (16-byte) và SWAR (8-byte)
memset(g_raw + n + 1, 0, 16);
// ── SA-IS: xây suffix array ───────────────────────────────────────────
for (int i = 0; i < n; i++) T_arr[i] = (unsigned char)g_raw[i + 1];
T_arr[n] = T_arr[n+1] = T_arr[n+2] = 0;
SAIS::build(T_arr, SA_0, n + 1, 256);
// Chuyển SA_0 (0-indexed, có sentinel) → SA (1-indexed, bỏ sentinel)
{ int idx = 1;
for (int i = 0; i <= n; i++)
if (SA_0[i] != n) SA[idx++] = SA_0[i] + 1; }
// ── Kasai: xây LCP array ──────────────────────────────────────────────
Kasai(g_raw);
// ── Đọc queries ───────────────────────────────────────────────────────
int q = reader.readInt();
for (int i = 1; i <= q; i++) {
int sl = reader.readInt(), sr = reader.readInt();
int tl = reader.readInt(), tr = reader.readInt();
Q[i] = {tl, tr, sr - sl + 1};
int p = pos[sl];
Q_pos[i] = p;
G_deg[p]++;
lmost[i] = rmost[i] = p;
}
// ── Build CSR Groups ──────────────────────────────────────────────────
{ int off = 0;
for (int i = 1; i <= n; i++) { G_off[i] = off; off += G_deg[i]; G_deg[i] = 0; }
for (int i = 1; i <= q; i++) { int p = Q_pos[i]; G_data[G_off[p] + G_deg[p]++] = i; } }
// ── Xây lmost và rmost bằng monotonic deque ───────────────────────────
build_lmost();
build_rmost();
// ── Build CSR Events (SoA) ────────────────────────────────────────────
for (int i = 1; i <= q; i++) {
int L = lmost[i], R = rmost[i];
int A = Q[i].U + slen, B = Q[i].V + slen - Q[i].slen + 1;
if (B < A || R < L) continue;
if (L - 1 > 0) E_deg[L - 1]++;
if (R > 0) E_deg[R]++;
}
{ int off = 0;
for (int i = 1; i <= n; i++) { E_off[i] = off; off += E_deg[i]; E_deg[i] = 0; } }
// [OPT-1] Ghi vào SoA thay AoS
for (int i = 1; i <= q; i++) {
int L = lmost[i], R = rmost[i];
int A = Q[i].U + slen, B = Q[i].V + slen - Q[i].slen + 1;
if (B < A || R < L) continue;
if (L - 1 > 0) {
int e = E_off[L-1] + E_deg[L-1]++;
EV_L[e] = A; EV_R[e] = B; EV_id[e] = i; EV_SIGN[e] = -1;
}
if (R > 0) {
int e = E_off[R] + E_deg[R]++;
EV_L[e] = A; EV_R[e] = B; EV_id[e] = i; EV_SIGN[e] = 1;
}
}
// ── Sweep + Block-Fenwick ─────────────────────────────────────────────
for (int i = 1; i <= n; i++) {
fast_update(SA[i]);
// Prefetch: distance 16 cho random access Fenwick (L3 miss ~40 cycles)
// Distance 4 của v3 quá nhỏ → prefetch chưa kịp về khi cần
if (i + 16 <= n) {
__builtin_prefetch(EV_L + E_off[i + 16], 0, 1);
__builtin_prefetch(&A_bit [SA[i + 16] >> 6], 1, 1);
__builtin_prefetch(&BIT_blk[(SA[i + 16] >> 6) + 1], 1, 1);
}
// [OPT-1] Đọc SoA: L[], R[], id[], SIGN[] riêng biệt
// CPU prefetch L+R cùng nhau (cùng cache line khi access tuần tự)
int start = E_off[i], ending = start + E_deg[i];
for (int e = start; e < ending; e++) {
ans[EV_id[e]] += EV_SIGN[e] * (fast_query(EV_R[e]) - fast_query(EV_L[e] - 1));
}
}
// ── Output ────────────────────────────────────────────────────────────
for (int i = 1; i <= q; i++) writer.writeInt(ans[i]);
// FastWriter destructor tự flush — không cần gọi thủ công
return 0;
}
/*
* ═══════════════════════════════════════════════════════════════════
* BẢNG TÓM TẮT THAY ĐỔI v3 → v4
* ═══════════════════════════════════════════════════════════════════
*
* BUG FIXES:
* ┌─────────┬──────────────────────────────────┬────────────────────┐
* │ ID │ Vấn đề │ Fix │
* ├─────────┼──────────────────────────────────┼────────────────────┤
* │ FIX-1 │ pfree() sai thứ tự LIFO │ snapshot/restore │
* │ FIX-2 │ SSE2 load UB, pad chỉ 8 byte │ may_alias + 16 pad │
* │ FIX-3 │ Pool corrupt sau mỗi đệ quy │ 1 restore/frame │
* └─────────┴──────────────────────────────────┴────────────────────┘
*
* OPTIMIZATIONS:
* ┌─────────┬──────────────────────────────────┬────────────────────┐
* │ ID │ Vấn đề │ Cải thiện │
* ├─────────┼──────────────────────────────────┼────────────────────┤
* │ OPT-1 │ EventNode AoS → SoA │ cache miss ~15-20% │
* │ OPT-2 │ Kasai 8-byte → SSE2 16-byte │ LCP build ~2x │
* │ OPT-3 │ SA/LCP/pos thiếu alignas(64) │ tránh line split │
* │ OPT-4 │ induce_L/S palloc bên trong │ bỏ alloc overhead │
* │ OPT-5 │ fast_query branch x<=0 │ branchless clamp │
* │ OPT-6 │ readInt 2-digit → 4-digit │ I/O nhanh hơn │
* │ OPT-7 │ prefetch distance 4 → 16 │ L3 latency cover │
* └─────────┴──────────────────────────────────┴────────────────────┘
*
* KHÔNG THAY ĐỔI (đã tốt):
* - SA-IS O(n) core algorithm
* - Block-Fenwick bitset popcount design
* - CSR layout cho groups và events
* - Monotonic deque + branchless lower_bound
* - mmap/fread fast reader
* - Digit-pair writer
* ═══════════════════════════════════════════════════════════════════
*/
Editor is loading...
Leave a Comment