排序：

基数，快排，希尔 7.15

线段树（单点修改，区间查询模板）：

#include<bits/stdc++.h>
using namespace std;
int n=0,a[114514],p=0,cnt=0,cntt=0;
struct xy
{
	int l,r,s;
};
xy f[114514];
void pushup(int i)
{
	f[i].s=f[i*2].s+f[i*2+1].s;
	return ;
}
void build(int i,int l,int r)
{
	p++;
	f[i].l=l;
	f[i].r=r;
	if(l==r)
	{
		f[i].s=a[l];
		return ;
	}
	int m=(l+r)/2;
	build(i*2,l,m);
	build(i*2+1,m+1,r);
	pushup(i);
	return ;
}
void update(int i,int l,int r)
{
	if(f[i].l>=l&&f[i].r<=l)
	{
		f[i].s=f[i].s+r;
		return ;
	}
	int m=(f[i].l+f[i].r)/2;
	if(l<=m)
	{
		update(i*2,l,r);
	}
	if(l>m)
	{
		update(i*2+1,l,r);
	}
	pushup(i);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=p;i++)
	{
		cout<<i<<" "<<f[i].s<<endl;
	}
	cin>>cnt>>cntt;
	update(1,cnt,cntt);
	for(int i=1;i<=p;i++)
	{
		cout<<i<<" "<<f[i].s<<endl;
	}
}

线段树（区间修改，区间查询模板）：

超快速排序（代码及解析）: 单调栈模板

/*const long long N = 1e5+10,INF = 0x3f3f3f3f;
long long a[N],ans[N],ans2[N],st[N],n,top,res,tmp;*/
void calc1(){
	for(long long i = 1; i <= n; i++){
		while(top>0&&a[i]<=a[st[top]])top--;
		ans[i]=st[top];st[++top]=i;
	}//单调栈模版，但是>=改成<=以达到效果 
}
void calc2(){
	for(long long i = n; i >= 1; i--){
		while(top>0&&a[i]<=a[st[top]])top--;
		ans2[i]=st[top];st[++top]=i;
	}//单调栈模版，但是>=改成<=以达到效果 
}