There are two sequences a 1 , a 2 , ⋅ ⋅ ⋅ , a n a_1, a_2, · · · , a_n a1,a2,⋅⋅⋅,an, b 1 , b 2 , ⋅ ⋅ ⋅ , b n b_1, b_2, · · · , b_n b1,b2,⋅⋅⋅,bn. Let S ( t ) = ∑ i = 1 n ⌊ t − b i a i ⌋ S(t) = \sum_{i=1}^n\left\lfloor\dfrac{t-b_i}{a_i}\right\rfloor S(t)=∑i=1n⌊ait−bi⌋. 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)}The first line contains a integer T ( 1 ≤ T ≤ 5 ) T (1 ≤ T ≤ 5) T(1≤T≤5) representing the number of test cases. For each test case, the first line contains two integers n n n ( 1 ≤ n ≤ 100000 1 ≤ n ≤ 100000 1≤n≤100000), m m m ( 1 ≤ m ≤ 10000 1 ≤ m ≤ 10000 1≤m≤10000). The following line contains n integers representing the sequence a 1 a_1 a1, a 2 a_2 a2, · · · , a n a_n an. The following line contains n integers representing the sequence b 1 b_1 b1, b 2 b_2 b2, · · · , b n b_n bn. 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 ≤ a i ≤ 1000 , 1 ≤ b i , k ≤ 1 0 9 1 ≤ a_i ≤ 1000, 1 ≤ b_i, k ≤ 10^9 1≤ai≤1000,1≤bi,k≤109. And the number of queries (type 3 operation) in each test case will not exceed 1000.
For each query operation (type 3 operation), print the answer in one line.
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
17 87 65 72 58 74 310 2875
有两个序列a, b, 另 S ( t ) = ∑ i = 1 n ⌊ t − b i a i ⌋ S(t) = \sum_{i=1}^n\left\lfloor\dfrac{t-b_i}{a_i}\right\rfloor S(t)=∑i=1n⌊ait−bi⌋，有m次操作，每次操作为一下三种之一：
1 x y: 另 a x = y a_x = y ax=y2 x y: 另 b x = y b_x = y bx=y3 k: 回答min{t|k ≤ S(t)}。因为S(t)是具有单调性的，所以可以考虑二分 t t t的取值。 1 ≤ a i ≤ 1000 1\le a_i\le1000 1≤ai≤1000，将 a i a_i ai分类处理，求出 ⌊ t a i ⌋ \left\lfloor\dfrac{t}{a_i}\right\rfloor ⌊ait⌋的和。 S ( t ) = ∑ i = 1 n ⌊ t − b i a i ⌋ S(t) = \sum_{i=1}^n\left\lfloor\dfrac{t-b_i}{a_i}\right\rfloor S(t)=∑i=1n⌊ait−bi⌋，因为还有 ⌊ − b i a i ⌋ \left\lfloor\dfrac{-b_i}{a_i}\right\rfloor ⌊ai−bi⌋部分未处理，设 x 1 = t % a i , x 2 = b i % a i x1=t\%a_i, x2=b_i\%a_i x1=t%ai,x2=bi%ai，若 x 1 ≥ x 2 x1\ge x2 x1≥x2，则 x 2 x_2 x2部分的影响可以忽略，若 x 1 < x 2 x_1 < x_2 x1<x2则S(t)减一。同时维护 b i a i \frac{b_i}{a_i} aibi的整数部分，设和为tmp。
因为之前将数据按 a i a_i ai的值进行分类处理，所以将一组所对应的 x 2 x_2 x2进行处理。可以考虑通过树状数组或预处理来完成求 ≥ x 1 \ge x_1 ≥x1的数的个数的问题。(实践证明预处理貌似比树状数组快)。
则二分t时，若 S ( t ) − t m p ≥ k S(t)-tmp\ge k S(t)−tmp≥k，则移动上界，否则移动下届。
#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<algorithm> #include<cstring> #include<map> #include<vector> #include<queue> #include<iterator> #include<set> #define dbg(x) cout<<#x<<" = "<<x<<endl; #define INF 0x3f3f3f3f #define LLINF 0x3f3f3f3f3f3f3f3f #define eps 1e-6 using namespace std; typedef long long LL; typedef pair<int, int> P; const int maxn = 100100; const int mod = 998244353; int a[maxn], b[maxn], c[1020], d[1020][1020]; LL check(LL mid); int main() { int t, n, m, i, j, k; LL tmp, l, r, mid; scanf("%d", &t); while(t--) { tmp = 0; memset(c, 0, sizeof(c)); memset(d, 0, sizeof(d)); 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]); c[a[i]]++; k = b[i]%a[i]; for(j=0;j<=k;j++)d[a[i]][j]++; tmp += b[i]/a[i]; } while(m--) { int op, x, y; scanf("%d", &op); if(op == 1){ scanf("%d %d", &x, &y); c[a[x]]--, c[y]++; k = b[x]%a[x]; for(j=0;j<=k;++j)d[a[x]][j]--; k = b[x]%y; for(j=0;j<=k;++j)d[y][j]++; tmp += b[x]/y-b[x]/a[x]; a[x] = y; }else if(op == 2){ scanf("%d %d", &x, &y); k = b[x]%a[x]; for(j=0;j<=k;++j)d[a[x]][j]--; k = y%a[x]; for(j=0;j<=k;++j)d[a[x]][j]++; tmp += y/a[x]-b[x]/a[x]; b[x] = y; }else{ scanf("%d", &k); l = 0, r = 1e10; while(l<r){ mid = (l+r)/2; if(check(mid)-tmp>=k)r = mid; else l = mid+1; } printf("%lld\n", l); } } } return 0; } LL check(LL mid) { LL sum = 0; for(int i=1;i<=1000;i++){ sum += mid/i*c[i]-d[i][mid%i+1]; } return sum; }