fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define sp ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
  6. #define cps CLOCKS_PER_SEC
  7. #define mod (ll)1000000007
  8. #define f first
  9. #define s second
  10. #define debug1(x) cout<<x<<"\n"
  11. #define debug2(x,y) cout<<x<<" "<<y<<"\n"
  12. #define debug3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n"
  13. #define nl cout<<"\n";
  14. #define pq priority_queue
  15. #define inf 0x3f3f3f3f
  16. #define test cout<<"abcd\n";
  17. #define pi pair<int,int>
  18. #define pii pair<int,pi>
  19. #define pb push_back
  20. #define mxn 200005
  21. int a[mxn],b[mxn],block,n;
  22. ll ans[mxn],bit[mxn];
  23. map<int,int> mp;
  24.  
  25. struct node{
  26. int l,r,id;
  27. };
  28.  
  29. bool compare(node p,node q){
  30. int l=p.l/block;
  31. int r=q.l/block;
  32. if(l==r)
  33.     return p.r<q.r;
  34. return l<r;
  35. }
  36.  
  37. ll read(int x){
  38.     ll sum=0;
  39. while(x>0){
  40.         sum+=bit[x];
  41. x-=x&(-x);
  42. }
  43. return sum;}
  44.  
  45. void update(int x,ll val){
  46. while(x<=n){
  47.     bit[x]+=val;
  48.     x+=(x&(-x));
  49. }
  50. }
  51.  
  52. int main(){
  53. sp;
  54. int qq;
  55. cin>>n>>qq;
  56. block=267;
  57. for(int i=1; i<=n; ++i){
  58.     cin>>a[i];
  59.     mp[a[i]];
  60. }
  61. int x=0;
  62. for(auto &it:mp)
  63. it.s=++x;
  64. for(int i=1; i<=n; ++i)
  65.     a[i]=mp[a[i]];
  66. node q[qq+1];
  67. int l,r,id;
  68. for(int i=1; i<=qq; ++i){
  69.     cin>>q[i].l>>q[i].r;
  70. q[i].id=i;
  71. }
  72. sort(q+1,q+qq+1,compare);
  73. int curl=q[1].l,curr=curl-1;
  74. ll z=0;
  75. for(int i=1; i<=qq; ++i){
  76.     l=q[i].l;
  77.     r=q[i].r;
  78.     id=q[i].id;
  79.     while(curr<r){
  80.         ++curr;
  81.         z+=read(n)-read(a[curr]);
  82.         update(a[curr],1);
  83.     }
  84.     while(curl>l){
  85.         --curl;
  86.         z+=read(a[curl]-1);
  87.         update(a[curl],1);
  88.     }
  89.     while(curl<l){
  90.         z-=read(a[curl]-1);
  91.         update(a[curl],-1);
  92.         ++curl;
  93.     }
  94.     while(curr>r){
  95.         z-=read(n)-read(a[curr]);
  96.         update(a[curr],-1);
  97.         --curr;
  98.     }
  99.     ans[id]=z;
  100. }
  101. for(int i=1; i<=qq; ++i)
  102.     cout<<ans[i]<<"\n";
  103.  
  104. return 0;}
  105.  
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
5 3
1 4 2 3 1
1 2
3 5
1 5
stdout
copy 
0
2
5
https://ideone.com/kC1nTX
language:
C++ (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!