标签：ai bi 更新 250005 int 序列 -- cc
- 考场思路是，离线处理询问，从大到小枚举bi，对每个ai维护已被统计的询问区间
- 由于数据随机，我们似乎可以感受到已统计询问区间扩张的次数不会太大，于是自然想到有没有办法精准扩张呢？很遗憾，难做
- 另一个思路是，区间扩张的情况往往集中出现在最大的几个bi
- 于是引入分块的“大段维护，局部朴素”思想，我们进行一部分区间扩张后，朴素地处理剩下来的情况
- 题解做法是，对于每次操作，并行考虑两种修改方法：①从ai出发，找到bi，更新ai ②从bi出发，找到ai,更新ai
- 考虑对最大的几个bi应用方法②修改，那么我们只需要对较小的ai应用①修改
- 修改次数期望为\(\sum (1-\frac{x}{n})^{i+1}\)（考虑每一步对期望的贡献）
- 用等比数列求和公式：约等于\(\frac {n}{x}\)，解毕
点击查看代码
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
long long ans[250005];
int c[250005],k[250005],la[250005];
int read1()
{
char cc=getchar();
while(!(cc>=48&&cc<=57))
{
if(cc=='-')
{
break;
}
cc=getchar();
}
bool f=false;
int s=0;
if(cc=='-')
{
f=true;
}
else
{
s=cc-48;
}
while(1)
{
cc=getchar();
if(cc>=48&&cc<=57)
{
s=s*10+cc-48;
}
else
{
break;
}
}
if(f==true)
{
s=-s;
}
return s;
}
struct t1
{
int id,va;
}a[250005],b[250005];
int A[250005],B[250005];
bool cmp(t1 a,t1 b)
{
return a.va<b.va;
}
int main()
{
int T;
cin>>T;
while(T--)
{
memset(c,0,sizeof(c));
int n,q;
cin>>n>>q;
for(int i=0;i<n;i++)
{
la[i]=q+1;
a[i].id=i;
a[i].va=read1();
A[i]=a[i].va;
}
sort(a,a+n,cmp);
for(int i=0;i<n;i++)
{
b[i].id=i;
b[i].va=read1();
B[i]=b[i].va;
}
sort(b,b+n,cmp);
for(int i=1;i<=q;i++)
{
k[i]=read1();
if(c[k[i]]==0)
{
c[k[i]]=i;
}
ans[i]=0;
}
int p=n;
for(int i=n-1;i>=max(n-500,0);i--)
{
while(p-1>=0&&a[p-1].va>b[i].va)
{
p--;
}
for(int j=0;j<p;j++)
{
int k=b[i].id-a[j].id;
if(k<0)
{
k+=n;
}
if(c[k]==0)
{
continue;
}
if(c[k]<la[a[j].id])
{
ans[c[k]]+=(b[i].va);
ans[la[a[j].id]]-=(b[i].va);
la[a[j].id]=c[k];
}
}
}
for(int i=0;i<n;i++)
{
for(int j=1;j<la[i];j++)
{
A[i]=max(A[i],B[(i+k[j])%n]);
ans[j]+=A[i];
ans[j+1]-=A[i];
}
}
for(int i=1;i<=q;i++)
{
ans[i]+=ans[i-1];
printf("%lld\n",ans[i]);
}
}
return 0;
}
标签：ai,
bi,
更新,
250005,
int,
序列,
--,
cc
From： https://www.cnblogs.com/watersail/p/18334313