洛谷 4979.矿洞:坍塌

第一眼,线段树!
开敲,真 TM 难写啊喂!

第二眼,分块!
开敲,还是真 TM 难写啊喂!

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

开 O2 过了,一开始区间赋值写得让珂朵莉退化成暴力还带 log\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");
}
}
}

arknights