結果

問題 No.1526 Sum of Mex 2
ユーザー 👑 Nachia
提出日時 2021-05-31 20:28:57
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,133 ms / 3,000 ms
コード長 4,301 bytes
コンパイル時間 2,805 ms
コンパイル使用メモリ 217,032 KB
最終ジャッジ日時 2025-01-21 20:51:59
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)


template<
  class S,
  S(*op)(S l,S r),
  S(*e)(),
  class F,
  S(*mapping)(F f,S a),
  F(*composition)(F f,F g),
  F(*id)(),
  bool(*beats)(S a)
>
struct segtreebeats{
private:
  struct Node{ S v; F r; };
  int N,logN;
  vector<Node> V;

  void mapF(int i,F f){
    V[i].v = mapping(f,V[i].v);
    V[i].r = composition(f,V[i].r);
    if(beats(V[i].v)){ spread(i); merge(i); }
  }
  void merge(int i){
    V[i].v = mapping(V[i].r,op(V[i*2].v,V[i*2+1].v));
  }
  void spread(int i){
    mapF(i*2,V[i].r); mapF(i*2+1,V[i].r);
    V[i].r=id();
  }
public:

  segtreebeats(int n){
    N=1; logN=0; while(N<n){ N*=2; logN++; }
    V.assign(N*2,{ e(),id() });
  }
  segtreebeats(vector<S> A) : segtreebeats(A.size()){
    rep(i,A.size()) V[N+i].v=A[i];
    for(int i=N-1; i>=1; i--) merge(i);
  }

  void set(int p,S v){
    p+=N;
    for(int d=logN; d>=1; d--) spread(p>>d);
    V[p].v=v;
    for(int d=1; d<=logN; d++) merge(p>>d);
  }
  S get(int p){
    p+=N;
    for(int d=logN; d>=1; d--) spread(p>>d);
    return V[p].v;
  }

  S prod(int l,int r){
    l+=N; r+=N;
    for(int d=logN; d>=1; d--){ spread(l>>d); spread((r-1)>>d); }
    S ql=e(), qr=e();
    while(l<r){
      if(l&1) ql=op(ql,V[l++].v);
      if(r&1) qr=op(V[--r].v,qr);
      l/=2; r/=2;
    }
    return op(ql,qr);
  }
  void apply(int p,F f){
    p+=N;
    for(int d=logN; d>=1; d--) spread(p>>d);
    mapF(p,f);
    for(int d=1; d<=logN; d++) merge(p>>d);
  }
  void apply(int l,int r,F f){
    l+=N; r+=N;
    for(int d=logN; d>=1; d--){ spread(l>>d); spread((r-1)>>d); }
    int lp=l, rp=r;
    while(l<r){
      if(l&1) mapF(l++,f);
      if(r&1) mapF(--r,f);
      l/=2; r/=2;
    }
    for(int d=1; d<=logN; d++){ merge(lp>>d); merge((rp-1)>>d); }
  }
};

struct cin_improve_speed{
  cin_improve_speed(){
    cin.tie(nullptr);
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
  }
} cin_improve_speed_instance;

const LL INF=2000000000000000000;
struct RCAS_S { LL l,lc,l2,r,rc,r2,s,z; bool beats; };
RCAS_S RCAS_op(RCAS_S l, RCAS_S r){
  RCAS_S res;
  res.l=min(l.l,r.l);
  res.lc=((l.l==res.l)?l.lc:0)+((r.l==res.l)?r.lc:0);
  res.l2=min(((l.l==res.l)?l.l2:l.l),((r.l==res.l)?r.l2:r.l));
  res.r=max(l.r,r.r);
  res.rc=((l.r==res.r)?l.rc:0)+((r.r==res.r)?r.rc:0);
  res.r2=max(((l.r==res.r)?l.r2:l.r),((r.r==res.r)?r.r2:r.r));
  res.s=l.s+r.s;
  res.z=l.z+r.z;
  res.beats=false;
  return res;
}
RCAS_S RCAS_e() { return { INF,0,INF,-INF,0,-INF,0,0,false }; }
struct RCAS_F { LL l,r,a; };
RCAS_S RCAS_mapping(RCAS_F f, RCAS_S a) {
  if(a.l2<=f.l){ a.beats=true; return a; }
  if(a.r2>=f.r){ a.beats=true; return a; }
  if(a.l<f.l){ a.s+=(f.l-a.l)*a.lc; if(a.r==a.l) a.r=f.l; if(a.r2==a.l) a.r2=f.l; a.l=f.l; }
  if(a.r>f.r){ a.s+=(f.r-a.r)*a.rc; if(a.l==a.r) a.l=f.r; if(a.l2==a.r) a.l2=f.r; a.r=f.r; }
  a.s+=f.a*a.z; if(a.l!=INF) a.l+=f.a; if(a.l2!=INF) a.l2+=f.a; if(a.r!=INF) a.r+=f.a; if(a.r2!=-INF) a.r2+=f.a;
  a.beats=false;
  return a;
}
RCAS_F RCAS_composition(RCAS_F f, RCAS_F g) {
  f.l-=g.a; f.r-=g.a;
  g.a+=f.a;
  g.l=min(max(g.l,f.l),f.r);
  g.r=min(max(g.r,f.l),f.r);
  return g;
}
RCAS_F RCAS_id() { return { -INF,INF,0 }; }
bool RCAS_beats(RCAS_S a){ return a.beats; }
using RCAS = segtreebeats<
  RCAS_S,
  RCAS_op,
  RCAS_e,
  RCAS_F,
  RCAS_mapping,
  RCAS_composition,
  RCAS_id,
  RCAS_beats
>;


RCAS_S uni(int v){
  RCAS_S res = RCAS_e();
  res.beats = false;
  res.l = res.r = res.s = v;
  res.lc = res.rc = 1;
  return res;
}


int main(){
  int N; cin >> N;
  vector<int> A(N);
  vector<int> prevbuf(N,0);
  vector<int> prev(N);
  for(int i=0; i<N; i++){ cin >> A[i]; A[i]--; }
  for(int i=0; i<N; i++){
    prev[i] = prevbuf[A[i]];
    prevbuf[A[i]] = i+1;
  }
  vector<RCAS_S> V(N); rep(i,N){ LL a = prevbuf[i]+1; V[i]={a,1,INF,a,1,-INF,a,1,false}; }
  RCAS G(V);
  LL ans = 0;
  for(int i=0; i<N; i++) G.apply(i,N,{-INF,prevbuf[i],0});
  for(int i=N-1; i>=0; i--){
    LL s = G.prod(0,N).s;
    ans += s;
    ans += i+1;
    G.apply(A[i],N,{-INF,prev[i],0});
  }
  cout << ans << "\n";
  return 0;
}



struct ios_do_not_sync{
  ios_do_not_sync(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  }
} ios_do_not_sync_instance;
0