fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. ll segtree[4*20005];
  6. ll mx[4*20005];
  7. ll arr[20005];
  8. ll brr[20005];
  9. ll ans[20005];
  10. ll k,sum;
  11. struct point
  12. {
  13.     ll l,r,id;
  14. } q[20005];
  15.  
  16. bool cmp(point &a,point &b)
  17. {
  18.     ll blocka=a.l/k,blockb=b.l/k;
  19.     if(blocka==blockb)
  20.         return a.r<b.r;
  21.     return blocka<blockb;
  22. }
  23.  
  24. void build(ll n,ll b,ll e)
  25. {
  26.     if(b==e)
  27.     {
  28.         mx[n]=brr[b];
  29.         return ;
  30.     }
  31.     ll mid=(b+e)/2;
  32.     build(2*n,b,mid);
  33.     build(2*n+1,mid+1,e);
  34.  
  35.     mx[n]=max(mx[2*n],mx[2*n+1]);
  36. }
  37.  
  38. void update(ll n,ll b,ll e,ll val,ll on)
  39. {
  40.     if(b==e)
  41.     {
  42.         if(on==1){
  43.             segtree[n]++;
  44.         }
  45.         else{
  46.             segtree[n]--;
  47.         }
  48.         return ;
  49.     }
  50.     ll mid=(b+e)/2;
  51.     ll left=2*n;
  52.     ll right=2*n+1;
  53.  
  54.     if(mx[left]<val&&mx[right]>=val)
  55.         update(right,mid+1,e,val,on);
  56.     else
  57.         update(left,b,mid,val,on);
  58.     segtree[n]=segtree[left]+segtree[right];
  59. }
  60.  
  61. ll query(ll n,ll b,ll e,ll val)
  62. {
  63.     if(e==b){   return 0;   }
  64.     ll mid=(b+e)/2;
  65.     ll left=2*n;
  66.     ll right=2*n+1;
  67.     if(mx[left]>=val){
  68.         return query(left,b,mid,val);
  69.     }
  70.     else{
  71.         return segtree[left]+query(right,mid+1,e,val);
  72.     }
  73. }
  74.  
  75. ll query1(ll n,ll b,ll e,ll val)
  76. {
  77.     if(e==b){   return 0;   }
  78.  
  79.     ll mid=(b+e)/2;
  80.     ll left=2*n;
  81.     ll right=2*n+1;
  82.     if(mx[left]>=val){
  83.         return segtree[right]+query1(left,b,mid,val);
  84.     }
  85.     else{
  86.         return query1(right,mid+1,e,val);
  87.     }
  88. }
  89.  
  90. void leftadd(ll pos,ll len)
  91. {
  92.     sum+=query(1,1,len,arr[pos]);
  93.     update(1,1,len,arr[pos],1);
  94. }
  95. void rightadd(ll pos,ll len)
  96. {
  97.     sum+=query1(1,1,len,arr[pos]);
  98.     update(1,1,len,arr[pos],1);
  99. }
  100. void leftrmv(ll pos,ll len)
  101. {
  102.     sum-=query(1,1,len,arr[pos]);
  103.     update(1,1,len,arr[pos],0);
  104. }
  105. void rightrmv(ll pos,ll len)
  106. {
  107.     sum-=query1(1,1,len,arr[pos]);
  108.     update(1,1,len,arr[pos],0);
  109. }
  110.  
  111. int main()
  112. {
  113.     ll i,j,n,m,t;
  114.     set<ll>s;
  115.     scanf("%lld",&n);
  116.     k=sqrt(n);
  117.     for(i=1; i<=n; i++)
  118.     {
  119.         scanf("%lld",&arr[i]);
  120.         s.insert(arr[i]);
  121.     }
  122.     ll len=s.size();
  123.     set< ll >::iterator it=s.begin();
  124.     for(i=1; i<=len; i++)
  125.     {
  126.         brr[i]=*it;
  127.         it++;
  128.     }
  129.     build(1,1,len);
  130.     scanf("%lld",&t);
  131.     for(i=1; i<=t; i++)
  132.     {
  133.         scanf("%lld%lld",&q[i].l,&q[i].r);
  134.         q[i].id=i;
  135.     }
  136.     sort(q+1,q+t+1,cmp);
  137.  
  138.     ll l=1,r=0;
  139.     for(i=1; i<=t; i++)
  140.     {
  141.         while(l>q[i].l){     leftadd(--l,len);   }
  142.         while(l<q[i].l){     leftrmv(l++,len);   }
  143.         while(r>q[i].r){    rightrmv(r--,len);  }
  144.         while(r<q[i].r){    rightadd(++r,len);  }
  145.         ans[q[i].id]=sum;
  146.     }
  147.  
  148.     for(i=1; i<=t; i++)
  149.     {
  150.         printf("%lld\n",ans[i]);
  151.     }
  152. }
  153.  
Runtime error #stdin #stdout 0.01s 5596KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/oy1zxH
language:
C++14 (gcc 8.3)
created:
4 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!