正题
题目链接:https://www.luogu.com.cn/problem/P6013?contestId=25945
题目大意
n张牌，玩家1从顶拿若干张，之后玩家2拿若干张。
若牌的和大于K那么分数为0否则为牌的和。
求K为多少时玩家1必胜。
解题思路
我们枚举玩家1拿多少张，然后用一个指针记录玩家2拿到哪里时比玩家1大。若玩家1的和为l，玩家2刚好比玩家1拿的大时的和为r。
那么[l,r−1]这个范围都是可以选择的K,用树状数组区间覆盖即可。
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define lowbit(x) (x&-x)
using namespace std;
const ll N=1e6+10;
ll n,a[N],t[N],K,ans;
void Change(ll x,ll w){
if(!x) return;
while(x<=K){
t[x]+=w;
x+=lowbit(x);
}
return;
}
ll Ask(ll x){
ll ans=0;
while(x){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
scanf("%lld",&K);
ll l=2,z=a[1],sum=0;
for(ll i=1;i<=n;i++){
sum+=a[i];z-=a[i];
while(l<=n&&z<sum)
z+=a[l++];
if(sum<z){
Change(sum,1);
Change(z,-1);
}
if(z<sum)
Change(sum,1);
}
for(ll i=1;i<=K;i++)
if(Ask(i)) ans++;
printf("%lld\n",ans);
for(ll i=1;i<=K;i++)
if(Ask(i)) printf("%lld ",i);
}