fork download 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. #pragma GCC optimize("Ofast,unroll-loops")
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. template<class T> using oset= tree<T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>;
  8. int n , Q=18 , q;
  9. struct block{
  10.     int cnt;
  11.     vector<int> mas;
  12.     vector<int> smas;
  13. };
  14. vector<int> mas;
  15. vector<vector<int> > t;
  16. vector<block> blocks;
  17. vector<vector<int> > m;
  18. vector<vector<int> > pref_m;
  19. vector<vector<int> > pref_stolb;
  20. void build(int v , int l , int r){
  21.     if(l==r){
  22.         t[v].push_back(mas[l]);
  23.     }
  24.     else{
  25.     int mid=(l+r)/2;
  26.     build(v*2 , l , mid);
  27.     build(v*2+1 , mid+1 , r);
  28.     int l1=0;
  29.     int l2=0;
  30.     while(l1!=t[v*2].size()||l2!=t[v*2+1].size()){
  31.         if(l1==t[v*2].size()){
  32.         t[v].push_back(t[v*2+1][l2]);
  33.         l2++;
  34.         }
  35.         else{
  36.             if(l2==t[v*2+1].size()){
  37.                 t[v].push_back(t[v*2][l1]);
  38.                 l1++;
  39.             }
  40.             else{
  41.                 if(t[v*2][l1]<=t[v*2+1][l2]){
  42.                     t[v].push_back(t[v*2][l1]);
  43.                     l1++;
  44.                 }
  45.                 else{
  46.                     t[v].push_back(t[v*2+1][l2]);
  47.                     l2++;
  48.                 }
  49.             }
  50.         }
  51.     }
  52.     }
  53. }
  54. int dih_t(int v , int x){
  55.     int siz=t[v].size();
  56.     int l=0 , r=siz-1;
  57.     int ans=0;
  58.     //cout << l << "-" << r << " " << siz << endl;
  59.     while(l<=r){
  60.             int mid=(l+r)/2;
  61.             if(t[v][mid]>x){
  62.                 ans=siz-mid;
  63.                 r=mid-1;
  64.             }
  65.             else{
  66.                 l=mid+1;
  67.             }
  68.     }
  69.    // cout << ans << ";" << endl;
  70.     return ans;
  71. }
  72. int find_ans(int v , int l , int r , int tl , int tr , int x){
  73.    /*cout << v << endl;
  74.   system("pause");*/
  75.     if(tl==l&&tr==r){
  76.         return dih_t(v , x);
  77.     }
  78.     else{
  79.         int mid=(l+r)/2;
  80.         if(tr<=mid){
  81.             return find_ans(v*2 , l , mid , tl , tr , x);
  82.         }
  83.         if(tl>mid){
  84.             return find_ans(v*2+1 , mid+1 , r , tl , tr , x);
  85.         }
  86.         return find_ans(v*2 , l , mid , tl , mid , x)+find_ans(v*2+1 , mid+1 , r , mid+1 , tr , x);
  87.     }
  88. }
  89. int find_blocks(int a , int b){
  90.     int ans=0;
  91.     if(a==b){
  92.         return blocks[a].cnt;
  93.     }
  94.     if(a<b){
  95.         swap(a , b);
  96.     }
  97.     else{
  98.         int l1=0 , l2=0;
  99.         while(l1!=blocks[a].smas.size()&&l2!=blocks[b].smas.size()){
  100.             if(blocks[a].smas[l1]>blocks[b].smas[l2]){
  101.                 ans+=blocks[a].smas.size()-l1;
  102.                 l2++;
  103.             }
  104.             else{
  105.                 l1++;
  106.             }
  107.         }
  108.     }
  109.     return ans;
  110. }
  111. int find_cnt(int a){
  112.     if(blocks[a].mas.size()==0){
  113.         return 0;
  114.     }
  115.     oset<int> s;
  116.     int ans=0;
  117.     for(int i=0;i<blocks[a].mas.size();i++){
  118.         ans+=s.size()-s.order_of_key(blocks[a].mas[i]);
  119.         s.insert(blocks[a].mas[i]);
  120.     }
  121.     return ans;
  122. }
  123. int pref_ans=0;
  124. void solve(){
  125.     int ans=0;
  126.     int l , r;
  127.     cin >> l >> r;
  128.     l=((pref_ans+l-1)%n)+1;
  129.     r=((pref_ans+r-1)%n)+1;
  130.     l--;
  131.     r--;
  132.     if(l>r){
  133.         swap(l , r);
  134.     }
  135.    // cout << l << " " << r << endl;
  136.     int q_min=999999 , q_max=-1;
  137.     for(int i=l;i<=r;){
  138.         if(i%Q==0&&i+Q-1<=r){
  139.         ans+=blocks[i/Q].cnt;
  140.         q_min=min(q_min , i/Q);
  141.         q_max=i/Q;
  142.         i+=Q;
  143.         }
  144.         else{
  145.             if(i!=l){
  146.             ans+=find_ans(1 , 0 , n-1 , l , i-1 , mas[i]);
  147.      //       cout << ans << endl;
  148.             }
  149.             //cout << "bebraa" << endl;
  150.             i++;
  151.         }
  152.     }
  153.     if(q_min!=999999){
  154.             if(q_min==0){
  155.                 ans+=pref_m[q_max][q_max];
  156.             }
  157.             else{
  158.         ans+=pref_m[q_max][q_max]-pref_m[q_max][q_min-1]-pref_m[q_min][q_max-1];
  159.             }
  160.     }
  161.     cout << ans << endl;
  162.     pref_ans=ans;
  163. }
  164. int main(){
  165.     cin >> n;
  166.     mas.resize(n+1);
  167.     t.resize(4*(n+1)+1);
  168.     pref_m.resize(n/Q+1 , vector<int>(n/Q+1));
  169.     blocks.resize(n/Q+1);
  170.     m.resize(n/Q+1 , vector<int>(n/Q+1));
  171.     pref_stolb.resize(n/Q+1 , vector<int>(n/Q+1));
  172.     for(int i=0;i<n;i++){
  173.         cin >> mas[i];
  174.     }
  175.     build(1 , 0 , n-1);
  176.   /*  for(int i=1;i<t.size();i++){
  177.         if(t[i].size()!=0){
  178.                 cout << i << ": ";
  179.             for(int j=0;j<t[i].size();j++){
  180.                 cout << t[i][j] << " ";
  181.             }
  182.             cout << endl;
  183.         }
  184.     }*/
  185.     for(int i=0;i<n;i++){
  186.         blocks[i/Q].mas.push_back(mas[i]);
  187.     }
  188.     for(int i=0;i<=n/Q;i++){
  189.         if(blocks[i].mas.size()!=0){
  190.         blocks[i].smas=blocks[i].mas;
  191.         sort(blocks[i].smas.begin() , blocks[i].smas.end());
  192.         }
  193.     }
  194.     for(int i=0;i<=n/Q;i++){
  195.             if(blocks[i].mas.size()!=0){
  196.         blocks[i].cnt=find_cnt(i);
  197.             }
  198.     }
  199.     for(int i=0;i<=n/Q;i++){
  200.         for(int j=0;j<=n/Q;j++){
  201.             m[i][j]=find_blocks(i , j);
  202.             if(i==0){
  203.                 pref_stolb[i][j]=m[i][j];
  204.             }
  205.             else{
  206.                 pref_stolb[i][j]=pref_stolb[i-1][j]+m[i][j];
  207.             }
  208.             if(j==0){
  209.                 pref_m[i][j]=pref_stolb[i][j];
  210.             }
  211.             else{
  212.                 pref_m[i][j]=pref_stolb[i][j]+pref_m[i][j-1];
  213.             }
  214.         }
  215.     }
  216.     cin >> q;
  217.     while(q--){
  218.         solve();
  219.     }
  220.     return 0;
  221. }
  222.  
Runtime error #stdin #stdout 0.68s 2095972KB
comments (?)
stdin 
0
0
stdout 
Standard output is empty
https://ideone.com/RwxKZB
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!