洛谷 4979 矿洞：坍塌

发表于 | 分类于 |

第一眼，线段树！
开敲，真 TM 难写啊喂！

第二眼，分块！
开敲，还是真 TM 难写啊喂！

学习了一下珂朵莉树，发现是一种很强大的珂学数据结构。

开 O2 过了，一开始区间赋值写得让珂朵莉退化成暴力还带 \(\log\)……

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#pragma GCC optimize (2)
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}
inline char nc()
{
    char ret = 0;
    while(ret < 'A' || ret > 'Z')
        ret = gc();
    return ret;
}

const int N = 5e5;
int n,k;
struct node
{
    int l,r;
    mutable char val;
    inline bool operator<(const node &a) const
    {
        return l < a.l;
    }
};
set<node> tree;
typedef set<node>::iterator IT;
IT split(int x)
{
    IT it = tree.lower_bound((node){x,0,0});
    if(it != tree.end() && it->l == x)
        return it;
    --it;
    int l = it->l,r = it->r;
    char v = it->val;
    tree.erase(it);
    tree.insert((node){l,x - 1,v});
    return tree.insert((node){x,r,v}).first;
}
inline void assign(int l,int r,char val)
{
    IT itr = split(r + 1),itl = split(l);
    tree.erase(itl,itr);
    tree.insert((node){l,r,val});
}
bool issame(int l,int r)
{
    IT itr = split(r + 1),itl = split(l);
    char same = itl->val;
    for(++itl;itl != itr;++itl)
        if(itl->val ^ same)
            return 0;
    return 1;
}
int main()
{
    read(n);
    char x,last = nc();
    int cnt = 1;
    for(register int i = 2;i <= n;++i)
    {
        x = nc();
        if(x == last)
            ++cnt;
        else
        {
            tree.insert((node){i - cnt,i - 1,last});
            last = x;
            cnt = 1;
        }
    }
    tree.insert((node){n - cnt + 1,n,last});
    read(k);
    char op;
    int l,r;
    while(k--)
    {
        op = nc();
        read(l),read(r);
        if(op == 'A')
        {
            x = nc();
            assign(l,r,x);
        }
        else
        {
            if(1 < l && r < n && split(l - 1)->val == split(r + 1)->val)
                puts("No");
            else if(!issame(l,r))
                puts("No");
            else
                puts("Yes");
        }
    }
}