题解-AT_abc314_d

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

题面大意

给你一个仅由大小写字母构成的字符串，要对其进行全体转大写或小写操作和单点修改为某字母操作，求所有操作完之后的字符串。

解题思路

我们考虑使用线段树维护大小写，字母的值是不变的，即使变也只会被单点修改，我们不用将其添加到线段树里面，线段树只用维护大小写状态。

问题就被转化成了：给你一个仅由 $0$ 和 $1$ 构成的数列，将其全部修改成某个值或单点改值，输出完成后的结果。

因为是全体转大写或小写，我们操作时只需要在根节点放一个赋值标记即可。

代码是赛时写的，比较恶心，将就着看吧。

#include <stdio.h>

typedef long long i64;
const i64 mod = 1, maxn = 800007;

int data[maxn << 2], upper[maxn << 2], lazy[maxn << 2], setf[2] = {387, 961};
// 用 setf 的原因是和 0 区分开，避免误传标记
char ch;

int gstd(char ch)
{
    if ('A' <= ch && ch <= 'Z')
        return ch - 'A';
    if ('a' <= ch && ch <= 'z')
        return ch - 'a';
    return 0;
}

void build(int index, int l, int r)
{
    if (l == r)
    {
        do
        {
            ch = getchar();
        } while ((!('a' <= ch && ch <= 'z')) && (!('A' <= ch && ch <= 'Z')));
        upper[index] = ('A' <= ch && ch <= 'Z');
        data[l] = gstd(ch);
        return;
    }
    int mid = (l + r) >> 1;
    build(index << 1, l, mid);
    build((index << 1) | 1, mid + 1, r);
}

void setlazy(int index, int l, int r, int val)
{
    if (val)
    {
        upper[index] = (val == setf[1]);
        lazy[index] = val;
    }
}

void push(int index, int l, int r)
{
    if (lazy[index])
    {
        int mid = (l + r) >> 1;
        setlazy(index << 1, l, mid, lazy[index]);
        setlazy(index << 1 | 1, mid + 1, r, lazy[index]);
        lazy[index] = 0;
    }
}

void single(int index, int l, int r, int pos, char val)
{
    push(index, l, r);
    if (l == r)
    {
        data[l] = gstd(val);
        setlazy(index, l, r, setf[('A' <= val && val <= 'Z')]);
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        single(index << 1, l, mid, pos, val);
    else
        single((index << 1) | 1, mid + 1, r, pos, val);
}

void search(int index, int l, int r)
{
    push(index, l, r);
    if (l == r)
    {
        putchar();
        return;
    }
    int mid = (l + r) >> 1;
    search(index << 1, l, mid);
    search(index << 1 | 1, mid + 1, r);
}

int n, m, u, v;

int main()
{
    scanf("%d", &n);
    build(1, 1, n);

    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        do
        {
            ch = getchar();
        } while (!('a' <= ch && ch <= 'z') && !('A' <= ch && ch <= 'Z'));

        if (u == 1)
            single(1, 1, n, v, ch);
        if (u == 2)
            setlazy(1, 1, n, setf[0]);
        if (u == 3)
            setlazy(1, 1, n, setf[1]);
    }

    search(1, 1, n);

    return 0;
}