题目
Description
有n个小朋友需要接水，其中第i个小朋友接水需要ai分钟。
由于水龙头有限，小Hi需要知道如果为第l个到第r个小朋友分配一个水龙头，如何安排他们的接水顺序才能使得他们等待加接水的时间总和最小。
小Hi总共会有m次询问，你能帮助他解决这个问题吗？
假设3个小朋友接水的时间分别是2，3，4。如果他们依次接水，第一位小朋友等待加接水的时间是2，第二位小朋友是5，第三位小朋友是9。时间总和是16。
Input
第一行一个数T(T<=10)，表示数据组数
对于每一组数据：
第一行两个数n，m（1<=n,m<=20,000）
第二行n个数a1…an，表示每个小朋友接水所需时间(ai<=20,000)
接下来m行，每行两个数l和r
Output
对于每次询问，输出一行一个整数，表示答案。
Sample Input
1
4 2
1 2 3 4
1 2
2 4
Sample Output
4
16
题解
20多天前看到的一个题，当时没想到用莫队去处理。今天来实验室复习OS时冥冥之中有种感觉要我来写这个题目，然后再次思考了会，突然发现我会了？？？？
玄学。
首先，看到大批量的区间查询，我们应该试着去考虑下莫队算法。所谓莫队算法，就是将m组区间查询[l，r]先存在一个结构体数组query中，然后对此结构体数组按照某个原则去排序。
这个原则有个学名叫“分块”，所谓分块就是将n个数分到sqrt（n）块，每块有sqrt（n）个值。
求一个值num=（l-1)/sqrt(n)，num表示l在第几块。
然后按照两个关键字num和r去对结构体数组query排序。
当num相等时，按r升序排；
当num不等时，按num升序排。
先结合题意，确定需要用什么数据结构去维护一个什么功能。
区间[l，r]的排队时间最少，显然是都升序排列即可。那么我们就维护一个有序数组。可以用一个树状数组person维护，每增加一个人就add（val，1），val为该人的等待时间。
而要求总和，一个明显的思路就是维护前缀和嘛，那么我们就需要维护一个数组的前缀和。用另一个树状数组tim维护。每次加一或减一变化的有两部分：
1、所加入或减少的人的等待时间（val）的前缀和，即tim.sum（val）。
2、val后面那一部分人都增加或减少val。即val*(person.sum(maxn-1)-person.sum(val))
接下来就是暴力从一个区间到另一个区间去更新答案了。只要区间加一和减一的时间复杂度为O(1)或O(logn)级别的，一般就可以认为不会超时了。
心得
莫队算法进行添加一个元素时要等添加完后再查询，进行删除一个元素时要先查询之后再删除。
如果样例过了，报超时错误，注意是不是用cin输入了，处理大批量数据，cin比scanf慢很多。
如果样例过了，报答案错误，注意是不是没有用long long去存这个结果。最后溢出了。
AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxn=2e4+7;
int T,n,m,a[maxn];
ll res[maxn];struct node
{int l,r,id,num;node(){}node(int l,int r,int id,int num):l(l),r(r),id(id),num(num){}bool operator<(const node &o)const{if(num==o.num) return r<o.r;return num<o.num;}
}query[maxn];struct bitTree{ll C[maxn];void init(){memset(C,0,sizeof(C));}void add(int i,ll val){while(i<maxn){C[i]+=val;i+=(i&(-i));}}ll sum(int i){ll ans=0;while(i){ans+=C[i];i-=(i&(-i));}return ans;}
}person,tim;void init()
{tim.init();person.init();
}
void myerase(int i)
{int val=a[i];tim.add(val,-val);person.add(val,-1);
}
void insert(int i)
{int val=a[i];tim.add(val,val);person.add(val,1);
}
void solve()
{sort(query,query+m);int L=1,R=0;ll ans=0;for(int i=0;i<m;i++){int l=query[i].l,r=query[i].r,id=query[i].id;while(l<L){insert(--L);int val=a[L];ans+=tim.sum(val)+(ll)val*(person.sum(maxn-1)-person.sum(val));}while(R<r){insert(++R);int val=a[R];ans+=tim.sum(val)+(ll)val*(person.sum(maxn-1)-person.sum(val));}while(l>L){int val=a[L];ans-=tim.sum(val)+(ll)val*(person.sum(maxn-1)-person.sum(val));myerase(L++);}while(R>r){int val=a[R];ans-=tim.sum(val)+(ll)val*(person.sum(maxn-1)-person.sum(val));myerase(R--);}res[id]=ans;}for(int i=0;i<m;i++){printf("%lld\n",res[i]);}
}
int main()
{scanf("%d",&T);while(T--){init();scanf("%d%d",&n,&m);a[0]=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=0;i<m;i++){int l,r;scanf("%d%d",&l,&r);int tmp=(int)sqrt(n);int num=(l-1)/tmp;query[i]=node(l,r,i,num);}solve();}return 0;
}