hdu 6274 Master of Sequence(公式推导)
程序员文章站
2022-06-07 21:44:10
...
这题一看a的范围比较小,肯定就是要往这上面做文章
(t-bi)/ai = =( (k1ai + c)-(k2ai-d) ) / ai k1和k2可以快速计算 维护c和d的个数
当c>d 贡献为0 当c
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <bits/stdc++.h>
typedef long long LL;
const int N =1e6+100;
using namespace std;
typedef long long LL;
const LL mod = 998244353;
struct node
{
LL a, b;
} p[N];
int num[1002][1002],cnt[1002];
int main()
{
//cout<<-1/3<<endl;
int t;
scanf("%d", &t);
while(t--)
{
int n, m;
LL s=0;
scanf("%d %d", &n, &m);
memset(num,0,sizeof(num));
memset(cnt,0,sizeof(cnt));
for(int i=1; i<=n; i++) scanf("%lld",&p[i].a);
for(int i=1; i<=n; i++)
{
scanf("%lld",&p[i].b);
s+=(p[i].b/p[i].a);
num[p[i].a][p[i].b%p[i].a]++;
cnt[p[i].a]++;
}
for(int i=1;i<=1000;i++)
{
for(int j=i-1;j>=0;j--)
{
num[i][j]+=num[i][j+1];
}
}
while(m--)
{
LL x, y, z;
scanf("%lld", &x);
if(x==1)
{
scanf("%lld %lld", &y, &z);
for(int i=p[y].b%p[y].a;i>=1;i--)num[p[y].a][i]--;
s-=(p[y].b/p[y].a);
cnt[p[y].a]--;
p[y].a=z;
s+=(p[y].b/p[y].a);
cnt[z]++;
for(int i=p[y].b%z;i>=1;i--)num[z][i]++;
}
else if(x==2)
{
scanf("%lld %lld", &y, &z);
for(int i=p[y].b%p[y].a;i>=1;i--)num[p[y].a][i]--;
s-=(p[y].b/p[y].a);
p[y].b=z;
s+=(p[y].b/p[y].a);
for(int i=z%p[y].a;i>=1;i--)num[p[y].a][i]++;
}
else
{
LL k;
scanf("%lld", &k);
LL l=1, r=1e13, ans;
while(l<=r)
{
LL mid=(l+r)/2;
LL sum=-s;
for(int i=1; i<=1000; i++) sum=sum+mid/i*cnt[i]-num[i][mid%i+1];
if(sum>=k)r=mid-1,ans=mid;
else l=mid+1;
}
printf("%lld\n",ans);
}
}
}
return 0;
}
上一篇: L2-021 点赞狂魔