• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Mar 28th, 2020 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<iostream>
2. #include<vector>
3. const int MAX_NUM = 100000;
4.
5. #define \$\$ std::cout << std::endl << "-----------------" << std::endl;
6. //#define sorted rev_sorted
7. //#define rev_sorted sorted
8.
9. int tree_min = 1000'000'000;
10. int min_ind = 0;
11.
12. int random_(){
13.     return (std::rand()<<14) + 5 * std::rand();
14. }
15.
16. struct Node{
17.     Node* left;
18.     Node* right;
19.     bool rev;
20.     int dop;
21.     int x;
22.     int y;
23.     int sz;
24.     int sum;
25.     int assig;
26.     int mx;
27.     int mn;
28.     bool sorted;
29.     bool rev_sorted;
30.     Node(int _x){
31.         x = _x;
32.         y = random_();
33.         dop = 0;
34.         rev = 0;
35.         sorted = 1;
36.         sz = 1;
37.         sum = x;
38.         assig = MAX_NUM;
39.         mx = _x;
40.         mn = _x;
41.         sorted = 1;
42.         rev_sorted = 1;
43.         left = nullptr;
44.         right = nullptr;
45.     }
46. };
47.
48. class Pivo{
49.     private:
50.         Node* root = nullptr;
51.
52.         static int size_(Node* &tree){
53.             return tree == nullptr ? 0 : tree->sz;
54.         }
55.
56.         static void push_dop(Node* &tree){
57.             if (tree->dop == 0){
58.                 return;
59.             }
60.             if (tree->left != nullptr){
61.                 tree->left->dop += tree->dop;
62.             }
63.             if (tree->right != nullptr){
64.                 tree->right->dop += tree->dop;
65.             }
66.             tree->sum += (tree->dop) * size_(tree);
67.             tree->x += tree->dop;
68.             tree->mx += tree->dop;
69.             tree->mn += tree->dop;
70.
71.             //std::cout << "aaaaaaaaaaaaaaaaaaaaaaaa\n" << size_(tree) << ' ' << tree->dop << ' ' << tree->sum <<  "\nbbbbbbbbbbbbbbbbbbbbbbbbbb\n";
72.             tree->dop = 0;
73.         }
74.
75.         static void push_assign(Node* &tree){
76.             if (tree->assig == MAX_NUM){
77.                 return;
78.             }
79.             if (tree->left != nullptr){
80.                 tree->left->assig = tree->assig;
81.                 tree->left->dop = 0;
82.             }
83.             if (tree->right != nullptr){
84.                 tree->right->assig = tree->assig;
85.                 tree->right->dop = 0;
86.             }
87.             tree->x = tree->assig;
88.             tree->sum = tree->assig * size_(tree);
89.             tree->mx = tree->assig;
90.             tree->mn = tree->assig;
91.             tree->sorted = 1;
92.             tree->rev_sorted = 1;
93.             tree->assig = MAX_NUM;
94.             tree->dop = 0;
95.         }
96.
97.         static void push_rev(Node* &tree){
98.             if (!tree->rev){
99.                 return;
100.             }
101.             if (tree->left != nullptr){
102.                 tree->left->rev ^= 1;
103.             }
104.             if (tree->right != nullptr){
105.                 tree->right->rev ^= 1;
106.             }
107.             std::swap(tree->right, tree->left);
108.             if (tree->sorted && !tree->rev_sorted || !tree->sorted && tree->rev_sorted){
109.             //if (tree->sorted ^ tree->rev_sorted){
110.                 tree->sorted ^= 1;
111.                 tree->rev_sorted ^= 1;
112.             }
113.             tree->rev = 0;
114.         }
115.
116.         static void push(Node* &tree){
117.             if(tree == nullptr){
118.                 return;
119.             }
120.             push_assign(tree);
121.             push_dop(tree);
122.             push_rev(tree);
123.         }
124.
125.         static void update(Node* &tree){
126.             if (tree == nullptr){
127.                 return;
128.             }
129.             push(tree->left);
130.             push(tree->right);
131.             int sm1 = 0;
132.             int sm2 = 0;
133.             tree->mx = tree->x;
134.             tree->mn = tree->x;
135.             tree->sz = size_(tree->left) + size_(tree->right) + 1;
136.             if (tree->left != nullptr){
137.                 sm1 = tree->left->sum;
138.                 tree->mx = std::max(tree->mx, tree->left->mx);
139.                 tree->mn = std::min(tree->mn, tree->left->mn);
140.             }
141.             if (tree->right != nullptr){
142.                 sm2 = tree->right->sum;
143.                 tree->mx = std::max(tree->mx, tree->right->mx);
144.                 tree->mn = std::min(tree->mn, tree->right->mn);
145.             }
146.             if ((tree->right != nullptr) && (tree->left != nullptr)){
147.                //     std::cout << "ya dolbaeb\n";
148.                 //std::cout << tree->left->x << ' ' << tree->left->mx << ' ' << tree->x << ' ' << tree->right->x << ' ' << tree->right->mx << std::endl;
149.                 tree->sorted = tree->left->sorted && tree->right->sorted && tree->left->mx <= tree->x && tree->x <= tree->right->mn ? 1 : 0;
150.                 tree->rev_sorted = (tree->left->rev_sorted) && (tree->right->rev_sorted) && (tree->left->mn <= tree->x) && (tree->x >= tree->right->mx) ? 1 : 0;
151.             } else if (tree->left != nullptr){
152.                 //std::cout << "ya dolbaeb2\n";
153.                 tree->sorted = tree->left->sorted && tree->x >= tree->left->mn ? 1 : 0;
154.                 tree->rev_sorted = tree->left->rev_sorted && tree->x <= tree->left->mn ? 1 : 0;
155.             } else if (tree->right != nullptr){
156.                 //std::cout << "ya dolbaeb3\n";
157.                 tree->sorted = tree->right->sorted && tree->x <= tree->right->mn ? 1 : 0;
158.                 tree->rev_sorted = tree->right->rev_sorted && tree->x >= tree->right->mx ? 1 : 0;
159.             } else {
160.                 //std::cout << "ya dolbaeb4\n";
161.                 tree->sorted = 1;
162.                 tree->rev_sorted = 1;
163.             }
164.             tree->sum = tree->x + sm1 + sm2;
165.         }
166.         static Node* merge_(Node* &f_tree, Node* &s_tree){
167.             push(f_tree);
168.             push(s_tree);
169.             //std::cout << "************" << std::endl;
170.             if (f_tree == nullptr){
171.                  //   std::cout << "govno" << std::endl;
172.                 return s_tree;
173.             }
174.             if (s_tree == nullptr){
175.                 return f_tree;
176.             }
177.             //std::cout << "%%%%%%%%%%%%%%%%%%" << std::endl;
178.             if (f_tree->y > s_tree->y){
179.                 f_tree->right = merge_(f_tree->right, s_tree);
180.                 update(f_tree);
181.                 return f_tree;
182.             } else {
183.                 s_tree->left = merge_(f_tree, s_tree->left);
184.                 update(s_tree);
185.                 return s_tree;
186.             }
187.         }
188.         static std::pair<Node*, Node*> split(Node* &tree, int key){
189.             push(tree);
190.             if (tree == nullptr){
191.                 return {nullptr, nullptr};
192.             }
193.             if(size_(tree->left) < key){
194.                 std::pair<Node*, Node*> trees = split(tree->right, key - size_(tree->left) - 1);
195.                 tree->right = trees.first;
196.                 update(tree);
197.                 return {tree, trees.second};
198.             } else {
199.                 std::pair<Node*, Node*> trees = split(tree->left, key);
200.                 tree->left = trees.second;
201.                 update(tree);
202.                 return {trees.first, tree};
203.             }
204.         }
205.
206.     public:
207.         static int descent(Node* &tree, int suff_max){
208.             if (tree == nullptr){
209.                 return -INT_MAX;
210.             }
211.             push(tree->left);
212.             push(tree->right);
213.           //  if (tree->rev_sorted){
214.           //      return size_(tree);
215.           //  }
216.             std::cout << "tree: "; print_(tree); std::cout << std::endl;
217.             if (tree->left != nullptr){
218.                 std::cout << "left:\n";
219.                 print_(tree->left);
220.                 std::cout << std::endl << ' ' << tree->left->sorted << ' ' << tree->left->rev_sorted << std::endl;
221.             } else {
222.                 std::cout << "No left\n";
223.             }
224.             if (tree->right != nullptr){
225.                 std::cout << "right:\n";
226.                 print_(tree->right);
227.                 std::cout << std::endl << ' ' << tree->right->sorted << ' ' << tree->right->rev_sorted << std::endl;
228.             } else {
229.                 std::cout << "No right\n";
230.             }
231.            /* if (!tree->right || tree->right->rev_sorted){
232.                 return descent(tree->left) + size_(tree->right) + 1;
233.             } else {
234.                 descent(tree->right);
235.             }*/
236.
237.             /*if (tree->right != nullptr && tree->right->rev_sorted && tree->x >= tree->right->mx){
238.                 return descent(tree->left) + size_(tree->right) + 1;
239.             } else if (tree->right != nullptr && tree->right->rev_sorted){
240.                 return size_(tree->right) + 1;
241.             } else {
242.                 return descent(tree->right);
243.             }*/
244.             //if (tree->right != nullptr && tree->x == tree->right->x){
245.             //    tree->
246.             //}
247.             std::cout << "suff_max: " << suff_max << std::endl;
248.             if (tree->right != nullptr && !(tree->right->rev_sorted)){
249.                 std::cout << "eshkere\n";
250.                 return descent(tree->right, suff_max);
251.             } else if (tree->right != nullptr && tree->right->rev_sorted){
252.                 std::cout << "ponos\n";
253.                 if (tree->right->mn < suff_max){
254.                     std::cout << "sudaaaaaaaaa\n";
255.                     return descent(tree->right, suff_max);
256.                 }
257.                 if (tree->right->mx > tree->x){
258.                     std::cout << "igor geniy" << std::endl;
259.                     return size_(tree->right);
260.                 }
261.                 return descent(tree->left, tree->x) + size_(tree->right) + 1;
262.             } else {
263.                 if (tree->x < suff_max){
264.                     std::cout << "igor gay" << std::endl;
265.                     return 0;
266.                 }
267.                 std::cout << "igor ne gay" << ' ' << size_(tree->right) + 1 << ' ';// << descent(tree->left, tree->x) << ' ' << (tree->left == nullptr) << std::endl;
268.                 return descent(tree->left, tree->x) + size_(tree->right) + 1;
269.             }
270.         }
271.         static void upper_bound_(Node* &tree, int val, int num){
272.             if (tree == nullptr){
273.                 return;
274.             }
275.             if (tree->x <= val && tree->left != nullptr){
276.                 upper_bound_(tree->left, val, num);// + size_(tree->left) + 1);
277.             } else {
278.                 if (tree_min > tree->x && tree->x > val){
279.                     tree_min = tree->x;
280.                     min_ind = num + size_(tree->left);// + size_(tree->left);
281.                 }
282.                 if (tree->right != nullptr){
283.                     upper_bound_(tree->right, val, num + size_(tree->left) + 1);
284.                 }
285.             }
286.         }
287.         static void swap_(Node* &tree, int fir, int sec){
288.             std::cout << "starttttttttttttttttttt\n";
289.             std::cout << "real swap: " << fir << ' ' << sec << std::endl;
290.             print_(tree); std::cout << std::endl;
291.             std::pair<Node*, Node*> forest1 = split(tree, fir + 1);
292.             std::cout << "ahuy: "; print_(forest1.first); std::cout << std::endl;
293.             std::pair<Node*, Node*> forest2 = split(forest1.second, sec - size_(forest1.first));
294.             Node* help_tree = merge_(forest1.first, forest2.second);
295.             \$\$
296.             print_(help_tree); std::cout << "   "; print_(forest1.first); std::cout << "   "; print_(forest2.second);
297.             \$\$
299.             add_reverse(help_tree, fir, fir + 1);
300.           //  print_(forest2.first);
301.             std::cout << std::endl;
302.         //add_reverse(forest2.first, 0, size_(forest2.first) - 1);
303.             std::pair<Node*, Node*> forest3 = split(help_tree, fir + 1);
304.             Node* help_tree2 = merge_(forest3.first, forest2.first);
305.             std::cout << "help_tree2: "; print_(help_tree2); std::cout << std::endl;
306.             tree = merge_(help_tree2, forest3.second);
307.             print_(tree);
308.             std::cout << "\nfinishhhhhhhhhhhhhhhhhh\n";
309.         }
310.
311.         static void next_permutation_(Node* &tree){
312.             \$\$ print_(tree); \$\$
313.             int otstup = descent(tree, -INT_MAX);
314.             int pos = size_(tree) - otstup - 1;
315.             std::cout << pos << ' ' << tree->sorted << ' ' << tree->rev_sorted << ' ' << otstup <<"  mocha" << std::endl;
316.             if (otstup < 0){
317.                 add_reverse(tree, 0, size_(tree) - 1);
318.                 return;
319.             }
320.             std::pair<Node*, Node*> forest1 = split(tree, pos);
321.             std::pair<Node*, Node*> forest2 = split(forest1.second, 1);
322.             int val = forest2.first->x;
323.             std::cout << val << std::endl;
324.             Node* new_tree = forest2.second; //merge_(forest2.first, forest2.second);
325.             tree_min = new_tree->mx + 1;
326.             std::cout << "qqqqqqqqqqqqqqqqqqqq\n";
327.             print_(new_tree);
328.             std::cout << std::endl << " chlen " << tree_min << std::endl;
329.             upper_bound_(new_tree, val, 0);
330.             std::cout << "tree_min: " << tree_min << ' ' << min_ind << std::endl;
331.             new_tree = merge_(forest2.first, forest2.second);
332.             tree = merge_(forest1.first, new_tree);
333.             std::cout << "swapaem: " << pos << ' ' << min_ind << std::endl;
334.             swap_(tree, pos, pos + min_ind + 1);
335.             add_reverse(tree, pos + 1, size_(tree) - 1);
336.             //add_reverse(tree, pos + 1, pos + min_ind);
337.         }
338.
339.         static void add_val(Node* &tree, int val){
340.             tree->dop += val;
341.             push(tree);
342.         }
343.         static void ass_val(Node* &tree, int val){
344.             tree->assig = val;
345.             tree->dop = 0;
346.             push(tree);
347.         }
348.         static void add_rev(Node* &tree, int val){
349.             tree->rev ^= val;
350.             push(tree);
351.         }
352.         static int get_sum(Node* &tree){
353.             return tree->sum;
354.         }
355.         static int get_min(Node* &tree){
356.             return tree->mn;
357.         }
358.         static int get_max(Node* &tree){
359.             return tree->mx;
360.         }
361.         void ins(int x, int pos){
362.             Node* new_vertex = new Node(x);
363.             std::pair<Node*, Node*> trees = split(root, pos + 1);
364.             Node* tree1 = merge_(trees.first, new_vertex);
365.             root = merge_(tree1, trees.second);
366.         }
367.
368.         void del(int pos){
369.             std::pair<Node*, Node*> trees1 = split(this->root, pos + 1);
370.             std::pair<Node*, Node*> trees2 = split(trees1.first, pos);
371.             this->root = merge_(trees2.first, trees1.second);
372.         }
373.         void operation(int val, int start, int finish, std::string type){
374.             std::pair<Node*, Node*> forest1 = split(this->root, finish + 1);
375.             std::pair<Node*, Node*> forest2 = split(forest1.first, start);
377.                 std::cout << "huy" << ' ' << val << '\n';
379.             } else if (type == "rev") {
381.             } else if (type == "assign"){
382.                 std::cout << "tut0" << std::endl;
383.                 ass_val(forest2.second, val);
384.             } else {
385.                 next_permutation_(forest2.second);
386.             }
387.            // f(forest2.second, val);
388.             Node* help_tree = merge_(forest2.first, forest2.second);
389.             this->root = merge_(help_tree, forest1.second);
390.         }
391.
392.         int get(int start, int finish, std::string type){
393.             std::pair<Node*, Node*> forest1 = split(this->root, finish + 1);
394.             std::pair<Node*, Node*> forest2 = split(forest1.first, start);
395.             Node* tree = forest2.second;
396.             push(tree);
397.           //  print_(tree);
398.         //    std::cout << std::endl;
400.             if (type == "sum"){
402.             } else if (type == "min"){
404.             } else {
406.             }
407.             Node* help_tree = merge_(forest2.first, tree);
408.             this->root = merge_(help_tree, forest1.second);
410.         }
411.         void build(std::vector<int> &s){
412.             for (int i: s){
413.                 Node* new_vertex = new Node(i);
414.                 //print2(new_vertex);
415.                 //print_(new_vertex);\$\$ \$\$
416.                 root = merge_(root, new_vertex);
417.                // std::cout << "jopa" << std::endl;
418.                 //print2(root);
419.                 //print_(root); \$\$
420.             }
421.         }
422.         void print(){
423.             print_(root);
424.         }
425.         static void print_(Node* &tree){
426.             //
427.             if (tree == nullptr){
428.                 return;
429.             }
430.             push(tree);
431.             //std::cout << "00000" << ' ' << (tree->left == nullptr) << ' ' << (tree->right == nullptr) << std::endl;
432.             if (tree->left != nullptr){
433.                 print_(tree->left);
434.             }
435.             //std::cout << "11111" << std::endl;
436.             std::cout << tree->x << ' ';
437.             //std::cout << "22222" << std::endl;
438.             if (tree->right != nullptr){
439.                 print_(tree->right);
440.             }
441.         }
442.         Pivo(){
443.             root = nullptr;
444.         }
445.         static void print2(Node* &t){
446.             std::cout << std::endl << t->x << ' ' << (t->left == nullptr) << ' ' << (t->right == nullptr) << std::endl;
447.             std::cout << t->dop << ' ' << t->sum << ' ' << t->x << ' ' << size_(t) << std::endl;
448.             if (t->left) std::cout << t->left->dop << ' ' << t->left->sum << ' ' << t->left->x << std::endl;
449.             else std::cout << "No left" << std::endl;
450.             if (t->right) std::cout << t->right->dop << ' ' << t->right->sum << ' ' << t->right->x << std::endl;
451.             else std::cout << "No right" << std::endl;
452.         }
453.         static void add_reverse(Node* &tree, int start, int finish){
454.             if (tree == nullptr){
455.                 return;
456.             }
457.             std::pair<Node*, Node*> forest1 = split(tree, finish + 1);
458.             std::pair<Node*, Node*> forest2 = split(forest1.first, start);
460.     // f(forest2.second, val);
461.             Node* help_tree = merge_(forest2.first, forest2.second);
462.             tree = merge_(help_tree, forest1.second);
463.             push(tree);
464.         }
465. };
466.
467. int main(){
468.    /* int n;
469.     std::cin >> n;
470.     std::vector<int> s(n);
471.     Pivo tree;
472.     for (int i = 0; i < n; ++i) std::cin >> s[i];
473.     tree.build(s);
474.     tree.print();
475.     std::cout << std::endl << tree.get(2, 4, "sum") << std::endl;
476.     \$\$
478.     tree.print();
479.     std::cout << std::endl << tree.get(2, 4, "sum") << std::endl;
480.     tree.print();
481.     std::cout << "gavnoooooooooooo" << std::endl;
482.     tree.operation(10, 1, 3, "assign");
483.     \$\$
484.     std::cout << tree.get(2, 4, "get") << "  huy\n";
485.     \$\$
486.     tree.print();
487.     \$\$
488.     tree.operation(1, 0, 2, "rev");
489.     tree.operation(6, 1, 1, "assign");
490.     tree.print();
491.     tree.del(1);
492.     \$\$
493.     tree.print();
494.     \$\$
495.     tree.ins(17, 2);
496.     tree.print();
497.     \$\$
498.     std::cout << tree.get(0, 4, "min") << ' ' << tree.get(0, 4, "max") << ' ' << tree.get(0,  4, "sum") << std::endl;
499.     */
500.     int type, n, m;
501.     std::cin >> n;
502.     std::vector<int> s(n);
503.     for (int i = 0; i < n; ++i){
504.         std::cin >> s[i];
505.     }
506.     Pivo tree;
507.     //\$\$
508.     tree.build(s);
509.     //\$\$
510.     //std::cout << n << ' ' << m << std::endl;
511.     while (1){
512.         int a, b;
513.         std::cin >> a >> b;
514.         tree.operation(1, a, b, "next");
515.         tree.print();
516.         std::cout << std::endl;
517.     }
518.     return 0;
519. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top