fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. //#include <ext/pb_ds/assoc_container.hpp>
  4. //using namespace __gnu_pbds;
  5. //typedef tree<int,null_type,less<int>,rb_tree_tag,
  6. //tree_order_statistics_node_update> indexed_set;
  7. #define pb push_back
  8. #define eb emplace_back
  9. #define mp make_pair
  10. #define pii pair<int,int>
  11. #define pll pair<long long , long long>
  12. #define vi vector<int>
  13. #define vpii vector<pii>
  14. #define SZ(x) ((int)(x.size()))
  15. #define fi first
  16. #define se second
  17. #define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
  18. #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
  19. #define IN(x,y) ((y).find((x))!=(y).end())
  20. #define ALL(t) t.begin(),t.end()
  21. #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
  22. #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
  23. #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
  24. #define REMAX(a,b) (a)=max((a),(b));
  25. #define REMIN(a,b) (a)=min((a),(b));
  26. #define dem(x) __builtin_popcount(x)
  27. #define DBG cerr << "debug here" << endl;
  28. #define DBGV(vari) cerr << #vari<< " = "<< (vari) <<endl;
  29. #define nn <<' '<<
  30. #define ln <<'\n'
  31. #define io_faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  32. //template <typename T>
  33. //inline void read(T& x){
  34. //    bool Neg = false;
  35. //    char c;
  36. //    for (c = getchar(); c < '0' | c > '9'; c = getchar())
  37. //        if (c == '-') Neg = !Neg;
  38. //    x = c - '0';
  39. //    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
  40. //        x = x * 10 + c - '0';
  41. //    if (Neg) x = -x;
  42. //}
  43.  
  44. //template <typename T>
  45. //inline void write(T x)
  46. //{
  47. //    if (x < 0)
  48. //    {
  49. //        putchar('-'); x = -x;
  50. //    }
  51. //    T p = 1;
  52. //    for (T temp = x / 10; temp > 0; temp /= 10) p *= 10;
  53. //    for (; p > 0; x %= p, p /= 10) putchar(x / p + '0');
  54. //}
  55.  
  56. #define PROB "a"
  57. void file(){
  58.     if(fopen(PROB".inp", "r")){
  59.         freopen(PROB".inp","r",stdin);
  60.         freopen(PROB".out","w",stdout);
  61.     }
  62. }
  63. void sinh_(){
  64. //    srand(time(0));
  65. //    freopen(PROB".inp" , "w" , stdout);
  66. //    int n;
  67. }
  68. typedef long long ll;
  69. const int INF = 5e4;
  70. const int N = 2e5 + 5e4 + 2;
  71. const int Q = 1e4 + 5;
  72. int n , q , s , a[N];
  73. pii c[Q];
  74. vector< vi > bit , it;
  75. void add(int pos, int x){
  76.     for (pos += s - 1; pos; pos >>= 1)
  77.         it[pos].pb(x);
  78. }
  79. void readip(){
  80.     cin >> n;
  81.     int x = (int)ceil(log2(n));
  82.     s = 1 << x;
  83.     x = (s << 1) - 1 + 5;
  84.     bit.resize(x) , it.resize(x);
  85.     REP(i ,1, n){
  86.         cin >> a[i];
  87.         add(i , a[i]);
  88.     }
  89.     cin >> q;
  90.     REP(i, 1, q){
  91.         cin >> c[i].fi >> c[i].se;
  92.         add(c[i].fi , c[i].se);
  93.     }
  94. }
  95. void build(int id, int l , int r){
  96.     it[id].pb(INF + 1);
  97.     sort(ALL(it[id]));
  98.     it[id].erase(unique(ALL(it[id])) , it[id].end());
  99.     bit[id].resize(SZ(it[id]) + 2, 0);
  100.     int mid = (l + r) >> 1;
  101.     if (l == r) return;
  102.     build(id << 1, l , mid);
  103.     build((id << 1) | 1 , mid + 1, r);
  104. }
  105. int get_pos(int id, int x){
  106.     int u = lower_bound(ALL(it[id]) , x) - it[id].begin() + 1;
  107.     if (it[id][u - 1] > x) u--;
  108.     return u;
  109. }
  110. void update_bit(int id, int x, int d){
  111.     x = get_pos(id , x);
  112.     for (; x < SZ(it[id]); x += x & -x) bit[id][x] += d;
  113. }
  114. void update(int pos, int x, int d){
  115.     for (pos += s - 1; pos ; pos >>= 1)
  116.         update_bit(pos, x, d);
  117. }
  118. int get(int id, int x){
  119.     int res = 0; x = get_pos(id, x);
  120.     for (; x ; x -= x & -x) res += bit[id][x];
  121.     return res;
  122. }
  123. int get_ans(int l , int r , int L, int R){
  124.     l += s - 1, r += s - 1;
  125.     int res = 0;
  126.     while(l <= r){
  127.         if (l & 1){
  128.             res += get(l , R) - get(l , L - 1);
  129.             l++;
  130.         }
  131.         if (!(r & 1)){
  132.             res += get(r , R) - get(r, L - 1);
  133.             r--;
  134.         }
  135.         l >>= 1, r >>= 1;
  136.     }
  137.     return res;
  138. }
  139.  
  140. void solve(){
  141.     build(1, 1, s);
  142.     REP(i ,1, n) update(i, a[i], 1);
  143.     ll res = 0;
  144.     REP(i, 1, n - 1){
  145.         if (a[i] != 1)
  146.             res += get_ans(i + 1, n , 1,  a[i] - 1);
  147. //        cout << res ln;
  148.     }
  149. //    cout << res;
  150.     REP(i, 1, q){
  151.         int x = a[c[i].fi];
  152.         if (c[i].fi != 1 && x != INF) res -= get_ans(1 , c[i].fi - 1, x + 1 , INF);
  153.         if (c[i].fi != n && x != 1) res -= get_ans(c[i].fi + 1, n , 1, x - 1);
  154.         update(c[i].fi , x , -1);
  155.         a[c[i].fi] = c[i].se;
  156.         x = a[c[i].fi];
  157.         update(c[i].fi , x , 1);
  158.         if (c[i].fi != 1 && x != INF) res += get_ans(1 , c[i].fi - 1, x + 1 , INF);
  159.         if (c[i].fi != n && x != 1) res += get_ans(c[i].fi + 1, n , 1, x - 1);
  160.         cout << res ln;
  161.     }
  162. //    cout << res;
  163. }
  164.  
  165. int main(){
  166.     sinh_();
  167.     io_faster
  168.     file();
  169.     int t = 1;
  170. //    cin >> t;
  171.     while (t--){
  172.         readip();
  173.         solve();
  174.     }
  175. }
  176.  
  177.  
Success #stdin #stdout 0.01s 5460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ykOz3X
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!