区间修改，区间查询，这一类题通常都可以使用线段树解决，但对于此题，树状数组同样可以，而且常数较小，代码简单。
思路：
考虑使用树状数组去维护差分数组，即对于$a_i$,我们使用树状数组去维护$|a_i-a_{i-1}|$的值。
对于修改，我们对一段区间进行修改的时候，能对结果产生影响的只有左右端点，因为绝对值之差相互抵消了。
所以我们考虑修改时，端点的影响即可。
对于$a_l$,若$a_{l-1}\le a_l$，那么我们在对$a_l$进行加一后，我们会发现，$|a_l-a_{l-1}|$的值同样会加一，所以我们正常给$a_l$加一即可。
反之，$a_{l-1}>a_l$,那么在给$a_l$加一的时候，$|a_l-a_{l-1}|$的值会减小，所以此时我们需要给该值减一。
对于$r,r+1$位置的分析同理。
同时，又因为查询需要输出$a_l$的值，所以我们再开一个树状数组去单独维护每个值的大小即可。

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"

struct MIT
{
ll tr[N];
int lowbit(int x) {
    return x & (-x);
}

void add(int u, int v) {
    for (int i = u; i < N; i += lowbit(i)) {
        tr[i] += v;
    }
}

ll query(int x) {
    ll res = 0;

    for (int i = x; i > 0; i -= lowbit(i)) {
        res += tr[i];
    }

    return res;
}
};

MIT t1,t2;

void solve()
{
	int n,q;
	cin>>n>>q;
	vector<int> a(n+5);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		t1.add(i,a[i]-a[i-1]);
		t2.add(i,abs(a[i]-a[i-1]));
	}
	while(q--){
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1){
			cout<<t1.query(l)+t2.query(r)-t2.query(l)<<endl;
		}
		else{
			ll c1=t1.query(l-1),c2=t1.query(l);
			if(c2-c1>=0) t2.add(l,1);
			else t2.add(l,-1);
			c1=t1.query(r),c2=t1.query(r+1);
			if(c2-c1>0) t2.add(r+1,-1);
			else t2.add(r+1,1);
			t1.add(l,1),t1.add(r+1,-1);
		}
	}
}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	//cin>>t;

	while(t--){
		solve();
	}
   	system("pause");
    return 0;
}

简化一下题意，给定一个数组，有$q$次操作，每次操作选择一个编号为$x$的元素删除，要求输出每次操作的中位数。

思路
考虑树状数组在这题中如何进行应用，我们同样把值域映射到下标，去统计对于第 i 个数，其前面有多少个比他小的数。然后运用二分去找值为$n/2$的下标即为所求。

因为值域很大所以需要进行离散化。

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"

struct MIT
{
ll tr[N];
int lowbit(int x) {
    return x & (-x);
}

void add(int u, int v) {
    for (int i = u; i < N; i += lowbit(i)) {
        tr[i] += v;
    }
}

ll query(int x) {
    ll res = 0;

    for (int i = x; i > 0; i -= lowbit(i)) {
        res += tr[i];
    }

    return res;
}
};

int n,q;
int a[N];
MIT tr;

int cal(int x)
{
	int l=1,r=N,ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(tr.query(mid)>=x){
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	return ans;
}

void solve()
{
	cin>>n;
	vector<int> b;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b.push_back(a[i]);
	}
	b.push_back(0);
	sort(b.begin(),b.end());
	b.erase(unique(b.begin(),b.end()),b.end());//离散化不多说了
	for(int i=1;i<=n;i++){
		int t=lower_bound(b.begin(),b.end(),a[i])-b.begin();
		a[i]=t;
		tr.add(t,1);
	}
	int q;
	cin>>q;
	while(q--){
		int x;
		cin>>x;
		x=a[x];
		tr.add(x,-1);
		n--;
		if(n%2==0){
			double ans=(b[cal(n/2)]+b[cal(n/2+1)])*1.0/2;
			printf("%.1lf ",ans);
		}
		else{
			double ans=b[cal((n+1)/2)]*1.0;
			printf("%.1lf ",ans);
		}
	}
	//cout<<endl;
}

int main()
{
	int t;
	t=1;
	while(t--){
		solve();
	}
   	//system("pause");
    return 0;
}