fork download
copy 
  1. /* Goal to be a Master */
  2.       #include <algorithm>
  3.       #include <bits/stdc++.h>
  4.       #include<string>
  5.       using namespace std;
  6.       #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  7.       #define vi vector<int>
  8.       #define ll long long
  9.       #define pb push_back
  10.       #define mp make_pair
  11.       #define all(x) x.begin(),x.end()
  12.  
  13.  const int maxN=1e5+1;
  14.  pair<int,int> st[4*maxN];
  15.  int a[maxN];
  16.  void build(int si,int ss,int se)
  17.  {
  18.      if(ss==se)
  19.      {
  20.          st[si]=mp(a[ss],1);
  21.          return ;
  22.  
  23.      } 
  24.      else{
  25.      int mid=(se+ss)/2;
  26.      build(2*si+1,ss,mid);
  27.      build(2*si+2,mid+1,se);
  28.      st[si].first=min(st[2*si+2].first,st[2*si+1].first);
  29.      if(st[2*si+2].first<st[2*si+1].first)
  30.       st[si].second=st[2*si+2].second;
  31.      else if(st[2*si+2].first>st[2*si+1].first)
  32.       st[si].second=st[2*si+1].second;
  33.      else
  34.       st[si].second=st[2*si+1].second+st[2*si+2].second;
  35.  
  36.  
  37.      }
  38.  }
  39.  void update(int si,int ss,int se,int idx,int data)
  40.  {
  41.      if(se<idx || ss>idx)
  42.       return;
  43.      if(se==ss)
  44.      {
  45.  
  46.  
  47.          if(ss==idx)
  48.           st[si]=mp(data,1);
  49.          else
  50.           st[si]=mp(a[ss],1); 
  51.          return;
  52.      }
  53.      else
  54.      {
  55.       int mid=(se+ss)/2;
  56.       update(2*si+1,ss,mid,idx,data);
  57.       update(2*si+2,mid+1,se,idx,data);
  58.      st[si].first=min(st[2*si+2].first,st[2*si+1].first);
  59.      if(st[2*si+2].first<st[2*si+1].first)
  60.       st[si].second=st[2*si+2].second;
  61.      else if(st[2*si+2].first>st[2*si+1].first)
  62.       st[si].second=st[2*si+1].second;
  63.      else
  64.       st[si].second=st[2*si+1].second+st[2*si+2].second;
  65.  
  66.      }
  67.  }
  68. pair<int,int> query(int si,int ss,int se,int qs,int qe)
  69. {
  70.     if(qs>qe)
  71.      return {INT_MAX,1};
  72.  
  73.     if(ss==qs && se==qe)
  74.      return st[si];
  75.     else
  76.     {
  77.         int mid=(ss+se)/2;
  78.         pair<int,int> l=query(2*si+1,ss,mid,qs,min(mid,qe));
  79.         pair<int,int> r=query(2*si+2,mid+1,se,max(mid+1,qs),qe);
  80.         st[si].first=min(l.first,r.first);
  81.      if(l.first<r.first)
  82.       st[si].second=l.second;
  83.      else if(l.first>r.first)
  84.       st[si].second=r.second;
  85.      else
  86.       st[si].second=l.second+r.second;
  87.      return st[si];
  88.     }
  89.  
  90. }
  91.       int main()
  92.       {
  93.         IOS  
  94.         int n,m;
  95.         cin>>n>>m;
  96.  
  97.         for(int i=0;i<n;i++)
  98.          cin>>a[i];
  99.         build(0,0,n-1); 
  100.         while(m--)
  101.         {
  102.             int x;
  103.             cin>>x;
  104.             if(x==1)
  105.             {
  106.                 int j,k;
  107.                 cin>>j>>k;
  108.                 update(0,0,n-1,j,k);
  109.             }
  110.             else
  111.             {
  112.                 int j,k;
  113.                 cin>>j>>k;
  114.                 pair<int,int> h=query(0,0,n-1,j,k-1);
  115.                 cout<<h.first<<" "<<h.second<<"\n";
  116.             }
  117.         } 
  118.         return 0;
  119.       }
Runtime error #stdin #stdout 0.77s 2095128KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VNbvP0
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

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!