代码

// noi17a 【NOI2017】整数  -- fully lazy 3-level hierarchy over 64-bit words
//
// x is a bit vector of NW 64-bit words.
//   level A1[e] : bit i  <=> word (64e+i) is all-ones (o) / all-zeros (z)
//   level A2[u] : bit j  <=> entry (64u+j) is all-ones / all-zeros
//   level A3   : bit u   <=> unit u is all-ones / all-zeros
// A bit set at a level means "the whole subtree is uniform"; the arrays below it
// may be stale.  Any op that descends into a lazily-marked node first expands
// the mark into the child level (O(1) qword writes).
#pragma GCC target("avx2,popcnt,sse4.2,ssse3")
#include <immintrin.h>

typedef unsigned long long u64;
typedef unsigned int u32;
typedef long long i64;

#ifdef TEST_IO
#include <cstdio>
#include <cstring>
#include <cstdlib>
static const char *IN; static u64 INSZ; static char *OUT; static u64 OUTSZ = 0; static u64 OUTLIM = 1u<<28;
#else
struct DI { u64 abi; const char*in; u64 insz; char*out; u64 outlim; u64 outsz; char*err;
            u64 errlim; u64 errsz; const char*IB; u64 IBlim; char*OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));
#define DUCKINFO 0x243FFF90ULL
static struct DI *di;
static const char *IN; static u64 INSZ; static char *OUT; static u64 OUTSZ = 0; static u64 OUTLIM;
#endif

static const int NW  = 471040;          // words (multiple of 4096), 30e6+64 bits needed
static const int NE  = NW >> 6;         // 7360 entries
static const int NU  = NE >> 6;         // 115 units
static const int NU3 = (NU + 63) >> 6;  // 2 qwords of A3

static u64 W[NW];
static u64 A1o[NE], A1z[NE];
static u64 A2o[NU], A2z[NU];
static u64 A3o[NU3], A3z[NU3];

static inline unsigned ctz64(u64 x) { return (unsigned)__builtin_ctzll(x); }

// ---- expansion of lazy marks (each O(1)) ----
static inline void matUnit(int u) {
    int h = u >> 6; u64 b = 1ULL << (u & 63);
    if (A3o[h] & b)      { A2o[u] = ~0ULL; A2z[u] = 0; A3o[h] &= ~b; }
    else if (A3z[h] & b) { A2z[u] = ~0ULL; A2o[u] = 0; A3z[h] &= ~b; }
}
static inline void matEntry(int e) {
    int u = e >> 6; u64 b = 1ULL << (e & 63);
    if (A2o[u] & b)      { A1o[e] = ~0ULL; A1z[e] = 0; A2o[u] &= ~b; }
    else if (A2z[u] & b) { A1z[e] = ~0ULL; A1o[e] = 0; A2z[u] &= ~b; }
}
static inline void pullEntry(int e) {
    int u = e >> 6; u64 b = 1ULL << (e & 63);
    if (A1o[e] == ~0ULL) A2o[u] |= b; else A2o[u] &= ~b;
    if (A1z[e] == ~0ULL) A2z[u] |= b; else A2z[u] &= ~b;
}
static inline void pullUnit(int u) {
    int h = u >> 6; u64 b = 1ULL << (u & 63);
    if (A2o[u] == ~0ULL) A3o[h] |= b; else A3o[h] &= ~b;
    if (A2z[u] == ~0ULL) A3z[h] |= b; else A3z[h] &= ~b;
}

// ---- scalar access ----

// ---------------- deferred uniform-region overlay cache ----------------
// When active, words [cL,cR) all equal cV; the tree is stale inside but exact
// outside, and the marks of nodes that STRADDLE the region are forced "mixed"
// so that any descent inside them is resolved word by word (results landing in
// the region are re-resolved through the cache).
static int cOn = 0, cL = 0, cR = 0;
static u64 cV = 0;
static int stU0 = -1, stU1 = -1, stE0 = -1, stE1 = -1;
static void flushC(void);
static inline void setCache(int l, int r, u64 v) {
    cOn = 1; cL = l; cR = r; cV = v;
    int uA = l >> 12, uB = (r - 1) >> 12;
    stU0 = (l & 4095) ? uA : -1;
    stU1 = (r & 4095) ? uB : -1;
    if (stU0 >= 0) { int h = stU0 >> 6; u64 b = 1ULL << (stU0 & 63); A3o[h] &= ~b; A3z[h] &= ~b; }
    if (stU1 >= 0 && stU1 != stU0) { int h = stU1 >> 6; u64 b = 1ULL << (stU1 & 63); A3o[h] &= ~b; A3z[h] &= ~b; }
    int eA = l >> 6, eB = (r - 1) >> 6;
    stE0 = (l & 63) ? eA : -1;
    stE1 = (r & 63) ? eB : -1;
    if (stE0 >= 0) { int u = stE0 >> 6; u64 b = 1ULL << (stE0 & 63); A2o[u] &= ~b; A2z[u] &= ~b; }
    if (stE1 >= 0 && stE1 != stE0) { int u = stE1 >> 6; u64 b = 1ULL << (stE1 & 63); A2o[u] &= ~b; A2z[u] &= ~b; }
}

static inline u64 getWord(int w) {
    if (cOn && (unsigned)(w - cL) < (unsigned)(cR - cL)) return cV;
    int u = w >> 12, h = u >> 6;
    u64 ub = 1ULL << (u & 63);
    if (A3o[h] & ub) return ~0ULL;
    if (A3z[h] & ub) return 0;
    u64 eb = 1ULL << ((w >> 6) & 63);
    if (A2o[u] & eb) return ~0ULL;
    if (A2z[u] & eb) return 0;
    int e = w >> 6; u64 b = 1ULL << (w & 63);
    if (A1o[e] & b) return ~0ULL;
    if (A1z[e] & b) return 0;
    return W[w];
}
static inline void putWord(int w, u64 v) {
    if (cOn && (unsigned)(w - cL) < (unsigned)(cR - cL)) flushC();
    int e = w >> 6, u = e >> 6, h = u >> 6;
    u64 ub = 1ULL << (u & 63), eb = 1ULL << (e & 63);
    if (A3o[h] & ub)      { A2o[u] = ~0ULL; A2z[u] = 0; A3o[h] &= ~ub; }
    else if (A3z[h] & ub) { A2z[u] = ~0ULL; A2o[u] = 0; A3z[h] &= ~ub; }
    if (A2o[u] & eb)      { A1o[e] = ~0ULL; A1z[e] = 0; A2o[u] &= ~eb; }
    else if (A2z[u] & eb) { A1z[e] = ~0ULL; A1o[e] = 0; A2z[u] &= ~eb; }
    W[w] = v;
    u64 b = 1ULL << (w & 63);
    u64 o = A1o[e], z = A1z[e];
    int wasF = (o == ~0ULL), wasZ = (z == ~0ULL);
    if (v == ~0ULL)      { o |= b;  z &= ~b; }
    else if (v == 0)     { z |= b;  o &= ~b; }
    else                 { o &= ~b; z &= ~b; }
    A1o[e] = o; A1z[e] = z;
    int nowF = (o == ~0ULL), nowZ = (z == ~0ULL);
    if (nowF != wasF || nowZ != wasZ) {
        if (nowF) A2o[u] |= eb; else A2o[u] &= ~eb;
        if (nowZ) A2z[u] |= eb; else A2z[u] &= ~eb;
        pullUnit(u);
    }
}

// ---- range fill on the word level (fully lazy) ----
static inline void setWordBits(int e, int lo, int hi, u64 val) {   // [lo,hi) within entry
    u64 m = (~0ULL << lo) & (~0ULL >> (64 - hi));
    if (val) { A1o[e] |= m; A1z[e] &= ~m; }
    else     { A1z[e] |= m; A1o[e] &= ~m; }
}
static inline void setEntryMarks(int u, int a, int b, u64 val) {   // entries [a,b) in unit u
    u64 m = (~0ULL << a) & (~0ULL >> (64 - b));
    if (val) { A2o[u] |= m; A2z[u] &= ~m; }
    else     { A2z[u] |= m; A2o[u] &= ~m; }
}
static inline void setUnitMarks(int a, int b, u64 val) {           // units [a,b)
    int h0 = a >> 6, h1 = (b - 1) >> 6;
    u64 m0 = ~0ULL << (a & 63), m1 = ~0ULL >> (63 - ((b - 1) & 63));
    if (h0 == h1) {
        u64 m = m0 & m1;
        if (val) { A3o[h0] |= m; A3z[h0] &= ~m; }
        else     { A3z[h0] |= m; A3o[h0] &= ~m; }
        return;
    }
    if (val) { A3o[h0] |= m0; A3z[h0] &= ~m0; } else { A3z[h0] |= m0; A3o[h0] &= ~m0; }
    for (int h = h0 + 1; h < h1; h++) { if (val) { A3o[h] = ~0ULL; A3z[h] = 0; } else { A3z[h] = ~0ULL; A3o[h] = 0; } }
    if (val) { A3o[h1] |= m1; A3z[h1] &= ~m1; } else { A3z[h1] |= m1; A3o[h1] &= ~m1; }
}
static inline void assignInUnit(int u, int l, int r, u64 val) {    // words [l,r) inside unit u
    int e0 = l >> 6, eF = r >> 6, eL = (r - 1) >> 6;
    if (e0 == eL) {
        matEntry(e0); setWordBits(e0, l & 63, r - (e0 << 6), val); pullEntry(e0);
        return;
    }
    if (l & 63) {
        matEntry(e0); setWordBits(e0, l & 63, 64, val); pullEntry(e0);
        e0++;
    }
    if (e0 < eF) setEntryMarks(u, e0 - (u << 6), eF - (u << 6), val);
    if (r & 63) {
        int e = r >> 6;
        matEntry(e); setWordBits(e, 0, r & 63, val); pullEntry(e);
    }
}
static inline void treeAssignWords(int l, int r, u64 val) {
    if (l >= r) return;
    int u0 = l >> 12, u1 = (r - 1) >> 12;
    if (u0 == u1) { matUnit(u0); assignInUnit(u0, l, r, val); pullUnit(u0); return; }
    matUnit(u0); assignInUnit(u0, l, (u0 + 1) << 12, val); pullUnit(u0);
    if (u0 + 1 < u1) setUnitMarks(u0 + 1, u1, val);
    matUnit(u1); assignInUnit(u1, u1 << 12, r, val); pullUnit(u1);
}

static void flushC(void) {
    if (!cOn) return;
    cOn = 0;
    treeAssignWords(cL, cR, cV);
}
static inline void assignWords(int l, int r, u64 val) {
    if (l >= r) return;
    if (cOn) {
        if (l == cL && r == cR) { cV = val; return; }        // same region: flip in place
        if (cL <= l && r <= cR) {
            if (val == cV) return;
            flushC();
        } else if (l <= cL && cR <= r) {
            setCache(l, r, val);
            return;
        } else {
            flushC();
        }
    }
    if (r - l >= 512) setCache(l, r, val);
    else treeAssignWords(l, r, val);
}
// ---- first word >= k which is not all-ones / not all-zeros ----
static inline int treeFindNonFull(int k) {
    int u = k >> 12, e = k >> 6;
    int h = u >> 6; u64 ub = 1ULL << (u & 63);
    if (!(A3o[h] & ub)) {
        if (A3z[h] & ub) return k;
        u64 m = ~A2o[u] & (~0ULL << (e & 63));
        if (m) {
            int e2 = (u << 6) + ctz64(m);
            if (e2 == e) {
                if (A2z[u] & (1ULL << (e & 63))) return k;
                u64 mm = ~A1o[e] & (~0ULL << (k & 63));
                if (mm) return (e << 6) + ctz64(mm);
                m &= m - 1;
                if (m) { e2 = (u << 6) + ctz64(m); }
                else goto later;
            }
            if (A2z[u] & (1ULL << (e2 & 63))) return e2 << 6;
            return (e2 << 6) + ctz64(~A1o[e2]);
        }
    }
later:
    {
        u64 um = ~A3o[h] & (~0ULL << ((u + 1) & 63));
        int uu;
        if (um) uu = (h << 6) + ctz64(um);
        else if (h + 1 < NU3 && (um = ~A3o[h + 1]) != 0) uu = ((h + 1) << 6) + ctz64(um);
        else return NW;
        if (A3z[uu >> 6] & (1ULL << (uu & 63))) return uu << 12;
        u64 m = ~A2o[uu];
        int e2 = (uu << 6) + ctz64(m);
        if (A2z[uu] & (1ULL << (e2 & 63))) return e2 << 6;
        return (e2 << 6) + ctz64(~A1o[e2]);
    }
}
static inline int treeFindNonZero(int k) {
    int u = k >> 12, e = k >> 6;
    int h = u >> 6; u64 ub = 1ULL << (u & 63);
    if (!(A3z[h] & ub)) {
        if (A3o[h] & ub) return k;
        u64 m = ~A2z[u] & (~0ULL << (e & 63));
        if (m) {
            int e2 = (u << 6) + ctz64(m);
            if (e2 == e) {
                if (A2o[u] & (1ULL << (e & 63))) return k;
                u64 mm = ~A1z[e] & (~0ULL << (k & 63));
                if (mm) return (e << 6) + ctz64(mm);
                m &= m - 1;
                if (m) { e2 = (u << 6) + ctz64(m); }
                else goto later;
            }
            if (A2o[u] & (1ULL << (e2 & 63))) return e2 << 6;
            return (e2 << 6) + ctz64(~A1z[e2]);
        }
    }
later:
    {
        u64 um = ~A3z[h] & (~0ULL << ((u + 1) & 63));
        int uu;
        if (um) uu = (h << 6) + ctz64(um);
        else if (h + 1 < NU3 && (um = ~A3z[h + 1]) != 0) uu = ((h + 1) << 6) + ctz64(um);
        else return NW;
        if (A3o[uu >> 6] & (1ULL << (uu & 63))) return uu << 12;
        u64 m = ~A2z[uu];
        int e2 = (uu << 6) + ctz64(m);
        if (A2o[uu] & (1ULL << (e2 & 63))) return e2 << 6;
        return (e2 << 6) + ctz64(~A1z[e2]);
    }
}

// ---- the two update primitives ----
static inline int findNonFull(int k) {
    if (cOn && k < cR) {
        if (k < cL) {
            int t = treeFindNonFull(k);
            if (t < cL) return t;
        }
        if (cV == 0) return k > cL ? k : cL;
        k = cR;
    }
    return treeFindNonFull(k);
}
static inline int findNonZero(int k) {
    if (cOn && k < cR) {
        if (k < cL) {
            int t = treeFindNonZero(k);
            if (t < cL) return t;
        }
        if (cV == ~0ULL) return k > cL ? k : cL;
        k = cR;
    }
    return treeFindNonZero(k);
}

static inline void addAtWord(int k, u64 v) {
    u64 cur = getWord(k);
    u64 t = cur + v;
    putWord(k, t);
    if (t < cur) {
        int j = findNonFull(k + 1);
        assignWords(k + 1, j, 0);
        putWord(j, getWord(j) + 1);
    }
}
static inline void subAtWord(int k, u64 v) {
    u64 cur = getWord(k);
    u64 t = cur - v;
    putWord(k, t);
    if (cur < v) {
        int j = findNonZero(k + 1);
        assignWords(k + 1, j, ~0ULL);
        putWord(j, getWord(j) - 1);
    }
}

// ---- input parsing (SSE, 8 digits at a time) ----
static const u64 POW10[9] = {1,10,100,1000,10000,100000,1000000,10000000,100000000};
static inline u64 parseU(const char *& p, const char *pend) {
    u64 v = 0;
    if (p + 16 <= pend) {
        for (;;) {
            __m128i x = _mm_loadl_epi64((const __m128i *)p);
            x = _mm_sub_epi8(x, _mm_set1_epi8('0'));
            __m128i ok = _mm_cmpeq_epi8(_mm_min_epu8(x, _mm_set1_epi8(9)), x);
            unsigned m = (unsigned)_mm_movemask_epi8(ok) & 0xFFu;
            int len = ctz64((u64)(~m | 0x100u));
            x = _mm_and_si128(x, ok);
            x = _mm_sll_epi64(x, _mm_cvtsi32_si128(8 * (8 - len)));
            __m128i t = _mm_maddubs_epi16(x, _mm_set1_epi16(0x010A));
            t = _mm_madd_epi16(t, _mm_set1_epi32(0x00010064));
            t = _mm_packus_epi32(t, t);
            t = _mm_madd_epi16(t, _mm_set1_epi32(0x00012710));
            v = v * POW10[len] + (u64)(unsigned)_mm_cvtsi128_si32(t);
            p += len;
            if (len < 8) return v;
            if (p + 16 > pend) break;
        }
    }
    while (p < pend && *p >= '0' && *p <= '9') v = v * 10 + (u64)(*p++ - '0');
    return v;
}


// ---- whole-line parser: one 32B load gives the field boundaries ----
static inline u64 convF(const char *q, int L) {   // 1 <= L <= 8
    u64 x; __builtin_memcpy(&x, q, 8);
    u64 d = x - 0x3030303030303030ULL;
    d <<= (8 - L) << 3;
    u64 t = (d * 10 + (d >> 8)) & 0x00FF00FF00FF00FFULL;
    t = (t * 100 + (t >> 16)) & 0x0000FFFF0000FFFFULL;
    t = (t * 10000 + (t >> 32)) & 0xFFFFFFFFULL;
    return t;
}
static inline u64 convN(const char *q, int L) {   // 1 <= L <= 16
    if (L <= 8) {
        if (__builtin_expect(L <= 2, 0)) {
            if (L == 1) return (u64)(q[0] - '0');
            return (u64)((q[0] - '0') * 10 + (q[1] - '0'));
        }
        return convF(q, L);
    }
    int L2 = L - 8;
    return convF(q, 8) * POW10[L2] + convF(q + 8, L2);
}

int main() {
#ifdef TEST_IO
    static char inbuf[1 << 26];
    INSZ = fread(inbuf, 1, sizeof(inbuf), stdin);
    IN = inbuf;
    static char outbuf[1 << 24];
    OUT = outbuf; OUTLIM = sizeof(outbuf);
#else
    di = (struct DI *)DUCKINFO;
    IN = di->in; INSZ = di->insz;
    OUT = di->out; OUTLIM = di->outlim;
#endif
    for (int e = 0; e < NE; e++) { A1o[e] = 0; A1z[e] = ~0ULL; }
    for (int u = 0; u < NU; u++) { A2o[u] = 0; A2z[u] = ~0ULL; }
    for (int h = 0; h < NU3; h++) { A3o[h] = 0; A3z[h] = ~0ULL; }
    // trim the tail bits of the last A3 word (units NU..63 of that word unused)
    if (NU & 63) A3z[NU3 - 1] = (1ULL << (NU & 63)) - 1;

    const char *p = IN, *pend = IN + INSZ;
    u64 n = parseU(p, pend);
    while (p < pend && *p != '\n') p++;
    p++;
    char *o = OUT;
    char *olim = OUT + (OUTLIM > 4 ? OUTLIM - 4 : 0);
    const char *win = p;
    u64 wmask = 0;
    for (u64 op = 0; op < n; op++) {
        if (__builtin_expect(wmask == 0, 0)) {
            if (p > pend - 128) { wmask = 0; goto slowpath; }
            win = p;
            __m256i w0 = _mm256_loadu_si256((const __m256i *)win);
            __m256i w1 = _mm256_loadu_si256((const __m256i *)(win + 32));
            __m256i nl = _mm256_set1_epi8('\n');
            u64 m0 = (unsigned)_mm256_movemask_epi8(_mm256_cmpeq_epi8(w0, nl));
            u64 m1 = (unsigned)_mm256_movemask_epi8(_mm256_cmpeq_epi8(w1, nl));
            wmask = m0 | (m1 << 32);
            if (!wmask) goto slowpath;
        }
        if (__builtin_expect(wmask != 0, 1)) {
            int nloff = __builtin_ctzll(wmask);
            int nlp = (int)((win + nloff) - p);
            if (__builtin_expect(nlp < 32, 1)) {
            __m256i v = _mm256_loadu_si256((const __m256i *)p);
            __m256i dv = _mm256_sub_epi8(v, _mm256_set1_epi8('0'));
            unsigned dm = (unsigned)_mm256_movemask_epi8(_mm256_cmpeq_epi8(_mm256_min_epu8(dv, _mm256_set1_epi8(9)), dv));
            {
                unsigned nd = (~dm) & ((1u << nlp) - 1);
                unsigned n1 = nd & (nd - 1);
                if (*p == '1') {
                    int neg = 0;
                    if (n1 && __builtin_ctz(n1) == __builtin_ctz(nd) + 1) { neg = 1; n1 &= n1 - 1; }
                    if (n1 && (n1 & (n1 - 1)) == 0) {          // exactly one space left
                        int sp2 = __builtin_ctz(n1);
                        int a0 = 2 + neg;
                        i64 a = neg ? -(i64)convN(p + a0, sp2 - a0) : (i64)convN(p + a0, sp2 - a0);
                        u64 b = convN(p + sp2 + 1, nlp - sp2 - 1);
                        p += nlp + 1; wmask &= wmask - 1;
                        if (a) {
                            int w = (int)(b >> 6), s = (int)(b & 63);
                            u64 av = (u64)(a < 0 ? -a : a);
                            u64 lo = av << s;
                            u64 hi = s ? (av >> (64 - s)) : 0;
                            if (a > 0) { if (lo) addAtWord(w, lo); if (hi) addAtWord(w + 1, hi); }
                            else       { if (lo) subAtWord(w, lo); if (hi) subAtWord(w + 1, hi); }
                        }
                        continue;
                    }
                } else {
                    if (nd && (nd & (nd - 1)) == 0) {          // exactly one space
                        int sp1 = __builtin_ctz(nd);
                        u64 k = convN(p + sp1 + 1, nlp - sp1 - 1);
                        p += nlp + 1; wmask &= wmask - 1;
                        u64 v2 = getWord((int)(k >> 6));
                        if (o < olim) { unsigned short sv = (unsigned short)((unsigned char)('0' + (char)((v2 >> (k & 63)) & 1)) | 0x0A00u); __builtin_memcpy(o, &sv, 2); o += 2; }
                        continue;
                    }
                }
            }
            }
        }
    slowpath:
        wmask = 0;
        if (*p == '1') {
            p += 2;
            i64 a;
            if (*p == '-') { p++; a = -(i64)parseU(p, pend); }
            else a = (i64)parseU(p, pend);
            p++;
            u64 b = parseU(p, pend);
            p++;
            if (!a) continue;
            int w = (int)(b >> 6), s = (int)(b & 63);
            u64 av = (u64)(a < 0 ? -a : a);
            u64 lo = av << s;
            u64 hi = s ? (av >> (64 - s)) : 0;
            if (a > 0) { if (lo) addAtWord(w, lo); if (hi) addAtWord(w + 1, hi); }
            else       { if (lo) subAtWord(w, lo); if (hi) subAtWord(w + 1, hi); }
        } else {
            p += 2;
            u64 k = parseU(p, pend);
            p++;
            u64 v = getWord((int)(k >> 6));
            if (o < olim) { unsigned short sv = (unsigned short)((unsigned char)('0' + (char)((v >> (k & 63)) & 1)) | 0x0A00u); __builtin_memcpy(o, &sv, 2); o += 2; }
        }
    }
    OUTSZ = (u64)(o - OUT);
#ifdef TEST_IO
    fwrite(OUT, 1, OUTSZ, stdout);
#else
    di->outsz = OUTSZ;
    register long rax __asm__("rax") = 60;
    register long rdi __asm__("rdi") = 0;
    __asm__ volatile("syscall" :: "a"(rax), "D"(rdi) : "rcx", "r11", "memory");
    __builtin_unreachable();
#endif
    return 0;
}

评测结果