Related Problem

Description

input

Output

Solution

可以根据操作x分类

当x=1或x=2时，暴力维护A或B就好

对于x=3的情况：

我们将原式拆开处理
∑ i = 1 n ⌊ T − B [ i ] A [ i ] ⌋ = ∑ i = 1 n ( ⌊ T A [ i ] ⌋ − ⌊ B [ i ] A [ i ] ⌋ − ( T % A [ i ] < B [ i ] % A [ i ] ) \sum_{i=1}^{n}\lfloor \frac{T-B[i]}{A[i]} \rfloor=\sum_{i=1}^{n}(\lfloor \frac{T}{A[i]} \rfloor-\lfloor \frac{B[i]}{A[i]} \rfloor-(T\%A[i]<B[i]\%A[i]) i=1∑n​⌊A[i]T−B[i]​⌋=i=1∑n​(⌊A[i]T​⌋−⌊A[i]B[i]​⌋−(T%A[i]<B[i]%A[i])
我们用一个 s u m [ i ] [ j ] sum[i][j] sum[i][j]表示当A[x]=i时 B [ x ] % A [ x ] = j B[x]\%A[x]=j B[x]%A[x]=j的个数

将sum[i]求前缀和

此时我们在询问时就可以枚举A[i]的大小算出来 ⌊ B [ i ] A [ i ] ⌋ \lfloor \frac{B[i]}{A[i]} \rfloor ⌊A[i]B[i]​⌋的答案，因为（A[i]最大为1000，所以肯定比穷举要优）

随后T二分，判断合法性，可以很快算出来答案

该时间复杂度是 O ( l o g N × M ) O(logN \times M) O(logN×M)的，其中N是二分的范围，M是1000，即A[i]的最大值

总时间复杂度
O ( l o g N × M × m ) O(logN \times M \times m) O(logN×M×m)

#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 100001
#define M 1000
#define open(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int n,m,i,l,r,mid,x,y,op,t,a[N],b[N];
long long tot,sum[M+10][M+10],c[M+10][M+10];
void updata(int x)
{
    sum[x][0]=c[x][0];
    for (int i=1;i<=M;i++)
        sum[x][i]=sum[x][i-1]+c[x][i];
}
bool check(int k,int t)
{
    long long ans=-tot;
    for (int i=1;i<=M;i++)
        ans+=1ll*sum[i][M]*(t/i)-1ll*(sum[i][M]-sum[i][t%i]);
    return (ans>=k);
}
int main()
{
    open("calculate");
    scanf("%d",&t);
    for (;t;t--)
    {
    	memset(c,0,sizeof(c));
    	memset(sum,0,sizeof(sum));
    	tot=0;
        scanf("%d%d",&n,&m);
        for (i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for (i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
            tot+=1ll*b[i]/a[i];
            c[a[i]][b[i]%a[i]]++;
        }
        for (i=1;i<=M;i++) 
            updata(i);
        for (i=1;i<=m;i++)
        {
            scanf("%d%d",&op,&x);
            if (op==3)
            {
                l=0; r=1e9;
                while (l<r)
                {
                    mid=(l+r)/2;
                    if (check(x,mid)) r=mid;else l=mid+1;
                }
                printf("%d\n",l);
            }else scanf("%d",&y);
            if (op==1)
            {
                c[a[x]][b[x]%a[x]]--;
                tot-=1ll*b[x]/a[x];
                updata(a[x]);
                a[x]=y;
                c[a[x]][b[x]%a[x]]++;
                tot+=1ll*b[x]/a[x];
                updata(a[x]);
            }
            if (op==2)
            {
                c[a[x]][b[x]%a[x]]--;
                tot-=1ll*b[x]/a[x];
                b[x]=y;
                c[a[x]][b[x]%a[x]]++;
                tot+=1ll*b[x]/a[x];
                updata(a[x]);
            }
        }
    }
    return 0;
}