Advertisement
GerONSo

Untitled

Jun 5th, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.31 KB | None | 0 0
  1. #define pragma
  2.  
  3. #ifdef pragma
  4. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
  5. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6. #endif // pragma
  7.  
  8. #include<bits/stdc++.h>
  9. #include <ext/pb_ds/assoc_container.hpp>
  10. #include <ext/pb_ds/tree_policy.hpp>
  11.  
  12. #define ll long long
  13. #define all(x) begin(x), end(x)
  14. #define pb push_back
  15. #define x first
  16. #define y second
  17. #define int long long
  18. #define zero(two) memset(two, 0, sizeof(two))
  19.  
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23.  
  24. typedef vector<int> vi;
  25. typedef vector<bool> vb;
  26. typedef pair<int, int> pii;
  27. typedef long double ld;
  28. typedef vector<vi> matrix;
  29. template<typename T>
  30. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31.  
  32. const ld PI = atan2(0, -1);
  33.  
  34. void seriy() {
  35. ios::sync_with_stdio(0);
  36. cin.tie(0);
  37. cout.tie(0);
  38. cout << fixed << setprecision(10);
  39. #if _offline
  40. freopen("input.txt", "r", stdin);
  41. freopen("output.txt", "w", stdout);
  42. #endif
  43. }
  44.  
  45. const int MAXN = 3e5 + 10;
  46. const int INF = 1e18 + 7;
  47. const int MAXLOG = 20;
  48. const int MOD = 998244353;
  49. const int BASE = 47;
  50.  
  51. struct p {
  52. int l, r, x;
  53. };
  54.  
  55. struct node {
  56. int sum, op;
  57. };
  58.  
  59. vector<node> t;
  60. vi kek, a, lg(MAXN);
  61. int tt[MAXN][MAXLOG], mmn = INF;
  62. int n, k;
  63.  
  64. void push(int v) {
  65. if(t[v].op != -1) {
  66. t[v * 2 + 1].op = t[v].op;
  67. t[v * 2 + 2].op = t[v].op;
  68. t[v].sum = t[v].op;
  69. t[v].op = -1;
  70. }
  71. }
  72.  
  73. int getmn(int l, int r) {
  74. l = kek[l];
  75. r = kek[r];
  76. // cerr << l << " " << r << " ";
  77. if(r - l + 1 >= n) {
  78. // cerr << mmn << '\n';
  79. return mmn;
  80. }
  81. else {
  82. l = (l - 1) % n;
  83. r = (r - 1) % n;
  84. if(l <= r) {
  85. int len = r - l + 1;
  86. int llg = lg[len];
  87. int res = min(tt[l][llg], tt[r - (1ll << llg) + 1][llg]);
  88. // cerr << res << '\n';
  89. return res;
  90. }
  91. else {
  92. int len = n - l;
  93. int llg = lg[len];
  94. int res = min(tt[l][llg], tt[n - (1ll << llg)][llg]);
  95.  
  96. int len1 = r + 1;
  97. int llg1 = lg[len];
  98. int res1 = min(tt[0][llg], tt[r - (1ll << llg) + 1][llg]);
  99. // cerr << min(res, res1) << '\n';
  100. return min(res, res1);
  101. }
  102. }
  103. }
  104.  
  105. void build(int v, int tl, int tr) {
  106. if(tl == tr) {
  107. // cerr << tl << " " << kek[tl] << '\n';
  108. t[v].sum = a[(kek[tl] - 1) % n];
  109. return;
  110. }
  111. int tm = (tl + tr) >> 1;
  112. build(v * 2 + 1, tl, tm);
  113. build(v * 2 + 2, tm + 1, tr);
  114. t[v].sum = getmn(tl, tr);
  115. }
  116.  
  117. int get(int v, int tl, int tr, int l, int r) {
  118. push(v);
  119. if(tl > r || tr < l) {
  120. return INF;
  121. }
  122. if(tl >= l && tr <= r) {
  123. // cerr << tl << " " << tr << " " << t[v].sum << '\n';
  124. return t[v].sum;
  125. }
  126. int tm = (tl + tr) >> 1;
  127. int left = get(v * 2 + 1, tl, tm, l, r);
  128. int right = get(v * 2 + 2, tm + 1, tr, l, r);
  129. return min(left, right);
  130. }
  131.  
  132. void update(int v, int tl, int tr, int l, int r, int val) {
  133. push(v);
  134. if(tl > r || tr < l) {
  135. // cerr << tl << " " << tr << " " << t[v].sum << '\n';
  136. return;
  137. }
  138. if(tl >= l && tr <= r) {
  139. t[v].op = val;
  140. push(v);
  141. cerr << tl << " " << tr << " " << t[v].sum << '\n';
  142. return;
  143. }
  144. int tm = (tl + tr) >> 1;
  145. update(v * 2 + 1, tl, tm, l, r, val);
  146. update(v * 2 + 2, tm + 1, tr, l, r, val);
  147. t[v].sum = min(t[v * 2 + 1].sum, t[v * 2 + 2].sum);
  148. cerr << tl << " " << tr << " " << t[v].sum << '\n';
  149. }
  150.  
  151. signed main() {
  152. seriy();
  153.  
  154. cin >> n >> k;
  155. a.resize(n);
  156. for(int i = 0; i < n; i++) {
  157. cin >> a[i];
  158. mmn = min(mmn, a[i]);
  159. tt[i][0] = a[i];
  160. }
  161. lg[1] = 0;
  162. for(int i = 2; i < MAXN; i++) {
  163. lg[i] = lg[i - 1];
  164. if((i & (i - 1)) > 0) {
  165. lg[i]++;
  166. }
  167. }
  168.  
  169.  
  170. for(int i = 1; i < MAXLOG; i++) {
  171. for(int j = 0; j < n; j++) {
  172. if(j + (1ll << i) <= n) tt[j][i] = min(tt[j][i - 1], tt[j + (1ll << (i - 1))][i - 1]);
  173. else tt[j][i] = -1;
  174. }
  175. }
  176.  
  177.  
  178. int q;
  179. cin >> q;
  180. vector<p> rq;
  181. for(int i = 0; i < q; i++) {
  182. int tp;
  183. cin >> tp;
  184. if(tp == 1) {
  185. int l, r, x;
  186. cin >> l >> r >> x;
  187. rq.pb({l, r, x});
  188. kek.pb(l);
  189. kek.pb(r);
  190. }
  191. else {
  192. int l, r;
  193. cin >> l >> r;
  194. kek.pb(l);
  195. kek.pb(r);
  196. rq.pb({l, r, -1});
  197. }
  198. }
  199. sort(all(kek));
  200. kek.resize(unique(all(kek)) - kek.begin());
  201. t.resize(8 * kek.size(), {INF, -1});
  202. build(0, 0, kek.size() - 1);
  203. for(int i = 0; i < q; i++) {
  204. if(rq[i].x == -1) {
  205. int left = lower_bound(all(kek), rq[i].l) - kek.begin();
  206. int right = lower_bound(all(kek), rq[i].r) - kek.begin();
  207. cout << get(0, 0, kek.size() - 1, left, right) << '\n';
  208. }
  209. else {
  210. int left = lower_bound(all(kek), rq[i].l) - kek.begin();
  211. int right = lower_bound(all(kek), rq[i].r) - kek.begin();
  212. update(0, 0, kek.size() - 1, left, right, rq[i].x);
  213. }
  214. }
  215. return 0;
  216. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement