[UVA] 12003 - Array Transformer

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12003 - Array Transformer
Source            : UVA Online Judge
Category          : Data Structure
Algorithm         : Segment Tree, Policy Based Data Structure
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2. #include <ext/pb_ds/assoc_container.hpp>  
3. #include <ext/pb_ds/tree_policy.hpp>  
4.   
5. using namespace std;  
6. using namespace __gnu_pbds;  
7.   
8. #define ll                       long long  
9. #define pli                      pair <ll, int>  
10. #define MK                       make_pair  
11. #define ff                       first  
12. #define ss                       second  
13.   
14. template <typename T> using orderedSet = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;  
15.   
16. static const int maxn = 300000 + 5;  
17.   
18. int ptr;  
19.   
20. struct segmentTree  
21. {  
22.       orderedSet <pli> oms;  
23.   
24.       void assignLeaf(ll val, int ptr)  
25.       {  
26.             oms.insert({val, ptr});  
27.       }  
28.       void marge(segmentTree &L, segmentTree &R)  
29.       {  
30.             orderedSet <pli>::iterator it;  
31.             for (it = L.oms.begin(); it != L.oms.end(); it++) oms.insert({it->ff, it->ss});  
32.             for (it = R.oms.begin(); it != R.oms.end(); it++) oms.insert({it->ff, it->ss});  
33.       }  
34.       int lessNum(ll v)  
35.       {  
36.             int cnt = oms.order_of_key({v, -1});  
37.             return cnt;  
38.       }  
39.       void eraseOld(ll v)  
40.       {  
41.             orderedSet <pli>::iterator it;  
42.             it = oms.lower_bound({v, -1});  
43.             oms.erase(it);  
44.       }  
45.       void insertNew(ll v, int ptr)  
46.       {  
47.             oms.insert({v, ptr});  
48.       }  
49. } Tree[maxn << 2];  
50.   
51. ll arr[maxn];  
52.   
53. void build(int node, int a, int b)  
54. {  
55.       if (a == b)  
56.       {  
57.             Tree[node].assignLeaf(arr[a], ++ptr);  
58.             return;  
59.       }  
60.       int lft = node << 1;  
61.       int rgt = lft|1;  
62.       int mid = (a+b) >> 1;  
63.       build(lft, a, mid);  
64.       build(rgt, mid+1, b);  
65.       Tree[node].marge(Tree[lft], Tree[rgt]);  
66. }  
67.   
68. int query(int node, int a, int b, int i, int j, ll v)  
69. {  
70.       if (a > b || a > j || b < i) return 0;  
71.       if (a >= i && b <= j) return Tree[node].lessNum(v);  
72.       int lft = node << 1;  
73.       int rgt = lft | 1;  
74.       int mid = (a+b) >> 1;  
75.       int p1, p2;  
76.       p1 = query(lft, a, mid, i, j, v);  
77.       p2 = query(rgt, mid+1, b, i, j, v);  
78.       return p1 + p2;  
79. }  
80.   
81. void update(int node, int a, int b, int pos, ll old, ll newNum, int ptr)  
82. {  
83.       if (a > b || a > pos || b < pos) return;  
84.       if (a >= pos && b <= pos)  
85.       {  
86.             arr[pos] = newNum;  
87.             Tree[node].eraseOld(old);  
88.             Tree[node].insertNew(newNum, ptr);  
89.             return;  
90.       }  
91.       int lft = node << 1;  
92.       int rgt = lft | 1;  
93.       int mid = (a+b) >> 1;  
94.       update(lft, a, mid, pos, old, newNum, ptr);  
95.       update(rgt, mid+1, b, pos, old, newNum, ptr);  
96.       Tree[node].eraseOld(old);  
97.       Tree[node].insertNew(newNum, ptr);  
98. }  
99.   
100. int main()  
101. {  
102.       //freopen("in.txt", "r", stdin);  
103.   
104.       int n, m; // m : query  
105.       ll u;  
106.       scanf("%d %d %lld", &n, &m, &u);  
107.       for (int i = 1; i <= n; i++) scanf("%lld", &arr[i]);  
108.       build(1, 1, n);  
109.       while (m--)  
110.       {  
111.             int L, R, p;  
112.             ll v;  
113.             scanf("%d %d %lld %d", &L, &R, &v, &p);  
114.             int k = query(1, 1, n, L, R, v);  
115.             ll newNum = (u*k)/(R-L+1);  
116.             update(1, 1, n, p, arr[p], newNum, ++ptr);  
117.       }  
118.       for (int i = 1; i <= n; i++) printf("%d\n", arr[i]);  
119. }