D&E线段树做法

#include <iostream>
#include <iomanip>
using namespace std;

int a[200005];
struct elem {
  double val;
  int l,r;
};
struct node {
  elem data, lazy;
} tree[800005];

void pushup(elem &e, elem &e1, elem &e2) {
  e = {e1.val + e2.val, e1.l, e2.r};
}

void build(int l, int r, int rt) {
  if (l == r) {
    tree[rt].data = {double(a[l]), l, l};
    return;
  }
  int m = (l+r)/2;
  build(l, m, rt*2);
  build(m+1, r, rt*2+1);
  pushup(tree[rt].data, tree[rt*2].data, tree[rt*2+1].data);
}

void pushdown(int rt, int ln, int rn) {
  tree[rt*2].data = {tree[rt].lazy.val*ln, tree[rt].lazy.l, tree[rt].lazy.r};
  tree[rt*2].lazy = tree[rt].lazy;
  tree[rt*2+1].data = {tree[rt].lazy.val*rn, tree[rt].lazy.l, tree[rt].lazy.r};
  tree[rt*2+1].lazy = tree[rt].lazy;
  tree[rt].lazy.l = 0;
}
// 区间更新
void update(int L, int R, double C, int l, int r, int rt) {
  if (L <= l && R >= r) {
    tree[rt].data = {C*(r-l+1), L, R};
    tree[rt].lazy = {C, L, R};
    return;
  }
  int m = (l+r)/2;
  if (tree[rt].lazy.l != 0)
    pushdown(rt, m-l+1, r-m);
  if (L <= m)
    update(L, R, C, l, m, rt*2);
  if (R > m)
    update(L, R, C, m+1, r, rt*2+1);
  pushup(tree[rt].data, tree[rt*2].data, tree[rt*2+1].data);
}
// 区间查询
elem query(int L, int R, int l, int r, int rt) {
  if (L <= l && R >= r)
    return tree[rt].data;
  int m = (l+r)/2;
  if (tree[rt].lazy.l != 0)
    pushdown(rt, m-l+1, r-m);
  elem e, e1{}, e2{};
  if (L <= m)
    e1 = query(L, R, l, m, rt*2);
  if (R > m)
    e2 = query(L, R, m+1, r, rt*2+1);
  if (e1.l == 0)
    return e2;
  if (e2.l == 0)
    return e1;
  pushup(e, e1, e2);
  return e;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n,m;
  cin>>n>>m;
  for (int i=1; i<=n; i++)
    cin>>a[i];
  build(1,n,1);
  while (m--) {
    int op;
    cin>>op;
    if (op == 1) {
      int l,r;
      cin>>l>>r;
      elem e = query(l,r,1,n,1); // 第一次查询 查询包含l到r的最远端点
      e = query(e.l,e.r,1,n,1); // 第二次查询 查询最远端点的区间的总和
      update(e.l,e.r,e.val/(e.r-e.l+1),1,n,1); // 更新最远端点的区间为该段均值
    } else {
      int i;
      cin>>i;
      cout<<fixed<<setprecision(6)<<query(i,i,1,n,1).val<<'\n';
    }
  }
  
  return 0;
}