不太清楚
static int x; if((x++)%(a->Size() + b->Size()) < a->Size()){ a = Cp(a);
我本來是用pri去合的，可是為啥會TLE喏._.不太懂
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
| #include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>using namespace std;template<typename T>struct _RefCounter{ T data; int ref; _RefCounter(const T&d=nullptr):data(d),ref(0){} void DecRefX(){ if(this == nullptr) return; ref--; if(ref == 0) delete this; return; } void IncRefX(){ if(this == nullptr) return; ref++; return; }};template<typename T>struct reference_pointer{ _RefCounter<T> *p; T *operator->(){ return &(p->data); } T &operator*(){ return p->data; } reference_pointer&operator=(const reference_pointer &t){ p->DecRefX(); p = t.p; p->IncRefX(); return *this; } bool IsNull(){ return p == nullptr; } void SetNull(){ p->DecRefX(); p = nullptr; return; } reference_pointer(_RefCounter<T> *t=nullptr):p(t){ p->IncRefX(); return; } reference_pointer(const reference_pointer &t):p(t.p){ p->IncRefX(); return; } ~reference_pointer(){ p->DecRefX(); return; }};template<typename T,typename... _Args>inline reference_pointer<T>new_reference(_Args... __args){ return reference_pointer<T> (new _RefCounter<T>(T(__args...)));}struct Jeap;typedef reference_pointer<Jeap> ptrJeap;struct Jeap{ ptrJeap l, r; int pri; char val; int sz; Jeap(char c = 0){ sz = 1; val = c; pri = rand(); return; } int Size(){ return (this == nullptr) ? 0:sz; } void Update(){ sz = 1 + l->Size() + r->Size(); return; } void Print(){ if(this == nullptr) return; l->Print(); putchar(val); r->Print(); return; }};ptrJeap Cp(ptrJeap a){ if(a.p == nullptr) return a; ptrJeap r = new_reference<Jeap>(); *r = *a; return r;}ptrJeap Merge(ptrJeap a, ptrJeap b){ if(a.IsNull()) return Cp(b); if(b.IsNull()) return Cp(a); static int x; if((x++)%(a->Size() + b->Size()) < a->Size()){ a = Cp(a); a->r = Merge(a->r, b); a->Update(); return a; }else{ b = Cp(b); b->l = Merge(a, b->l); b->Update(); return b; }}void Split(ptrJeap org, int low, ptrJeap &a, ptrJeap &b){ if(org.IsNull()){ a.SetNull(); b.SetNull(); }else if(org->l->Size() < low){ a = Cp(org); Split(org->r, low - org->l->Size() - 1, a->r, b); a->Update(); }else{ b = Cp(org); Split(org->l, low, a, b->l); b->Update(); } return;}char buf[1000010];ptrJeap Build(int ll, int rr){ if(ll > rr){ ptrJeap nl; return nl; } int mid = (ll+rr)>>1; ptrJeap ret = Build(ll, mid-1); ret = Merge(ret, new_reference<Jeap>(buf[mid])); return Merge(ret, Build(mid+1, rr));}int main(){ int n, m; scanf("%d", &m); scanf("%s", buf); scanf("%d", &n); ptrJeap root(Build(0, strlen(buf) - 1)); while(n--){ int l, r, x; scanf("%d %d %d", &l, &r, &x); ptrJeap gen, tmp, a, b; Split(root, r+1, gen, tmp); Split(gen, l, tmp, gen); Split(root, x, a, b); root = Merge(Merge(a, gen), b); Split(root, m, root, tmp); } root->Print(); puts(""); return 0;} |
