#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const ull BASE = 131;
const int MAXN = 1000005 + 5;

ull pow_base[MAXN];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Node {
    int ch[2], sz, val;
    ull h1, h2;      // 正向哈希、反向哈希
    int pri;         // 随机优先级
    bool rev;        // 翻转标记
} t[MAXN];
int tot;

int new_node(int v) {
    ++tot;
    t[tot].ch[0] = t[tot].ch[1] = 0;
    t[tot].sz = 1;
    t[tot].val = v;
    t[tot].h1 = t[tot].h2 = v;
    t[tot].pri = rng();
    t[tot].rev = false;
    return tot;
}

void push_up(int u) {
    if (!u) return;
    int l = t[u].ch[0], r = t[u].ch[1];
    t[u].sz = t[l].sz + 1 + t[r].sz;
    int v = t[u].val;
    t[u].h1 = t[l].h1 * pow_base[t[r].sz + 1] + v * pow_base[t[r].sz] + t[r].h1;
    t[u].h2 = t[r].h2 * pow_base[t[l].sz + 1] + v * pow_base[t[l].sz] + t[l].h2;
}

void apply_rev(int u) {
    if (!u) return;
    swap(t[u].ch[0], t[u].ch[1]);
    swap(t[u].h1, t[u].h2);
    t[u].rev ^= 1;
}

void push_down(int u) {
    if (t[u].rev) {
        apply_rev(t[u].ch[0]);
        apply_rev(t[u].ch[1]);
        t[u].rev = false;
    }
}

// 按大小分裂：左树包含前 k 个节点
void split(int u, int k, int &l, int &r) {
    if (!u) { l = r = 0; return; }
    push_down(u);
    int left_sz = t[t[u].ch[0]].sz;
    if (k <= left_sz) {
        r = u;
        split(t[u].ch[0], k, l, t[u].ch[0]);
    } else {
        l = u;
        split(t[u].ch[1], k - left_sz - 1, t[u].ch[1], r);
    }
    push_up(u);
}

int merge(int l, int r) {
    if (!l || !r) return l | r;
    if (t[l].pri > t[r].pri) {
        push_down(l);
        t[l].ch[1] = merge(t[l].ch[1], r);
        push_up(l);
        return l;
    } else {
        push_down(r);
        t[r].ch[0] = merge(l, t[r].ch[0]);
        push_up(r);
        return r;
    }
}

// 不修改树结构的区间哈希查询（会下传懒标记）
ull range_hash(int u, int ql, int qr) {
    if (!u || ql > qr) return 0;
    if (ql <= 1 && qr >= t[u].sz) {
        return t[u].h1;
    }
    push_down(u);
    int lsz = t[t[u].ch[0]].sz;
    int mid = lsz + 1;
    if (qr < mid) {
        return range_hash(t[u].ch[0], ql, qr);
    } else if (ql > mid) {
        return range_hash(t[u].ch[1], ql - mid, qr - mid);
    } else {
        ull left_part = range_hash(t[u].ch[0], ql, mid - 1);
        int left_len = mid - ql;
        ull right_part = range_hash(t[u].ch[1], 1, qr - mid);
        int right_len = qr - mid;
        ull mid_val = t[u].val;
        return left_part * pow_base[right_len + 1] + mid_val * pow_base[right_len] + right_part;
    }
}

void insert(int &root, int pos, int val) {
    int a, b;
    split(root, pos - 1, a, b);
    int u = new_node(val);
    root = merge(merge(a, u), b);
}

void remove(int &root, int pos) {
    int a, b, c;
    split(root, pos - 1, a, b);
    split(b, 1, b, c);
    root = merge(a, c);
}

void reverse(int &root, int l, int r) {
    int a, b, c;
    split(root, l - 1, a, b);
    split(b, r - l + 1, b, c);
    apply_rev(b);
    root = merge(merge(a, b), c);
}

int query(int root, int s, int tt) {
    int len = t[root].sz - 2;          // 真实长度
    int max_len = min(len - s + 1, len - tt + 1);
    int inner_s = s + 1, inner_t = tt + 1;
    int low = 0, high = max_len;
    while (low < high) {
        int mid = (low + high + 1) >> 1;
        if (range_hash(root, inner_s, inner_s + mid - 1) ==
            range_hash(root, inner_t, inner_t + mid - 1))
            low = mid;
        else
            high = mid - 1;
    }
    return low;
}

int build(int l, int r, int *arr) {
    if (l > r) return 0;
    int mid = (l + r) >> 1;
    int u = new_node(arr[mid]);
    t[u].ch[0] = build(l, mid - 1, arr);
    t[u].ch[1] = build(mid + 1, r, arr);
    push_up(u);
    return u;
}

int arr[500010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    pow_base[0] = 1;
    for (int i = 1; i < MAXN; ++i)
        pow_base[i] = pow_base[i - 1] * BASE;

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    // 建树，哨兵 0 在首尾，内部字符 1/2 表示 '0'/'1'
    arr[1] = 0;                        // 哨兵
    for (int i = 0; i < n; ++i)
        arr[i + 2] = (s[i] == '0' ? 1 : 2);
    arr[n + 2] = 0;                    // 哨兵

    int root = build(1, n + 2, arr);

    while (m--) {
        int op; cin >> op;
        if (op == 1) {
            int p; char c;
            cin >> p >> c;
            int val = (c == '0' ? 1 : 2);
            insert(root, p + 2, val);
        } else if (op == 2) {
            int p; cin >> p;
            remove(root, p + 1);
        } else if (op == 3) {
            int s, t;
            cin >> s >> t;
            reverse(root, s + 1, t + 1);
        } else if (op == 4) {
            int s, t;
            cin >> s >> t;
            cout << query(root, s, t) << '\n';
        }
    }
    return 0;
}

记录详情
Wrong Answer

状态 耗时 内存占用

#1 Accepted 3ms 312.0 KiB
#2 Wrong Answer 2ms 312.0 KiB
#3 Wrong Answer 2ms 328.0 KiB
#4 Wrong Answer 14ms 312.0 KiB
#5 Wrong Answer 73ms 312.0 KiB
#6 Wrong Answer 159ms 308.0 KiB
#7 Wrong Answer 192ms 312.0 KiB
#8 Wrong Answer 208ms 312.0 KiB
#9 Wrong Answer 160ms 328.0 KiB
#10 Wrong Answer 136ms 312.0 KiB

#include<iostream>
using namespace std;

const int n2=81,n4=1185,n6=751075,n8=72879159;

bool nearly2(int i1,int i2)
{
    return i1!=i2;
}

bool nearly4(int i1,int i2,int i3,int i4)
{
    int aa=i1+i3,bb=i2+i4,cc=aa-bb;
    if (cc==0) return false;
    else if (cc>0) return ((i1-cc>0)||(i3-cc>=0)||(i2+cc<10)||(i4+cc<10));
    else return ((i2-cc>=0)||(i4-cc>=0)||(i1+cc<10)||(i3+cc<10));
}

bool nearly6(int i1,int i2,int i3,int i4,int i5,int i6)
{
    int aa=i1+i3+i5,bb=i2+i4+i6,cc=aa-bb;
    if (cc==0) return false;
    else if (cc>0) return ((i1-cc>0)||(i3-cc>=0)||(i5-cc>=0)||(i2+cc<10)||(i4+cc<10)||(i6+cc<10));
    else return ((i2-cc>=0)||(i4-cc>=0)||(i6-cc>=0)||(i1+cc<10)||(i3+cc<10)||(i5+cc<10));
}

bool nearly8(int i1,int i2,int i3,int i4,int i5,int i6,int i7,int i8)
{
    int aa=i1+i3+i5+i7,bb=i2+i4+i6+i8,cc=aa-bb;
    if (cc==0) return false;
    else if (cc>0) return ((i1-cc>0)||(i3-cc>=0)||(i5-cc>=0)||(i7-cc>=0)||(i2+cc<10)||(i4+cc<10)||(i6+cc<10)||(i8+cc<10));
    else return ((i2-cc>=0)||(i4-cc>=0)||(i6-cc>=0)||(i8-cc>=0)||(i1+cc<10)||(i3+cc<10)||(i5+cc<10)||(i7+cc<10));   
}

int f1(int x)
{
    int i,t;
    for (i=t=1;t<=x;t*=10,i++);
    return i;
}

int f2(int x)
{
    int t;
    for (t=1;t<=x;t*=10);
    return t;
}

int main()
{
    int a,b,sum=0;
    cin>>a>>b;
    for (int i=a;i<=b;i++) 
    {
        if (i>9 && i<100) sum+=nearly2(i/10,i%10);
        else if (i>999 && i<10000) sum+=nearly4(i/1000,i/100%10,i/10%10,i%10);
        else if (i>99999 && i<1000000) sum+=nearly6(i/100000,i/10000%10,i/1000%10,i/100%10,i/10%10,i%10);
        else if (i>9999999 && i<10000000) sum+=nearly8(i/10000000,i/1000000%10,i/100000%10,i/10000%10,i/1000%10,i/100%10,i/10%10,i%10);
    }
    cout<<sum<<endl;
    return 0;
}