欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu 6274 Master of Sequence(公式推导)

程序员文章站 2022-06-07 21:44:10
...

hdu 6274 Master of Sequence(公式推导)
hdu 6274 Master of Sequence(公式推导)
这题一看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;
}