这回被阴得比较惨，不过也是自己没好好想，，
T1被阴是因为误认为 S2 有序。其实需要先排序再求中位数。然后题解是说，这个无序数列比较均匀，所以每次中位数的变化是常数级的，那个指针维护一下中位数就好了
T2被阴是因为觉得差要加上绝对值。优先队列搞到\(O(nk \log n)\)。
若将初始集合里的元素放入一个桶，新加入的元素若比桶里最大元素还要大，就被选走了，也就是说桶里发生的决策是单调递减的，维护个指针指向桶内最大元素乱搞一下
T3不会搞 dp，写了个 dfs 乱搞然后爆 0
T1
#include<bits/stdc++.h>
using namespace std;
#define re register
const int N=1.8e8+11;
const int N1=1.3e7+11;
int n,k,w,sl;
long long p[N1];
int s[N1],s2[N1];
int ton[2*N1];
bool fp[N];
double ans;
void get_prime()
{
for(re int i=2;i<N;i+=(i&1)+1)
{
if(!fp[i])
p[++sl]=i;
for(re int j=1;j<=sl&&p[j]*i<N;j++)
{
fp[p[j]*i]=1;
if(!(i%p[j]))
break;
}
}
return;
}
void pre()
{
for(int i=1;i<=n;i++)
{
s[i]=p[i]*i%w;
s2[i]=s[i]+s[i/10+1];
}
return;
}
signed main()
{
cin>>n>>k>>w;
get_prime();
pre();
re int mid1=0,mid2=0;
re int mid=0;
re int l;
int md=(k>>1);
int sl=0;
for(re int i=1;i<=k;i++)
ton[s2[i]]++;
if(k&1)
{
md++;
int zd=2*w-2;
re int i=-1;
while((sl+=ton[++i])<md);
l=sl;
mid=i;
ans+=mid;
i=k;
while(++i<=n)
{
ton[s2[i]]++;
ton[s2[i-k]]--;
s2[i]>mid?:l++;
s2[i-k]>mid?:l--;
if(l-ton[mid]>=md)
{
l-=ton[mid];
while(!ton[--mid]);
}
if(k-l>=md)
{
while(!ton[++mid]);
l+=ton[mid];
}
ans+=mid;
}
printf("%.1lf\n",ans);
}
else
{
int zd=2*w-2;
int wz;
re int i=-1;
while((sl+=ton[++i])<md);
l=sl;
mid1=mid2=i;
if(md==l)
while(!ton[++mid2]);
ans+=(double(mid1+mid2))/2.0;
i=k;
int t=n-i;
while(t--)
{
++i;
ton[s2[i]]++;
ton[s2[i-k]]--;
s2[i]>mid1?:l++;
s2[i-k]>mid1?:l--;
if(l-ton[mid1]>=md)
{
l-=ton[mid1];
while(!ton[--mid1]);
}
if(k-l>md)
{
while(!ton[++mid1]);
l+=ton[mid1];
}
mid2=mid1;
if(l==md)
while(!ton[++mid2]);
ans+=(double(mid1+mid2))/2.0;
}
printf("%.1lf\n",ans);
}
return 0;
}
T2
#include<bits/stdc++.h>
using namespace std;
const int N=100011;
int p,k,n,a[N];
int ton[N];
inline int read()
{
int s=0;
char ch=getchar();
while(ch>‘9‘||ch<‘0‘)
ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)
{
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s;
}
int main()
{
n=read();
k=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=k;i++)
{
int x=0;
long long peo[2];
peo[1]=peo[0]=0;
p=read();
int pi=p,sl=1;
for(int j=1;j<p;j++)
{
ton[a[j]]++;
x=max(a[j],x);
}
while(sl<=n)
{
if(pi<=n&&x<a[pi])
peo[sl&1]+=a[pi];
else
{
if(pi<=n)
ton[a[pi]]++;
peo[sl&1]+=x;
ton[x]--;
while(!ton[x])
x--;
}
pi++;
sl++;
}
printf("%lld\n",peo[1]-peo[0]);
}
return 0;
}