fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. const int B = 31;
  6. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  7. int irandom_range(int l, int r) { return (l + rng() % (r-l+1)); }
  8.  
  9. struct Query {
  10.   int op;
  11.   int p, y;
  12.  
  13.   void input() {
  14.     cin >> op;
  15.     if (op == 1) cin >> p >> y;
  16.   }
  17. };
  18.  
  19. void brute_update(vector<int>& a, int p, int q) {
  20.   int n = (int)a.size();
  21.   for (int i = 0; i < n; ++i) {
  22.     if (__builtin_popcount(a[i]) == p) {
  23.       a[i] |= q;
  24.       break;
  25.     }
  26.   }
  27. }
  28.  
  29. ll brute_query(vector<int>& a) {
  30.   int n = (int)a.size();
  31.   ll ret = 0;
  32.   for (int l = 0; l < n; ++l) for (int r = l; r < n; ++r) {
  33.     int mx = 0;
  34.     for (int i = l; i <= r; ++i) {
  35.       mx = max(mx, __builtin_popcount(a[i]));
  36.     }
  37.     ret += (ll)(r-l+1) * mx;
  38.   }
  39.   return ret;
  40. }
  41.  
  42. ll get_sum(ll l, ll r) {
  43.   ll ret = r * (r + 1) / 2;
  44.   if (l > 0) ret -= l * (l - 1) / 2;
  45.   return ret;
  46. }
  47.  
  48. ll get_val(ll i, ll l, ll r) {
  49.   ll ld = i - l + 1;
  50.   ll rd = r - i + 1;
  51.   ll ret = (ld + rd) * ld * rd / 2;
  52.   return ret;
  53. }
  54.  
  55. void solve_case(){
  56.   int n, q;
  57.   n = 100;
  58.   q = 100;
  59. //  cin >> n >> q;
  60.  
  61.   vector<int> a(n);
  62.   for (int i = 0; i < n; ++i) a[i] = irandom_range(1, 100);
  63. //  for (int i = 0; i < n; ++i) cin >> a[i];
  64.  
  65.   vector<Query> queries(q);
  66.   for (int i = 0; i < q; ++i) {
  67.     queries[i].op = 1;
  68.     queries[i].p = irandom_range(1, 4);
  69.     queries[i].y = irandom_range(1, 100);
  70. //    queries[i].input();
  71.   }
  72.  
  73.   vector<int> P(n);
  74.   for (int i = 0; i < n; ++i) {
  75.     P[i] = __builtin_popcount(a[i]);
  76.   }
  77.  
  78.   vector<int> L(n);
  79.   {
  80.     stack<int> st;
  81.     for (int i = 0; i < n; ++i) {
  82.       while (!st.empty() && (P[st.top()] < P[i])) st.pop();
  83.       if (st.empty()) L[i] = 0;
  84.         else L[i] = st.top() + 1;
  85.       st.push(i);
  86.     }
  87.   }
  88.  
  89.   vector<int> R(n);
  90.   {
  91.     stack<int> st;
  92.     for (int i = n-1; i >= 0; --i) {
  93.       while (!st.empty() && (P[st.top()] <= P[i])) st.pop();
  94.       if (st.empty()) R[i] = n-1;
  95.         else R[i] = st.top() - 1;
  96.       st.push(i);
  97.     }
  98.   }
  99.  
  100.   ll ans = 0;
  101.   for (int i = 0; i < n; ++i) {
  102.     ans += get_val(i, L[i], R[i]) * P[i];
  103.   }
  104.  
  105.   array<set<pair<int,int>>,B> pos;
  106.   for (int i = 0; i < n; ++i) pos[P[i]].emplace(i, a[i]);
  107.  
  108.   auto debug_print = [&]() -> void {
  109.     cout << "\tP: ";
  110.     for (int i = 0; i < n; ++i) cout << P[i] << " ";
  111.     cout << "\n";
  112.     cout << "\tL: ";
  113.     for (int i = 0; i < n; ++i) cout << L[i] << " ";
  114.     cout << "\n";
  115.     cout << "\tR: ";
  116.     for (int i = 0; i < n; ++i) cout << R[i] << " ";
  117.     cout << "\n";
  118.   };
  119.  
  120.   auto update_L = [&](int i, int new_i) -> void {
  121.     ans -= get_val(i, L[i], R[i]) * P[i];
  122.     L[i] = new_i;
  123.     ans += get_val(i, L[i], R[i]) * P[i];
  124.   };
  125.  
  126.   auto update_R = [&](int i, int new_i) -> void {
  127.     ans -= get_val(i, L[i], R[i]) * P[i];
  128.     R[i] = new_i;
  129.     ans += get_val(i, L[i], R[i]) * P[i];
  130.   };
  131.  
  132.   vector<int> b = a;
  133.   for (int qi = 0; qi < q; ++qi) {
  134. //    queries[qi].input();
  135.     int op = queries[qi].op;
  136.     int p = queries[qi].p;
  137.     int y = queries[qi].y;
  138.     if (op == 1) {
  139.       if (pos[p].empty()) continue;
  140.       auto it = pos[p].begin();
  141.       int i = it->first;
  142.       int x = it->second;
  143.       pos[p].erase(pos[p].begin());
  144.       int xto = x | y;
  145.       if (xto == x) continue;
  146.       int xto_p = __builtin_popcount(xto);
  147.  
  148.       ans -= get_val(i, L[i], R[i]) * P[i];
  149.  
  150.       // update R
  151.       R[i] = n;
  152.       for (int b = xto_p + 1; b < B; ++b) {
  153.         if (pos[b].empty()) continue;
  154.         auto it = pos[b].lower_bound({i, -1});
  155.         if (it != pos[b].end()) {
  156.           R[i] = min(R[i], it->first - 1);
  157.         }
  158.       }
  159.       if (!pos[xto_p].empty()) {
  160.         auto it = pos[xto_p].lower_bound({i, -1});
  161.         if (it != pos[xto_p].end()) {
  162.           if (it->first < R[i]) {
  163.             R[i] = R[it->first];
  164.             update_L(it->first, i+1);
  165.           }
  166.         }
  167.       }
  168.       R[i] = min(R[i], n-1);
  169.  
  170.       // update L
  171.       L[i] = -1;
  172.       for (int b = xto_p + 1; b < B; ++b) {
  173.         if (pos[b].empty()) continue;
  174.         auto it = pos[b].lower_bound({i, -1});
  175.         if (it != pos[b].begin()) {
  176.           --it;
  177.           L[i] = max(L[i], it->first + 1);
  178.         }
  179.       }
  180.       if (!pos[xto_p].empty()) {
  181.         auto it = pos[xto_p].lower_bound({i, -1});
  182.         while (it != pos[xto_p].begin()) {
  183.           --it;
  184.           if (it->first < L[i]) break;
  185.           if (it->first > L[i]) {
  186.             L[i] = it->first+1;
  187.           }
  188.           update_R(it->first, R[i]);
  189.         }
  190.       }
  191.       L[i] = max(L[i], 0);
  192.  
  193.       int curr = P[i];
  194.       for (int j = i+1; j < n; ++j) {
  195.         if (P[j] >= xto_p) break;
  196.         if (P[j] > curr) {
  197.           update_L(j, i+1);
  198.           curr = P[j];
  199.         }
  200.       }
  201.  
  202.       for (int j = i-1; j >= 0; --j) {
  203.         if (P[j] > xto_p) break;
  204.         if (P[j] >= x) {
  205.           update_R(j, i-1);
  206.         }
  207.       }
  208.  
  209.       a[i] = xto;
  210.       P[i] = xto_p;
  211.       pos[xto_p].emplace(i, a[i]);
  212.       ans += get_val(i, L[i], R[i]) * P[i];
  213.  
  214.       brute_update(b, p, y);
  215.  
  216.       int bans = brute_query(b);
  217.       if (ans != bans) {
  218.         cout << ans << " : " << bans << "\n";
  219.         debug_print();
  220.         break;
  221.       }
  222.     } else {
  223.       cout << "\t" << ans << " " << brute_query(b) << endl;
  224.     }
  225.   }
  226. }
  227.  
  228. int main(){
  229. //  ios_base::sync_with_stdio(false); cin.tie(NULL);
  230.  
  231.   int tc = 1, ti;
  232.   cin >> tc;
  233.   for (ti = 1; ti <= tc; ++ti) {
  234.     solve_case();
  235.   }
  236. }
  237.  
  238. /*
  239. 1
  240. 10 123123
  241. 1 2 3 4 5 6 7 8 9 10
  242. 1 1 10000
  243. 1 1 100000000
  244. 1 2 10000
  245.  
  246. 1
  247. 10 123123
  248. 1 2 3 4 5 6 7 8 9 10
  249. 1 1 10000
  250. 1 1 100000000
  251. 1 2 10000
  252. 1 5 213123
  253. 1 5 23123
  254. 1 4 123123
  255. 1 6 123123
  256. 1 10 123123
  257. 1 3 123123
  258.  
  259. 8
  260.  
  261. 3 5
  262. 2 1 3
  263. 2
  264. 1 2 4
  265. 2
  266. 1 1 1
  267. 2
  268.  
  269. 9 6
  270. 8 3 4 6 1 7 3 8 2
  271. 2
  272. 1 2 5
  273. 2
  274. 1 2 6
  275. 1 3 8
  276. 2
  277.  
  278. 9 6
  279. 2 8 3 7 1 6 4 3 8
  280. 2
  281. 1 2 5
  282. 2
  283. 1 2 6
  284. 1 3 8
  285. 2
  286.  
  287. 7 1
  288. 1 1 1 1 1 1 1
  289. 2
  290.  
  291. 7 1
  292. 1 1 1 3 1 1 1
  293. 2
  294.  
  295. 7 1
  296. 7 7 7 3 7 7 7
  297. 2
  298.  
  299. 7 1
  300. 7 7 7 7 7 7 7
  301. 2
  302.  
  303. 7 1
  304. 7 7 7 15 7 7 7
  305. 2
  306.  
  307. */
  308.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
970131 : 969922
	P: 5 4 5 5 5 3 4 3 2 4 3 4 4 3 3 4 1 3 1 1 3 2 4 3 6 3 2 3 3 5 2 6 2 2 3 5 1 3 3 2 3 4 4 4 5 3 3 5 5 5 3 4 3 5 2 4 3 4 2 2 3 5 3 2 2 2 4 3 5 2 1 3 5 5 2 3 4 4 2 1 5 4 5 3 5 3 3 4 3 4 2 3 4 2 2 3 3 1 4 4 
	L: 0 1 1 3 4 5 5 7 8 7 10 10 12 13 14 13 16 16 18 19 18 21 16 23 0 25 26 26 28 25 30 25 32 33 32 32 36 36 38 39 39 36 42 43 36 45 46 45 48 49 50 50 52 50 54 54 56 56 58 59 58 54 62 63 64 65 62 67 62 69 70 69 69 73 74 74 74 77 78 79 74 81 81 83 83 85 86 85 88 88 90 90 90 93 94 93 96 97 93 99 
	R: 23 1 23 23 23 5 23 8 8 23 10 23 23 14 14 23 16 21 19 19 21 21 23 23 99 28 26 28 28 30 30 99 33 33 34 99 36 40 40 39 40 43 43 43 99 46 46 99 99 99 50 52 52 99 54 60 56 60 59 59 60 99 65 65 65 65 67 67 99 70 70 71 99 99 74 75 79 79 79 79 99 81 99 83 99 86 86 99 88 99 90 91 99 94 94 97 97 97 99 99
https://ideone.com/71No3e
language:
C++14 (gcc 8.3)
created:
9 days 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!