fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  3. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  4. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  5. #define ll long long
  6. #define el "\n"
  7. #define fi first
  8. #define se second
  9. #define M 1000000007
  10. #define MAXN 101001
  11. #define NAME "dizalo"
  12. using namespace std;
  13.  
  14. ll n, q, v ;
  15. ll a[MAXN] , b[MAXN] , c[MAXN] , d[MAXN] , g[MAXN] ;
  16. map<ll, ll> e, f ;
  17.  
  18. struct FEN {
  19.     ll bit[MAXN];
  20.  
  21.     void update(ll pos, ll c) {
  22.         while (pos < MAXN ) {
  23.             bit[pos] += c;
  24.             pos += pos & - pos ;
  25.         }
  26.     }
  27.     ll get(ll pos) {
  28.         ll res = 0;
  29.         while (pos) {
  30.             res += bit[pos];
  31.             pos -= pos & -pos ;
  32.         }
  33.         return res;
  34.     }
  35.     ll rem(ll pos) {
  36.         return get(MAXN - 1 ) - get(pos);
  37.     }
  38. };
  39.  
  40. FEN t1, t2, t3, t4;
  41.  
  42. void init() {
  43.     cin >> n >> q ;
  44.     FOR(i, 1, n ) {
  45.         cin >> a[i] ;
  46.         b[a[i]] = i ;
  47.         e[i] = 1 ;
  48.     }
  49.     FOR(i, 1, q ) {
  50.         cin >> c[i];
  51.         d[i] = a[c[i]];
  52.         e.erase(c[i] );
  53.     }
  54. }
  55.  
  56. void solve() {
  57.     ll cur = q;
  58.     for(auto s = e.begin(); s != e.end(); s++) {
  59.         cur++ ;
  60.         c[cur ] = (s->fi);
  61.         d[cur] = a[c[cur]] ;
  62.     }
  63.  
  64.     e.clear();
  65.  
  66.     FORD(u , n , 1 ) {
  67.         f[0] = 0;
  68.         auto x = f.upper_bound(d[u]);
  69.         x--;
  70.         if((x->se) < c[u]) {
  71.             while(true) {
  72.                 auto y = f.upper_bound(d[u]);
  73.  
  74.                 if(y == f.end()) break ;
  75.                 if((y->se) > c[u]) break ;
  76.  
  77.                 v -= t1.get(y->se - 1);
  78.                 v += t4.get(y->fi - 1);
  79.                 t2.update(y->se, -1);
  80.                 t3.update(y->fi, -1);
  81.                 f.erase(y);
  82.             }
  83.  
  84.             v += t1.get(c[u] - 1);
  85.             v -= t4.get(d[u] - 1);
  86.             t2.update(c[u], 1);
  87.             t3.update(d[u], 1);
  88.             f[d[u]] = c[u];
  89.         }
  90.  
  91.         f.erase(0);
  92.         t1.update(c[u], 1);
  93.         t4.update(d[u], 1);
  94.         v += t2.rem(c[u]);
  95.         v -= t3.rem(d[u]);
  96.         g[u] = v + n + 1 - u;
  97.     }
  98.  
  99.     FOR(i, 1, q + 1 ) cout << g[i] << " " ;
  100.     cout << el ;
  101. }
  102.  
  103.  
  104.  int main() {
  105.     freopen(NAME".inp" , "r" , stdin);
  106.     freopen(NAME".out" , "w", stdout) ;
  107.     ios_base::sync_with_stdio(0);
  108.     cin.tie(0);
  109.     cout.tie(0);
  110.     int t = 1; // cin >> t ;
  111.     while(t--) {
  112.         init();
  113.         solve();
  114.     }
  115.     return (0);
  116. }
  117.  
Success #stdin #stdout 0.01s 5856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eiVY8F
language:
C++14 (gcc 8.3)
created:
7 hours 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!