pastebin

Paste Search Dynamic
Recent pastes
sort
  1. #include <iostream>
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define MAX 2100010
  6. #define MAXN 1000010
  7. #define INF 2000000000
  8. typedef pair<int, int> ii;
  9. typedef long long int ll;
  10.  
  11. int c[2*MAXN], w[2*MAXN], t[MAX], lazy[MAX], n, m;
  12. ii aa[MAXN], bb[MAXN];
  13.  
  14. ll intercala(int p, int q, int r, int v[]){
  15.         ll inv = 0;
  16.         int i=p, j=q, k=0;
  17.         while(i<q && j<r){
  18.                 if(v[i]>v[j]){
  19.                         inv += q-i;     
  20.                         w[k++]=v[j++];
  21.                 }
  22.                 else{
  23.                         w[k++]=v[i++];
  24.                 }
  25.         }
  26.         while(i<q){ w[k++]=v[i++]; }
  27.         while(j<r){ w[k++]=v[j++]; }
  28.         for(int i=p; i<r; i++){ v[i]=w[i-p]; }
  29.         return inv;
  30. }
  31.  
  32. ll merge(int p, int r, int v[]){
  33.         ll inv = 0;
  34.         if(p<(r-1)){
  35.                 int q = (p+r)/2;
  36.                 inv += merge(p, q, v);
  37.                 inv += merge(q, r, v);
  38.                 inv += intercala(p, q, r, v);
  39.         }
  40.         return inv;
  41. }
  42.  
  43. int lazyValue(int node, int L, int R){
  44.         return lazy[node] + t[node];
  45. }
  46.  
  47. void refresh(int node, int L, int R){
  48.         int nl = 2*node, nr = 2*node+1;
  49.         t[node] = lazyValue(node, L, R);
  50.         lazy[nl] += lazy[node];
  51.         lazy[nr] += lazy[node];
  52.         lazy[node] = 0;
  53. }
  54.  
  55. void st_build(int node, int L, int R){
  56.         if(L==R){
  57.                 t[node] = L+1;
  58.                 return ;
  59.         }
  60.         int nl = 2*node, nr = 2*node+1;
  61.         st_build(nl, L, (L+R)/2);
  62.         st_build(nr, (L+R)/2+1, R);
  63.         t[node] = min(t[nl], t[nr]);
  64. }
  65.  
  66. int st_query(int node, int L, int R, int i, int j){
  67.         if(R<i || j<L){
  68.                 return INF;
  69.         }
  70.         if(i<=L && R<=j){
  71.                 return lazyValue(node, L, R);
  72.         }
  73.         refresh(node, L, R);
  74.         int nl = 2*node, nr = 2*node+1;
  75.         int minl = st_query(nl, L, (L+R)/2, i, j);
  76.         int minr = st_query(nr, (L+R)/2+1, R, i, j);
  77.         return min(minl, minr);
  78. }
  79.  
  80. void st_update(int node, int L, int R, int pos, int sum){
  81.         if(R<pos){
  82.                 return;
  83.         }
  84.         if(pos<=L && R<=n){
  85.                 lazy[node] += sum;
  86.                 return ;
  87.         }
  88.         refresh(node, L, R);
  89.         int nl = 2*node, nr = 2*node+1;
  90.         st_update(nl, L, (L+R)/2, pos, sum);
  91.         st_update(nr, (L+R)/2+1, R, pos, sum);
  92.         int minl = lazyValue(nl, L, (L+R)/2);
  93.         int minr = lazyValue(nr, (L+R)/2+1, R);
  94.         t[node] = min(minl, minr);
  95. }
  96.  
  97. void st_build(){ st_build(1, 0, n); }
  98. void st_create(){
  99.         memset(lazy, 0, sizeof(lazy));
  100.         st_build();
  101. }
  102. void st_update(int pos, int sum){ st_update(1, 0, n, pos, sum); }
  103. int st_query(int i, int j){ return st_query(1, 0, n, i, j); }
  104.  
  105. int main() {
  106.         int tt;
  107.         scanf("%d", &tt);
  108.         for(int cas=1; cas<=tt; cas++){
  109.                 scanf("%d %d", &n, &m);
  110.                 for(int i=0; i<n; i++){
  111.                         scanf("%d", &aa[i+1].first);
  112.                         aa[i+1].second = i+1;
  113.                 }
  114.                 for(int i=0; i<m; i++){
  115.                         scanf("%d", &bb[i].first);
  116.                         bb[i].second = 0;
  117.                 }
  118.                 sort(bb, bb+m);
  119.                 int qcur = 1, cur = bb[0].first, q = 0;
  120.                 for(int i=1; i<m; i++){
  121.                         if(bb[i].first != cur){
  122.                                 bb[q++] = ii(cur, qcur);
  123.                                 qcur = 1;
  124.                                 cur = bb[i].first;
  125.                         }
  126.                         else{
  127.                                 qcur++;
  128.                         }
  129.                 }
  130.                 bb[q++] = ii(cur, qcur);
  131.                 sort(bb, bb+q);
  132.                 int k=0;
  133.                 for(int i=0; i<q; i++){
  134.                         for(int j=0; j<bb[i].second; j++){
  135.                                 c[k++] = bb[i].first;
  136.                         }
  137.                 }
  138.                 for(int i=0; i<n; i++){
  139.                         c[i+m] = aa[i+1].first;
  140.                 }
  141.                 sort(aa+1, aa+n+1);
  142.                
  143.                 st_create();
  144.                 st_update(0, -1);
  145.                
  146.                 int i=1;
  147.                 ll sum = 0;
  148.                
  149.                 for(int j=0; j<q; j++){
  150.                         while(i<=n && aa[i].first<bb[j].first){
  151.                                 st_update(aa[i].second, -2);
  152.                                 i++;
  153.                         }
  154.                         int beg = i;
  155.                         while(i<=n && aa[i].first==bb[j].first){
  156.                                 st_update(aa[i].second, -1);
  157.                                 i++;
  158.                         }
  159.                        
  160.                         ll qntb = bb[j].second;
  161.                         ll queryb = (ll) st_query(0, n);
  162.                         sum += qntb*queryb;
  163.                        
  164.                         int k=beg;
  165.                         for(; k<i; k++){
  166.                                 st_update(aa[k].second, +1);
  167.                         }
  168.                         i = beg;
  169.                 }
  170.                 ll mc = merge(0, n+m, c);
  171.                 printf("%lldn", sum + mc);
  172.         }
  173.         return 0;
  174. }
  175.  
Parsed in 0.019 seconds