fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int BLOCK,n,q,a[100001],temp[100001],tree[400001];
  4. long long cans=0;
  5. long long ans[100001];
  6. void add(int node,int s,int e,int val)
  7. {
  8.     if(s==e)
  9.     {
  10.         tree[node]++;
  11.         return;
  12.     }
  13.     int m = (s+e)/2;
  14.  
  15.     if( val<=m)
  16.         add(2*node,s,m,val);
  17.     else
  18.         add(2*node+1,m+1,e,val);
  19.     tree[node] = tree[2*node]+tree[2*node+1];
  20.     return;
  21. }
  22. void del(int node,int s,int e,int val)
  23. {
  24.     if(s==e)
  25.     {
  26.         tree[node]--;
  27.         return ;
  28.     }
  29.     int m = (s+e)/2;
  30.  
  31.     if( val<=m)
  32.         del(2*node,s,m,val);
  33.     else
  34.         del(2*node+1,m+1,e,val);
  35.     tree[node] = tree[2*node]+tree[2*node+1];
  36.     return;
  37. }
  38. int query(int node,int s,int e,int l,int r)
  39. {
  40.     if(e<l || r<s)
  41.     return 0;
  42.  
  43.     if(s>=l && e<=r)
  44.         return tree[node];
  45.  
  46.     int m =(s+e)/2;
  47.     return query(2*node,s,m,l,r)+query(2*node+1,m+1,e,l,r);
  48. }
  49. bool cmp(const pair< pair<int,int>,int> &a,const pair< pair<int,int>,int> &b)
  50. {
  51.     int l1 = a.first.first/BLOCK;
  52.     int l2 = b.first.first/BLOCK;
  53.     if(l1 != l2)
  54.         return (l1<l2);
  55.     return (a.first.second < b.first.second);
  56. }
  57. int main()
  58. {
  59.     scanf("%d %d",&n,&q);
  60.     BLOCK = static_cast<int>(sqrt(n));
  61.     for(int i=0;i<n;i++){
  62.         scanf("%d", &a[i]);
  63.         temp[i]=a[i];
  64.     }
  65.     sort(temp,temp+n);
  66.     for(int i=0;i<n;i++)
  67.         a[i]= lower_bound(temp,temp+n,a[i])-temp +1;
  68.     vector< pair< pair<int,int>,int> > qry;
  69.     for(int i=0;i<q;i++)
  70.     {
  71.         int l,r;
  72.         scanf("%d %d",&l,&r);
  73.         l--;
  74.         r--;
  75.         qry.push_back(make_pair(make_pair(l,r),i));
  76.     }
  77.     sort(qry.begin(),qry.end(),cmp);
  78.  
  79.     int ml = 0,mr = -1;
  80.     cans=0;
  81.     for(int i=0;i<q;i++)
  82.     {
  83.         int l=qry[i].first.first,r=qry[i].first.second;
  84.         while(mr < r)
  85.         {
  86.             mr++;
  87.             if( a[mr] != n )
  88.                 cans += query(1,1,n,a[mr]+1,n);
  89.             add(1,1,n,a[mr]); 
  90.         }
  91.         while(ml > l)
  92.         {
  93.             ml--;
  94.             if(a[ml] != 1)
  95.             {
  96.                 cans += query(1,1,n,1,a[ml]-1);
  97.             }
  98.             add(1,1,n,a[ml]);
  99.         }
  100.         while(mr > r)
  101.         {
  102.             if( a[mr] != n )
  103.                 cans -= query(1,1,n,a[mr]+1,n);
  104.             del(1,1,n,a[mr]);
  105.             mr--;
  106.         }
  107.         while(ml < l)
  108.         {            
  109.             if(a[ml] != 1)
  110.             {
  111.                 cans -= query(1,1,n,1,a[ml]-1);
  112.             }
  113.             del(1,1,n,a[ml]);
  114.             ml++;
  115.         }
  116.         ans[qry[i].second]=cans;
  117.     }
  118.     for(int i=0;i<q;i++)
  119.     {
  120.         printf("%lld\n", ans[i]);
  121.     }
  122.     return 0;
  123. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
5 3
1 4 2 3 1
1 2
3 5
1 5
stdout
copy 
0
2
5
https://ideone.com/XoFsHQ
language:
C++14 (gcc 8.3)
created:
6 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!