题目传送门（内部题62）
输入格式
第一行两个整数$n,K$表示序列长度和游戏数
第二行$n$个数为序列$a_i$
第三行$K$个数，为$p_i$
输出格式
输出有$K$行，第$i$行为第$i$次游戏的分数差
样例
样例输入：
5 2
2 4 2 3 5
4 3
样例输出：
2
6
数据范围与提示
对于$10\%$的数据，$1leqslant nleqslant 10$
对于$30\%$的数据，$1leqslant nleqslant 600$
对于$50\%$的数据，$1leqslant nleqslant 10,000,1leqslant kleqslant 1,000$
对于$100\%$的数据，$nleqslant 100,000,kleqslant 2,000,1leqslant aileqslant n,1leqslant pileqslant n,kleqslant n$
题解
如果你做过这道题，你可能会知道这道题中的分数差是指$Alice-Bob$，而不是$abs(Alice-Bob)$，某同学博客$downarrow$
剩下的就没啥好说的了，开个桶维护一下即可，不过既然它卡常，我们最好还是先离散化一下……
我也不知道这出题人出的都是什么玄学题，就是想吐槽出题人（多说一句不取绝对值不好嘛）……
时间复杂度：$Theta(n imes k)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
int n,K;
int a[100001],b[100001],t[100001];
int main()
{
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
int len=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+len+1,a[i])-b;
while(K--)
{
int p;scanf("%d",&p);
int res=0;
long long Alice=0,Bob=0;
int now=0;
for(int j=1;j<=p;j++)
{
res=max(a[j],res);
t[a[j]]++;
}
Alice+=b[res];
t[res]--;
while(!t[res]&&res)res--;
for(int j=p+1;j<=n;j++)
{
now^=1;
if(now)
{
if(a[j]>=res)Bob+=b[a[j]];
else
{
t[a[j]]++;
Bob+=b[res];
t[res]--;
while(!t[res]&&res)res--;
}
}
else
{
if(a[j]>=res)Alice+=b[a[j]];
else
{
t[a[j]]++;
Alice+=b[res];
t[res]--;
while(!t[res]&&res)res--;
}
}
}
while(res)
{
now^=1;
if(now)Bob+=b[res];
else Alice+=b[res];
t[res]--;
while(!t[res]&&res)res--;
}
printf("%lld
",Alice-Bob);
}
return 0;
}
rp++