【[Offer收割]编程练习赛11 D】排队接水

【题目链接】:http://hihocoder.com/problemset/problem/1488

【题意】



中文题

【题解】



莫队算法+树状数组;

首先贪心地知道,应该按照时间从小到大的顺序打水;

可以发现;

新增加一个人打水的话,对时间小于它的人打水没有影响;

只对时间大于它的人打水的时间有影响;

具体的;

对于时间大于它的打水的人的个数*这个人打水的时间;是新增加的打水时间;

然后同时还要加上这个人单独打水的时间;

即在它前面（时间比它小的打水的人）的所有打水时间总和+这个人的打水时间就是这个人的单独打水时间;

同样的道理

减去一个人也只会对它后面的人造成影响;

前面的人不受影响;

再减去它自身就可以了;

既然能够知道减少一个或者多一个人对答案的影响了;

则直接用莫队算法搞就好了



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)typedef pair<int,int> pii;
typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 2e4+100;struct abc
{
int l,r,id;
};int n,m,a[N],l,r,num;
LL bit[N],bit2[N],ans,out[N];
abc b[N];int lowbit(int x)
{
return x&(-x);
}bool cmp(abc a,abc b)
{
if (a.l/100==b.l/100)
return a.r < b.r;
else
return a.l < b.l;
}void add(int x,int key)
{
if (key==1)
{
int y = x-1;
LL sum = 0,cnt = 0;
while (y>0)
{
sum+=bit[y];
cnt+=bit2[y];
y-=lowbit(y);
}
ans+=sum+x+(num-cnt)*x;
y = x;
while (y<N-10)
{
bit[y]+=x;
bit2[y]++;
y+=lowbit(y);
}
num++;
}
else
{
int y = x-1;
LL sum = 0,cnt = 0;
while (y>0)
{
sum+=bit[y];
cnt+=bit2[y];
y-=lowbit(y);
}
ans-=sum+x+(num-cnt-1)*x;
y = x;
while (y<N-10)
{
bit[y]-=x;
bit2[y]--;
y+=lowbit(y);
}
num--;
}
}int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use
int T;
cin >> T;
while (T--)
{
rep1(i,0,N-10)
bit[i] = bit2[i] = 0;
cin >> n >> m;
rep1(i,1,n) cin >> a[i];
rep1(i,1,m)
{
cin >> b[i].l >> b[i].r;
b[i].id = i;
}
sort(b+1,b+1+m,cmp);
l = 1,r = 1,ans = 0,num = 0;
add(a[l],1);
rep1(i,1,m)
{
while (r<b[i].r) add(a[++r],1);
while (l>b[i].l) add(a[--l],1);
while (r>b[i].r) add(a[r--],-1);
while (l<b[i].l) add(a[l++],-1);
out[b[i].id] = ans;
}
rep1(i,1,m) cout << out[i] << endl;
}
return 0;
}