Submission #603234

#	Time	Username	Problem	Language	Result	Execution time	Memory
603234		cadmiumsky	Diversity (CEOI21_diversity)	C++14	64 / 100	7076 ms	30544 KiB

diversity

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
const int nmax = 3e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 rng(2);

int n, q;

int absol(int x) { return  (x >= 0? x : -x);}


namespace Treap {
  struct Node {
    Node *l, *r;
    int area, pri;
    int ind() { return l -> area + 1; } 
    int val, sum;
    bool lazy; 
    ll intl, intr; // left : e mai mic in left
  }*nil = new Node{0, 0, 0, -1, 0, 0, 0, 0, 0};
  using ns = Node*;
  struct pns { ns l, r; };
  
  void prop(ns& node) {
    if(node == nil)
      return;
    if(node -> lazy == 1) {
      swap(node -> l, node -> r);
      swap(node -> intl, node -> intr);
      node -> l -> lazy ^= 1;
      node -> r -> lazy ^= 1;
      node -> lazy = 0;
    }
    return;
  } 
  ns updnode(ns node, ns x, int w) {
    if(node == nil)
      return nil;
    (w == 1? node -> r : node -> l) = x;
    prop(node);
    prop(node -> l);
    prop(node -> r);
    node -> area = 1 + node -> l -> area + node -> r -> area;
    node -> sum = node -> val + node -> l -> sum + node -> r -> sum; 
    node -> intl = node -> l -> intl + (ll)(node -> r -> sum + node -> val) * (node -> ind()) + node -> r -> intl;
    node -> intr = node -> r -> intr + (ll)(node -> l -> sum + node -> val) * (node -> r -> area + 1) + node -> l -> intr;
    return node;
  }
  pns split(ns node, int val) {
    prop(node);
    pns temp;
    return node == nil? pns{nil, nil}:
            node -> area <= val? pns{node, nil}:
              val == 0?  pns{nil, node}:
                node -> ind() <= val? (temp = split(node -> r, val - node ->ind()), temp.l = updnode(node, temp.l, 1), temp):
                  (temp = split(node -> l, val), temp.r = updnode(node, temp.r, 0), temp);
  }
  ns merge(ns l, ns r) {
    prop(l);
    prop(r);
    return l == nil? r:
            r == nil? l:
              l -> pri < r -> pri? updnode(r, merge(l, r -> l), 0): 
                updnode(l, merge(l -> r, r), 1); 
  }
  void print(ns node) {
  } 
  ns parity[2] = {nil, nil};
  void flip(ns& root) {
    root -> lazy ^= 1;
    prop(root);
  }
  void append(ns& root) { root = merge(new Node{nil, nil, 1, rng(), 0, 0, 0, 0, 0}, root);}
  void pop(ns& root) { pns temp = split(root, 1); root = temp.r; }
  
  ll modify(ns& root, int poz, int with) {
    int how = (root == parity[0]? 1 : 0);
    poz++;
    poz = (root == parity[0]? poz : root -> area - poz + 1);
    pns temp[2];
    temp[0] = split(root, poz - 1);
    temp[1] = split(temp[0].r, 1);
    
    temp[1].l -> val += with;
    temp[1].l -> sum += with;
    temp[1].l -> intl += with;
    temp[1].l -> intr += with;
    
    ll modifier = temp[1].r -> intl + temp[0].l -> intr;
    root = merge(temp[0].l, merge(temp[1].l, temp[1].r));
    poz = (how == 1? root -> area - poz : poz - 1);
    if(how == 1) modifier += parity[how] -> intl;
    else modifier += parity[how] -> intr;
    modifier += (ll)parity[how] -> sum * poz;
    modifier *= with;
    return modifier;
  }
}
using namespace Treap;
int buck;
int v[nmax];
struct Query { 
  int l, r, ind;
  bool operator <(const Query& other) const {
    return (l / buck < other.l / buck || (l / buck == other.l / buck && r < other.r));
  }
};

namespace Mo {
  deque<int> sorted;
  deque<int> vals;
  int freq[nmax];
  int atrindex[nmax];
  ll total, comb, sum, sqsum;
  void add(int x) {
    x = v[x];
    //cerr <<x << '\n';
    
    int it;
    if(freq[x] == 0) {
      flip(parity[0]);
      flip(parity[1]);
      swap(parity[0], parity[1]);
      append(parity[0]);
      it = 0;
      atrindex[x] = sorted.size();
      sorted.push_front(0);
      vals.push_front(x);
    }
    else {
      it = prev(upper_bound(sorted.begin(), sorted.end(), sorted.rbegin()[atrindex[x]])) - sorted.begin();
      int otr = vals[it];
      swap(atrindex[x], atrindex[otr]);
      swap(vals.rbegin()[atrindex[x]], vals.rbegin()[atrindex[otr]]);
    }
    auto temp = modify(parity[it % 2], it / 2, 1);
    total += temp;
    
    sorted[it]++;
    
    sqsum += freq[x] * 2 + 1;
    sum++;
    freq[x]++;
    comb += freq[x];
  }
  void erase(int x) {
    x = v[x];
    
    int it;
    it = lower_bound(sorted.begin(), sorted.end(), sorted.rbegin()[atrindex[x]]) - sorted.begin();
    int otr = vals[it];
    swap(atrindex[x], atrindex[otr]);
    swap(vals.rbegin()[atrindex[x]], vals.rbegin()[atrindex[otr]]);
    
    total += modify(parity[it % 2], it / 2, -1);
    sorted[it]--;
    
    
    comb -= freq[x];
    freq[x]--;
    sum--;
    sqsum -= freq[x] * 2 + 1;
    if(freq[x] == 0) {
      pop(parity[0]);
      flip(parity[0]);
      flip(parity[1]);
      swap(parity[0], parity[1]);
      sorted.pop_front();
      vals.pop_front();
      atrindex[x] = 0;
    }
    return;
  }
  ll query() {
    //cerr << total << ' ' << comb << ' ' << sum << ' ' << sqsum << '\n';
    return total + comb + (sum * sum - sqsum) / 2;
  }
}

signed main() {
  cin >> n >> q;
  buck = max(1.0, sqrt((ll) n * n / q));
  for(int i = 1; i <= n; i++)
    cin >> v[i];
  vector<int> rez(q);
  vector<Query> qs(q);
  int cnt = 0;
  for(auto &[l, r, ind] : qs) {
    cin >> l >> r;        
    ind = cnt++;
  }
  
  sort(qs.begin(), qs.end());
  int lastl = 1, lastr = 0;
  for(auto [l, r, ind] : qs) {
    while(lastr < r)
      Mo::add(++lastr);
    while(lastl > l)
      Mo::add(--lastl);
    while(lastl < l)
      Mo::erase(lastl++);
    while(lastr > r)
      Mo::erase(lastr--);
    //cerr << lastr << ' ' << lastl << '\n';
    rez[ind] = Mo::query();
    //if(ind % 500 == 213)
      //cerr << "amog\n";
  }
  //cerr << "unamog\n";
  for(auto x : rez)
    cout << x << '\n';
}
// TLE my beloved

Compilation message (stderr)

diversity.cpp: In function 'void Treap::append(Treap::Node*&)':
diversity.cpp:76:65: warning: narrowing conversion of 'rng.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'll' {aka 'long long int'} [-Wnarrowing]
   76 |   void append(ns& root) { root = merge(new Node{nil, nil, 1, rng(), 0, 0, 0, 0, 0}, root);}
      |                                                              ~~~^~
diversity.cpp: In function 'int main()':
diversity.cpp:191:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  191 |   for(auto &[l, r, ind] : qs) {
      |             ^
diversity.cpp:198:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  198 |   for(auto [l, r, ind] : qs) {
      |            ^

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 0 / 36