Submission #2379174

---

Source Code Expand

void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  int n; rd(n);
  auto a=readln.split.to!(int[]);

  auto pos=new int[](n+1);
  foreach(int i; 0..n) pos[a[i]]=(i+1);
  auto tree=new SquareRootDecomposition(n);
  long sum=0;
  for(int v=n; v>=1; v--){
    int i=pos[v];
    tree.merge(i);
    auto seq=tree.get(i);
    auto l=seq.left, r=seq.right,
         dl=(i-l+1).to!(long), dr=(r-i+1).to!(long);
    sum+=dl*dr*v;
  }
  writeln(sum);
}

struct Seq{int left, right;}

class SquareRootDecomposition{
  import std.algorithm;
  int D=1, inf=1_000_000_000;
  int[] left, right;
  int[] buc_left, buc_right;
  this(int n){
    while(D*D<n) D++;
    left.length=right.length=(D*D+1);
    buc_left.length=buc_right.length=(D+1);
    fill(left, inf); fill(right, -inf);
    fill(buc_left, -1); fill(buc_right, -1);
  }
  void merge(int i){
    int l=i, r=i;
    if(buc_left[(i-1)/D+1]>=0) chmin(l, buc_left[(i-1)/D+1]);
    if(buc_right[(i-1)/D+1]>=0) chmax(r, buc_right[(i-1)/D+1]);
    if(i-1>=1){
      chmin(l, left[i-1]);
      if(buc_left[(i-1-1)/D+1]>=0) chmin(l, buc_left[(i-1-1)/D+1]);
    }
    if(i+1<=D*D){
      chmax(r, right[i+1]); 
      if(buc_right[(i+1-1)/D+1]>=0) chmax(r, buc_right[(i+1-1)/D+1]);
    }
    int bl=(l-1)/D+1, br=(r-1)/D+1;
    if(br-bl<=1){
      eachUpdate(l, r, l, r);
    }else{
      eachUpdate(l, bl*D, l, r);
      buc_left[(bl+1)..br]=l;
      buc_right[(bl+1)..br]=r;
      eachUpdate((br-1)*D+1, r, l, r);
    }
  }
  void eachUpdate(int st, int ed, int l, int r){ // j in [st, ed], left[j]<-l, right[j]<-r
    push((st-1)/D+1); push((ed-1)/D+1); // ここらへん、頭使わないといけないので、よくない
    for(int j=st; j<=ed; j++) left[j]=l, right[j]=r;
  }
  void push(int k){
    if(buc_left[k]>=0){
      for(int j=(k-1)*D+1; j<=k*D; j++) left[j]=buc_left[k];
      buc_left[k]=-1;
    }
    if(buc_right[k]>=0){
      for(int j=(k-1)*D+1; j<=k*D; j++) right[j]=buc_right[k];
      buc_right[k]=-1;
    }
  }
  Seq get(int i){
    auto ret=Seq(i, i);
    if(buc_left[(i-1)/D+1]>=0) chmin(ret.left, buc_left[(i-1)/D+1]);
    else chmin(ret.left, left[i]);
    if(buc_right[(i-1)/D+1]>=0) chmax(ret.right, buc_right[(i-1)/D+1]);
    else chmax(ret.right, right[i]);
    return ret;
  }
  void show(){
    import std.stdio;
    writeln(left);
    // writeln(buc_left);
    writeln(right);
  }
}

void chmin(T)(ref T l, T r){if(l>r)l=r;}
void chmax(T)(ref T l, T r){if(l<r)l=r;}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x) e=l[i].to!(typeof(e));
}

Submission Info

Judge Result