fork(1) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. template <class POINTER_TYPE, class TYPE> class segment_tree
  5. {
  6.     TYPE *SegmentTree;
  7.     POINTER_TYPE base_capacity = 0;
  8.     TYPE (*g)(TYPE, TYPE);
  9.     TYPE neutral;
  10.  
  11.     TYPE result_on_segment_in
  12.     (
  13.         POINTER_TYPE v, POINTER_TYPE tl,
  14.         POINTER_TYPE tr, POINTER_TYPE l,
  15.         POINTER_TYPE r
  16.     )
  17.     {
  18.     	if (l > r) return neutral;
  19.     	else if (l == tl && r == tr) return SegmentTree[v];
  20.     	else
  21.     	{
  22.         	POINTER_TYPE tm = (tl + tr) / 2;
  23.         	return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
  24.         	result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
  25.         }
  26.     }
  27.  
  28.     void make_monoid_and_fill_rest(TYPE *NewTree, const POINTER_TYPE &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
  29.     {
  30.         g = f;
  31.         neutral = neutr;
  32.         for(POINTER_TYPE i = base_capacity+n; i < 2*base_capacity; ++i)
  33.         {
  34.             NewTree[i] = neutral;
  35.         }
  36.         for(POINTER_TYPE i = base_capacity-1; i > 0; --i)
  37.         {
  38.             NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
  39.         }
  40.         SegmentTree = NewTree;
  41.     }
  42.  
  43.     void fix_capacity(const POINTER_TYPE &base_array_size)
  44.     {
  45.         for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
  46.     }
  47.  
  48.     public:
  49.  
  50.     void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)
  51.     {
  52.         POINTER_TYPE base_size = end - begin;
  53.         fix_capacity(base_size);
  54.         TYPE *NewTree = new TYPE[base_capacity*2];
  55.         for(POINTER_TYPE i = 0; i < base_size; ++i)
  56.         {
  57.             NewTree[base_capacity+i] = begin[i];
  58.         }
  59.         make_monoid_and_fill_rest(NewTree, base_size, f, neutr);
  60.     }
  61.  
  62.     void read_and_construct(const POINTER_TYPE amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)
  63.     {
  64.         fix_capacity(amount_of_elements);
  65.         TYPE *NewTree = new TYPE[base_capacity*2];
  66.         for(POINTER_TYPE i = 0; i < amount_of_elements; ++i)
  67.         {
  68.             NewTree[base_capacity+i] = preprocessing_function();
  69.         }
  70.         make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
  71.     }
  72.  
  73.     void assign(const POINTER_TYPE index, const TYPE new_value)
  74.     {
  75.         SegmentTree[base_capacity+index] = new_value;
  76.         for (POINTER_TYPE i = (base_capacity+index)/2; i > 0; i /= 2)
  77.         {
  78.             SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
  79.         }
  80.     }
  81.  
  82.     TYPE result_on_segment (POINTER_TYPE l, POINTER_TYPE r)
  83.     {
  84.         return result_on_segment_in(1, 0, base_capacity-1, l, r);
  85.     }
  86. };
  87.  
  88. unsigned int f()
  89. {
  90.     unsigned int X;
  91.     cin >> X;
  92.     return X;
  93. }
  94.  
  95. unsigned int g(unsigned int a, unsigned int b)
  96. {
  97.     return max(a, b);
  98. }
  99.  
  100. int main()
  101. {
  102.     unsigned int n, m;
  103.     cin >> n;
  104.     segment_tree <unsigned int, unsigned int> D;
  105.     D.read_and_construct(n, f, g, 0);
  106.  
  107.     cin >> m;
  108.     unsigned char *type = new unsigned char[m];
  109.     unsigned int *a = new unsigned int[m], *b = new unsigned int[m], l, r;
  110.  
  111.     for (unsigned int i = 0; i < m; ++i)
  112.     {
  113.     	cin >> type[i] >> a[i];
  114.     	if (type[i] == '2') cin >> b[i];
  115.     }
  116.  
  117.     for (unsigned int i = 0; i < m; ++i)
  118.     {
  119.     	while (i < m)
  120.     	{
  121.     		if (type[i] == '2')
  122.     		{
  123.     			D.assign(a[i]-1, b[i]);
  124.     			++i;
  125.     		}
  126.     		else break;
  127.     	}
  128.     	cin >> l >> r;
  129.     	if (i < m)
  130.     	{
  131.     		if (D.result_on_segment(l-1, r-1) == a[i]) cout << "Yes\n";
  132.     		else cout << "No\n";
  133.     	}
  134.     }
  135. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5
1 2 4 3 1
5
1 4
1 5
2 3 5
1 1
1 4
1 3
1 5
5 5
2 4
stdout
copy 
Yes
No
Yes
No
https://ideone.com/sbG5Vn
Трое из Простаквашино
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!