hdu - 6274

Posted by WildCow on April 21, 2018

Master of Sequence

Time Limit: 1000 MS
Memory Limit: 32768 KB

Description

There are two sequences $a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_n$. Let $S(t) = \sum_{i=1}^{n}\left \lfloor \frac{t-b_i}{a_i} \right \rfloor$ . There are m operations within three kinds as following:

  • 1 x y: change value ax to y.
  • 2 x y: change value bx to y.
  • 3 k: ask min{t|k ≤ S((t))}

Input

The first line contains a integer T $(1\leqslant T \leqslant 5)$ representing the number of test cases. For each test case, the first line contains two integers n $(1\leqslant n \leqslant 100000)$, m $(1\leqslant m \leqslant 100000)$. The following line contains n integers representing the sequence $a_1,a_2,\cdots,a_n$. The following line contains n integers representing the sequence $b_1,b_2,\cdots,b_n$. The following m lines, each line contains two or three integers representing an operation mentioned above. It is guaranteed that, at any time, we have $1\leqslant a_i \leqslant 1000,1\leqslant b_i,k \leqslant 10^9$. And the number of queries, type 3 operation in each test case will not exceed 1000.

Output

For each query operation, type 3 operation, print the answer in one line.

Sample Input

2
4 6
2 4 6 8
1 3 5 7
1 2 3
2 3 3
3 15
1 3 8
3 90
3 66
8 5
2 4 8 3 1 3 6 24
2 2 39 28 85 25 98 35
3 67
3 28
3 73
3 724
3 7775

Sample Output

17
87
65
72
58
74
310
2875


题目还是很有趣的

题意很明显我就不解释了

很显然 $S(t)$ 满足单调性

我们可以二分 $t$ 来算

然后问题来了

我们要怎么 check

直接暴力 $O(n)$ 肯定被 T 飞

但是我觉得肯定没法在直接运算上优化了

有一个很明显的思路点拨就是 a 最大只有 1000

于是想着能不能预处理

然后根据操作修改预处理的结果

在 $S(t)$ 中

我们令 $t = k_{1i} * a_{i} + c_{1i}, b_i = k_{2i} * a_i + c_{2i}$

那么我们有$S(t)=K_1+K_2+\sum_{i=1}^{n}\left \lfloor \frac{c_{2i}- c_{1i}}{a_i} \right \rfloor$

其中 $K1 = \sum_{i=1}^{n}k_{1i}, K2 = \sum_{i=1}^{n}k_{2i}$

然后我们先来看 $K2$ 怎么求

可以在读入的时候直接预处理出来

即 $K_2 = \sum_{i = 1}^{n}\left \lfloor \frac{b_i}{a_i} \right \rfloor$

当 $a_x$变成 $y$ 的时候

有 $K_2 = K_2 - \left \lfloor \frac{b_i}{a_i} \right \rfloor + \left \lfloor \frac{b_i}{y} \right \rfloor$

当 $b_x$ 变成 $y$ 的时候

有 $K_2 = K_2 - \left \lfloor \frac{b_i}{a_i} \right \rfloor + \left \lfloor \frac{y}{a_i} \right \rfloor$

$O(1)$更新

然后是 $K_1
$

因为 $a_i$ 最大才 1000

所以我们可以开一个计数数组维护一下 $a$ 中每个数字出现的次数

那么有 $K_1 = \sum_{i = 1}^{1000}mid / i * cnt_{a_i}$

可以 $O(1000)$ 求

然后考虑 $\sum_{i=1}^{n}\left \lfloor \frac{c_{2i}- c_{1i}}{a_i} \right \rfloor$

因为 $c_{2i},c_{1i} < a_i$

所以:

  • 当 $c_{2i} \geqslant c_{1i}$ 时,有 $\left \lfloor \frac{c_{2i}- c_{1i}}{a_i} \right \rfloor = 0$
  • 当 $c_{2i}< c_{1i} $ 时,有 $\left \lfloor \frac{c_{2i}- c_{1i}}{a_i} \right \rfloor = -1$

于是变成我们要讨论

在 $b$ 中

有多少个 $i$

满足 $b_i \% a_i > t\%a_i$

于是我们定义二维数组 $cnt$

$cnt[x][y]$ 表示 $a$ 中满足 $a_i =x$ 且 $b_i \% a_i \geqslant y$ 的 $i$ 的个数

那么 $cnt[x][0]$ 就是 $a_i$ 中等于 $x$ 的个数

所以满足 $b_i \% a_i > t\%a_i$ 的 $a_i$ 的个数有 $\sum_{i=1}^{1000}cnt[i][t\%i+1]$

$ O(1000)$算出最后再减掉就好了


#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100010;

int n, m;
int ma[N];
int mb[N];
int cnt[1010][1010];
int w;
LL t;

bool check(LL x)
{
    LL ans;

    ans = 0;
    for(int i = 1; i <= 1000; i ++){
        ans += x / i * cnt[i][0];
        ans -= cnt[i][x % i + 1];
    }
    if(t + w <= ans){
        return true;
    }
    else{
        return false;
    }
}

int main()
{
    int ncase;

    scanf("%d", &ncase);
    while(ncase --){
        memset(cnt, 0, sizeof(cnt));
        t = 0;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i ++){
            scanf("%d", &ma[i]);
        }
        for(int i = 1; i <= n; i ++){
            scanf("%d", &mb[i]);
        }
        for(int i = 1; i <= n; i ++){
            t += mb[i] / ma[i];
            cnt[ma[i]][mb[i] % ma[i]] ++;
        }
        for(int i = 1; i <= 1000; i ++){
            for(int j = i - 1; j >= 0; j --){
                cnt[i][j] += cnt[i][j + 1];
            }
        }
        for(int i = 0; i < m; i ++){
            int o;

            scanf("%d", &o);
            if(o == 1){
                int x, y;

                scanf("%d%d", &x, &y);
                for(int i = mb[x] % ma[x]; i >= 0; i --){
                    cnt[ma[x]][i] --;
                }
                for(int i = mb[x] % y; i >= 0; i --){
                    cnt[y][i] ++;
                }
                t -= (mb[x] / ma[x]);
                t += (mb[x] / y);
                ma[x] = y;
            }
            else if(o == 2){
                int x, y;

                scanf("%d%d", &x, &y);
                for(int i = mb[x] % ma[x]; i >= 0; i --){
                    cnt[ma[x]][i] --;
                }
                for(int i = y % ma[x]; i >= 0; i --){
                    cnt[ma[x]][i] ++;
                }
                t -= (mb[x] / ma[x]);
                t += (y / ma[x]);
                mb[x] = y;
            }
            else{
                LL ans;
                LL l, r;

                scanf("%d", &w);
                l = 1;
                r = 1e13;
                while(l <= r){
                    LL mid;

                    mid = l + ((r - l) >> 1);
                    if(check(mid)){
                        r = mid - 1;
                        ans = mid;
                    }
                    else{
                        l = mid + 1;
                    }
                }
                printf("%lld\n", ans);
            }
        }
    }

    return 0;
}