# 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

$O(1)$更新

• 当 $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$

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

$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;
}