题目
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
有n个小朋友需要接水，其中第i个小朋友接水需要ai分钟。
由于水龙头有限，小Hi需要知道如果为第l个到第r个小朋友分配一个水龙头，如何安排他们的接水顺序才能使得他们等待加接水的时间总和最小。
小Hi总共会有m次询问，你能帮助他解决这个问题吗？
假设3个小朋友接水的时间分别是2，3，4。如果他们依次接水，第一位小朋友等待加接水的时间是2，第二位小朋友是5，第三位小朋友是9。时间总和是16。
输入
第一行一个数T(T<=10)，表示数据组数
对于每一组数据：
第一行两个数n，m（1<=n,m<=20,000）
第二行n个数a1...an，表示每个小朋友接水所需时间(ai<=20,000)
接下来m行，每行两个数l和r
输出
对于每次询问，输出一行一个整数，表示答案。
样例输入
1
4 2
1 2 3 4
1 2
2 4
样例输出
4
16
分析
- 离线算法——莫队算法 O(n1.5logn)；
- 已知查询（l，r），用平衡树维护区间数据，可以O（logn）求解（l-1，r）、（l+1，r）、（l，r-1）、（l，r+1）；
- sqrt(n)分块，左端点在同一块中的查询为一组，组内按右端点排序，调节左右端点即可；
- 平衡树难写，每个排队时间不超过2e4，可以映射到数组，转换成数组区间求和，这里用树状数组；
代码
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef uint8_t byte;
typedef int64_t illong;
typedef uint64_t ullong;
typedef uint32_t uint;
#define CLEAN(x) memset(x,0,sizeof(x))
#define TR(i,obj) for(__typeof(obj.begin()) i=obj.begin();i!=obj.end();++i)
struct Node{
int l,r,ind;
void set(int l,int r,int ind){
this->l=l;
this->r=r;
this->ind=ind;
}
bool operator<(const Node &other)const;
};
const int tsize=1<<15;
int t,n,m,bsize;
int dat[tsize];
Node query[tsize];
illong cur,cl,cr;
illong dst[tsize];
bool Node::operator <(const Node &other)const{
int sb=l/bsize;
int ob=other.l/bsize;
if(sb!=ob) return sb<ob;
else return r<other.r;
}
struct Arr{
illong arr[tsize+1];
void add(int ind,illong value){
while(ind<=tsize){
arr[ind]+=value;
ind+=ind&-ind;
}
}
illong sum(int ind){
illong rs=0;
while(ind){
rs+=arr[ind];
ind-=ind&-ind;
}
return rs;
}
void reset(){
memset(arr,0,sizeof(arr));
}
};
Arr num,sum;
void rm(int ind){
illong value=dat[ind];
cur-=sum.sum(value);
cur-=value*(num.sum(tsize)-num.sum(value));
sum.add(value,-value);
num.add(value,-1);
}
void add(int ind){
illong value=dat[ind];
cur+=sum.sum(value)+value;
cur+=value*(num.sum(tsize)-num.sum(value));
sum.add(value,value);
num.add(value,1);
}
int main() {
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i){
scanf("%d",dat+i);
}
cl=0;
cr=0;
sum.reset();
num.reset();
sum.add(dat[0],dat[0]);
num.add(dat[0],1);
cur=dat[0];
bsize=sqrt(n);
for(int i=0;i<m;++i){
int l,r;
scanf("%d%d",&l,&r);
--l;--r;
query[i].set(l,r,i);
}
sort(query,query+m);
for(int i=0;i<m;++i){
const Node &it=query[i];
while(cl<it.l)
rm(cl++);
while(cl>it.l)
add(--cl);
while(cr<it.r)
add(++cr);
while(cr>it.r)
rm(cr--);
dst[it.ind]=cur;
}
for(int i=0;i<m;++i){
printf("%lld\n",dst[i]);
}
}
return 0;
}
网友评论