Advertisement
Guest User

Untitled

a guest
Sep 25th, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 100010;
  7. int a[N];
  8. int tm[4 * N], tx[4 * N];
  9.  
  10. void change(int v, int L, int R, int l, int r, int x) {
  11.     if (L == l && R == r) {
  12.         tx[v] = x;
  13.         tm[v] = x;
  14.     }
  15.     else {
  16.         int M = (L + R) / 2;
  17.         if (tx[v] != -1) {
  18.             tx[v * 2 + 1] = tx[v];
  19.             tx[v * 2 + 2] = tx[v];
  20.         }
  21.         tx[v] = -1;
  22.  
  23.         if (l <= M) {
  24.             change(v * 2 + 1, L, M, l, min(M, r), x);
  25.         }
  26.         if (r > M) {
  27.             change(v * 2 + 2, M + 1, R, max(M + 1, l), r, x);
  28.         }
  29.  
  30.         tm[v] = min(tm[v * 2 + 1], tm[v * 2 + 2]);
  31.     }
  32. }
  33.  
  34. void get(int v, int L, int R, int l, int r) {
  35.     if (L == l && R == r) {
  36.         cout << tm[v] << ' ';
  37.         return;
  38.     }
  39.     if (tx[v] != -1){
  40.         cout << tx[v] << ' ';
  41.         return;
  42.     }
  43.  
  44.     int M = (L + R) / 2;
  45.     if (l <= M) {
  46.         get(v * 2 + 1, L, M, l, min(M, r));
  47.     }
  48.     if (r > M) {
  49.         get(v * 2 + 2, M + 1, R, max(M + 1, l), r);
  50.     }
  51. }
  52.  
  53. void build(int v, int L, int R) {
  54.     if (L == R) {
  55.         tx[v] = a[L];
  56.         tm[v] = a[L];
  57.     }
  58.     else {
  59.         int M = (L + R) / 2;
  60.         build(v * 2 + 1, L, M);
  61.         build(v * 2 + 2, M + 1, R);
  62.         tm[v] = min(tm[v * 2 + 1], tm[v * 2 + 2]);
  63.     }
  64. }
  65.  
  66. int main() {
  67.     ios_base::sync_with_stdio(0);
  68.     cin.tie(0);
  69.     cout.tie(0);
  70.  
  71.     int n, m;
  72.     cin >> n;
  73.     for (int i = 0; i < n; i++) {
  74.         cin >> a[i];
  75.     }
  76.     build(0, 0, n - 1);
  77.  
  78.     cin >> m;
  79.     for (int i = 0; i < m; i++) {
  80.         int op, l, r, val;
  81.         cin >> op;
  82.         if (op == 1) {
  83.             cin >> l >> r;
  84.             get(0, 0, n - 1, l - 1, r - 1);
  85.         }
  86.         else {
  87.             cin >> l >> r >> val;
  88.             change(0, 0, n - 1, l - 1, r - 1, val);
  89.         }
  90.     }
  91.  
  92.     system("pause");
  93.     return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement