Game——题解

题目大意

两人玩游戏，先往集合里塞 p p 个数a[1,p]a[1,p]

A取个数加入自己分数，再往集合里塞接下来的数

B取个数加入自己分数，再往集合里塞接下来的数

……

两人都选最优策略，求最后A-B的分数差

n<=100000,ai<=100000,pi<=n,k(询问次数)<=2000，2s n <= 100000 , a i <= 100000 , p i <= n , k ( 询 问 次 数 ) <= 2000 ， 2 s

暴力没得说，堆 log l o g 一下

然后，上高端数据结构？

好像都是 log l o g 级的，还有一个常数媲美 log l o g 的斐波那契堆。。

继续玄学！！！

我们实际上只要开个计数数组就Ok了

维护当前最大的数，则这个指针显然是不升的：

如果进来一个大的，立刻就会被干掉了

所以均摊就是 O(max(ai)) O ( m a x ( a i ) ) 的

#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#define gt() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
#define __R register
#define LL long long
using namespace std;
static char buf[],*p1=buf,*p2=buf;
const int maxn=()+;
int n,Q,p,a[maxn],hsh[maxn];LL S;
inline int read(){
    int ret=;char ch=gt();
    while(ch<'0'||ch>'9') ch=gt();
    while(ch>='0'&&ch<='9') ret=ret*+ch-'0',ch=gt();
    return ret;
}
void write(LL x){if(x<) x=-x,putchar('-');if(x<) putchar(x+'0');else write(x/),putchar(x%+'0');}
int main(){
    n=read(),Q=read();
    for(__R int i=;i<=n;i++) S+=(a[i]=read());
    LL now;int lst;bool flg;
    while(Q--){
        p=read(),lst=,flg=(p&);
        for(__R int i=;i<=p;i++) hsh[a[i]]++,lst=a[i]>lst?a[i]:lst;
        now=lst,hsh[lst]--;
        for(__R int i=p+;i<=n;i++){
            while(lst&&!hsh[lst]) lst--;
            if(a[i]>=lst){if((i&)==flg) now+=a[i];}
              else{hsh[a[i]]++;if((i&)==flg) now+=lst;hsh[lst]--;}
        }
        for(__R int i=n+;lst;i++){
            while(lst&&!hsh[lst]) lst--;
            if((i&)==flg) now+=lst;
            hsh[lst]--;
        }
        write(now-(S-now)),putchar('\n');
    }
    return ;
}