SHARE
TWEET

Untitled

a guest Sep 18th, 2019 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define fe 2*x+1
  3. #define fd 2*x+2
  4. #define mid (l+r)/2
  5. #define infinito 10000000
  6. #define f first
  7. #define s second
  8.  
  9. using namespace std;
  10.  
  11. typedef pair<int,int> ii;
  12.  
  13. int posMaior=-2,posMenor=-1;
  14.  
  15. const int maxn = 100005;
  16.  
  17. vector<int> v[maxn];
  18. ii treeMin[4*maxn],treeMax[4*maxn];
  19.  
  20. ii menor(ii a, ii b){
  21.     return a.f < b.f ? a : b;
  22. }
  23. ii maior(ii a,ii b){
  24.     return a.f > b.f ? a : b;
  25. }
  26.  
  27.  
  28.  
  29. void build(int x,int l,int r){
  30.     if(l==r){
  31.         treeMin[x].s = l;
  32.         treeMax[x].s = l;
  33.         treeMin[x].f = v[l][0];
  34.         treeMax[x].f = v[l][0];
  35.         return;
  36.     }
  37.     build(fe,l,mid);
  38.     build(fd,mid+1,r);
  39.     treeMin[x] = menor(treeMin[fe],treeMin[fd]);
  40.     treeMax[x] = maior(treeMax[fe],treeMax[fd]);
  41. }
  42.  
  43. void update(int x, int l, int r, int pos, int valor){
  44.     if(l==r){
  45.         treeMin[x] = menor(treeMin[x],{valor,l});
  46.         treeMax[x] = maior(treeMax[x],{valor,l});
  47.         return;
  48.     }
  49.     if(pos<=mid) update(fe,l,mid,pos,valor);
  50.     else update(fd,mid+1,r,pos,valor);
  51.     treeMin[x] = menor(treeMin[fe],treeMin[fd]);
  52.     treeMax[x] = maior(treeMax[fe],treeMax[fd]);   
  53. }
  54. ii queryMin(int x, int l, int r, int ql, int qr){
  55.     if(ql > r or qr < l) return {infinito,-1};
  56.     if(ql<=l and r<=qr) return treeMin[x];
  57.     return menor(queryMin(fe,l,mid,ql,qr),queryMin(fd,mid+1,r,ql,qr));
  58. }
  59. ii queryMax(int x, int l, int r, int ql, int qr){
  60.     if(ql > r or qr < l) return {-1,-1};
  61.     if(ql<=l and r<=qr) return treeMax[x];
  62.     return maior(queryMax(fe,l,mid,ql,qr),queryMax(fd,mid+1,r,ql,qr));
  63. }
  64. int main(){
  65.     int n,m;
  66.     cin>>n>>m;
  67.     for(int i=0;i<n;i++){
  68.         int x;
  69.         cin>>x;
  70.         v[i].push_back(x);
  71.     };
  72.     build(0,0,n-1);
  73.     for(int i=0;i<m;i++){
  74.         int opera;
  75.         cin>>opera;
  76.         if(opera==1){
  77.             int p,b;
  78.             v[b-1].push_back(p);
  79.             cin>>p>>b;
  80.             update(0,0,n-1,b-1,p);
  81.         }
  82.         else{
  83.             int a,b;
  84.             cin>>a>>b;
  85.             ii menor = queryMin(0,0,n-1,a-1,b-1);
  86.             ii maior = queryMax(0,0,n-1,a-1,b-1);
  87.             if(menor.s != maior.s){
  88.                 cout<<maior.f - menor.f <<endl;
  89.             }
  90.             else{
  91.                 ii aux1,aux2;
  92.                 aux1 = menor(queryMin(0,0,n-1,maior.s+1,b-1),queryMin(0,0,n-1,a-1,maior.s-1));
  93.                 aux2 = maior(queryMax(0,0,n-1,maior.s+1,b-1),queryMax(0,0,n-1,a-1,maior.s-1));
  94.                 if(abs(aux1.f - maior.f)>= abs(aux2.f - menor.f)) cout<<abs(aux1.f - maior.f)<<endl;
  95.                 else cout<<abs(aux2.f - menor.f)<<endl;
  96.             }
  97.         }
  98.     }  
  99.     return 0;
  100. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top