分块字符串操作

题目描述

给定一个初始字符串 $s$ 和 $m$ 次操作，操作分为两种：

1. 插入操作 (I)：在位置 $x$ 插入字符 $ch$
2. 查询操作 (Q)：查询位置 $x$ 的字符

解题思路

采用分块数据结构：

• 将字符串分成 $\sqrt{n+m}$ 大小的块
• 每个块维护字符数组和大小
• 使用前缀和数组快速定位块

标程代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

#define MAXN 1000005
#define N 2005

struct Block {
    int Size;
    char data[N];
    
    void Push_back(char ch) {
        data[++Size] = ch;
    }
    
    void Insert(int pos, char ch) {
        for(int i = Size; i >= pos; --i)
            data[i+1] = data[i];
        data[pos] = ch;
        Size++;
    }
    
    char getData(int pos) {
        return data[pos];
    }
};

Block block[N];
int sum[N];
int n, m, num;
char s[MAXN];

void maintain() {
    for(int i = 1; i <= num; ++i)
        sum[i] = sum[i-1] + block[i].Size;
}

void Insert(int id, int pos, char ch) {
    block[id].Insert(pos, ch);
}

char Query(int id, int pos) {
    return block[id].getData(pos);
}

void myInsert(int p, char ch) {
    int id = lower_bound(sum+1, sum+1+num, p) - sum;
    Insert(id, p-sum[id-1], ch);
    maintain();
}

char myQuery(int p) {
    int id = lower_bound(sum+1, sum+1+num, p) - sum;
    return Query(id, p-sum[id-1]);
}

void Init() {
    num = sqrt((n+m)*1.0) + 1;
    for(int i = 1; i < N; ++i)
        block[i].Size = 0;
    for(int i = 0; i < n; ++i)
        block[i/num+1].Push_back(s[i]);
    maintain();
}

int main() {
    scanf("%s", s);
    n = strlen(s);
    scanf("%d", &m);
    memset(sum, 0, sizeof(sum));
    Init();
    
    for(int i = 0; i < m; ++i) {
        char op[5];
        scanf("%s", op);
        if(op[0] == 'Q') {
            int x;
            scanf("%d", &x);
            printf("%c\n", myQuery(x));
        }
        else if(op[0] == 'I') {
            int x;
            char ch[5];
            scanf("%s%d", ch, &x);
            if(x > sum[num]) {
                block[num].Push_back(ch[0]);
                maintain();
            }
            else {
                myInsert(x, ch[0]);
            }
        }
    }
    return 0;
}