Submission #603220

#	Time	Username	Problem	Language	Result	Execution time	Memory
603220		cadmiumsky	Diversity (CEOI21_diversity)	C++14	64 / 100	430 ms	32324 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) {
    //if(node == nil)
      //return;
    //print(node -> l);
    //cerr << node -> val << ' ';
    //print(node -> r);
    //return;
  } 
  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);
     //cerr << "--\n"; print(root); cerr << "\n--\n";
     }
  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);
    //cerr << "long " << poz << ' ' << root -> area<<  ' ' ;
    //cerr << "So here we have had " << root -> sum << ' ' << root -> area << '\n';
    pns temp[2];
    temp[0] = split(root, poz - 1);
    temp[1] = split(temp[0].r, 1);
    //auto incaunu = split(temp[1].r, 1);
    //temp[1].r = merge(incaunu.l, incaunu.r);
    
    temp[1].l -> val += with;
    temp[1].l -> sum += with;
    temp[1].l -> intl += with;
    temp[1].l -> intr += with;
    //cerr << temp[1].l -> val << ' ' << temp[1].l -> intl << ' ' <<temp[1].l -> sum << ' ' <<temp[1].l -> area << ' ' << '\n';
    
    ll modifier = temp[1].r -> intl + temp[0].l -> intr;
    //cerr << "> " << modifier << ' ' << temp[1].r -> val << ' ' << temp[1].r -> intl << ' ' << temp[1].r->intr << ' ' << temp[1].r -> sum << ' ' << temp[1].r -> area << '\n';
    //if(temp[1].r != nil)
      //cerr << temp[1].r -> l -> val << ' ' << ' ' << temp[1].r -> val << ' ' << temp[1].r -> r -> val << '\n';
    //cerr << temp[0].l -> area << '\n';
    //cerr << "to be further told " << temp[0].l -> sum << ' ' << temp[1].l -> sum << ' ' << temp[1].r -> sum << '\n';
    root = merge(temp[0].l, merge(temp[1].l, temp[1].r));
    //cerr << "So here we have " << root -> sum << ' ' << root -> area << '\n';
    poz = (how == 1? root -> area - poz : poz - 1);
    if(how == 1) modifier += parity[how] -> intl;
    else modifier += parity[how] -> intr;
    //cerr << "> " << modifier << '\n';
    modifier += (ll)parity[how] -> sum * poz;
    //cerr << how << ' ' << parity[how] -> sum<< '/' << parity[how] -> area << ' ' << root -> area << ' ' << poz << '\n';
    //cerr << modifier << "< \n";;
    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);
    //cout << x << ' ' << temp << '\n';
    total += temp;
    
    sorted[it]++;
    
    sqsum += freq[x] * 2 + 1;
    sum++;
    freq[x]++;
    comb += freq[x];
    
    //for(auto a : vals)
      //cerr << a << ' ';
    //cerr << '\n';
    //for(auto a : sorted)
      //cerr << a << ' ';
    //cerr << '\n';
    //cerr << '\n';
    
    //cerr << parity[0] -> area << ' ' << parity[1] -> area << '\n';
  }
  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_back();
      vals.pop_back();
      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) {
    //cerr << l << ' ' << r << ' ' << ind << '\n';0
    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';
    //for(auto x : Mo::sorted)
      //cerr << x << ' ';
    //cerr << '\n';
    //for(auto x : Mo::vals)
      //cerr << x << ' ';
    //cerr << '\n';
    rez[ind] = Mo::query();
  }
  //cerr << "unamog\n";
  for(auto x : rez)
    cout << x << '\n';
}

Compilation message (stderr)

diversity.cpp: In function 'void Treap::append(Treap::Node*&)':
diversity.cpp:82: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]
   82 |   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:224:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  224 |   for(auto &[l, r, ind] : qs) {
      |             ^
diversity.cpp:231:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  231 |   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