地中海气候

　

地中海气候

题意

有一个包含 N 个正整数的序列，序列元素不大于 N。紧接着，他们维护了一

个可重集合 S，包含序列中的前 P 个元素。Alice 先手，二人轮流进行下面的一

系列操作：

1. 从集合 S 中拿走一个元素，加到玩家的总分上面；
2. 将序列中的下一个数字(如果存在)添加到集合 S 中；

   假使二人都尽力使自己的总分最大，设游戏的结果为 Alice 的总分与 Bob 的

   总分之差，那么请你在给定序列和集合元素的情况下，输出游戏的结果

   N<=100000,Q<=2000

题解

为了简单，我们可以看做本来只有P-1个元素，然后是先插入，再取出

比较显然的性质是，每次都是取的multiset中最大那个元素

于是我们就直接上个multiset或者优先队列，成功得到再nlogn的时间内搞定每次询问

那么现在的问题是怎么优化呢

我们必须优化到O(n)内完成每次查询

必须发现的一点是，每次我们只会往这个multiset中插一个值，而且如果这个值大于了当前的最大值，就一定会被马上取走

那么也就是说，这个最大值一定是不增的

那么如果当前增加值是大于这个最大值，就一定给当前的人加上这么多分

那如果不是呢？我们会取出最大值，然后插入当前的这个值。

那么问题来了怎么实现呢？

二分链表？或者干脆直接上个二叉堆？似乎那个log怎么都砍不掉啊？

然而…考虑到所有数都小于等于n，我们可以直接用一个数组来维护出现次数…成功实现O(1)插入，然后更新最大值暴力更新即可，由于是单调不增的，可以证明是O(n)的

于是最后O(NQ)解决本题

记得开ll

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=100005;
int n,m;
int a[N],cnt[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        int p;
        scanf("%d",&p);
        int mx=0;
        for(int j=1;j<=p-1;j++){
            cnt[a[j]]++;
            mx=max(mx,a[j]);
        }
        ll ans=0;
        for(int j=1,k=1;j<=n;j++,k*=-1){
            if(p+j-1<=n){
                if(a[p+j-1]>mx)
                    ans+=k*a[p+j-1];
                else{
                    ans+=k*mx;
                    cnt[a[p+j-1]]++;
                    cnt[mx]--;
                    while(mx>0&&!cnt[mx])
                        mx--;
                }
            }
            else{
                ans+=k*mx;
                cnt[mx]--;
                while(mx>0&&!cnt[mx])
                    mx--;
            }
        }
        printf("%lld\n",ans);
    }
}

相关阅读

当当卖身记：证明只挣读书人钱成不了气候

当当还是被卖了。这个曾经号称&ldquo;中国的亚马逊&rdquo;、&ldquo;最大的中文网上书城&rdquo;，中国第一家完全基于线上业务、在美

艺术衍生品电商为何始终难成气候？

由于尚未出现独角兽平台出现，也不失为创业者们从各环节切入艺术衍生品市场大展拳脚的好时机。艺术家授权厂商使用其创作的艺术品进

艺术衍生品电商为何始终难成气候？

由于尚未出现独角兽平台出现，也不失为创业者们从各环节切入艺术衍生品市场大展拳脚的好时机。艺术家授权厂商使用其创作的艺术品进