Hdu 6274（預處理+二分）

1、題面：

2、思路：

因為ai的範圍是1~1000，是以可以周遊所有1~1000的值，

是以将t，bi拆分為t = k1*ai+c1 , bi = k2*ai+c2.

得到k1,c1,k2,c2均為0~1000範圍内，将不等式化簡。

推導在圖中，因為c1 = t%ai，c2 = bi%ai

而且因為向下取整，隻考慮c1-c2<0的情況即可。

是以可以預處理這部分值，設定數組sum[x][y]表示ai = x，所有滿足bi%ai>=y的情況。

這樣求圖中不等式右邊部分時隻要-sum[i][x%i+1](表示減去c1小于c2這部分的值)這部分就行了。

然後每次通過二分求解求得t的最小值。

3、代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1005;
const int N = 1e5+10;
const LL INF = 1e13+10;
int sum[maxn][maxn],a[N],b[N],n,m;
bool pd(LL x,LL y){
	LL res = 0;
	for(int i=1;i<=1000;i++){
		res += x/i*sum[i][0];
		res -= sum[i][x%i+1];
	}
	return res>=y;
}
LL cal(LL x){
	LL l = 1,r = INF;
	while(l<=r){
		LL mid = (l+r)>>1LL;
		if(pd(mid,x)==true) r = mid-1;
		else l = mid+1;
	}
	return l;
}
int main(void){
	int T;
	scanf("%d",&T);
	while(T--){
		memset(sum,0,sizeof(sum));
		LL k = 0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++){
			scanf("%d",&b[i]);
			sum[a[i]][b[i]%a[i]]++;
			k += b[i]/a[i];
		}
		for(int i=1;i<=1000;i++){
			for(int j=i-1;j>=0;j--){
				sum[i][j] += sum[i][j+1];
			}
		}
		while(m--){
			int op,x,y;
			scanf("%d",&op);
			if(op==1){
				scanf("%d%d",&x,&y);
				k -= b[x]/a[x];
				k += b[x]/y;
				for(int i=b[x]%a[x];i>=0;i--)
					sum[a[x]][i]--;
				for(int i=b[x]%y;i>=0;i--)
					sum[y][i]++;
				a[x] = y;
			}
			else if(op==2){
				scanf("%d%d",&x,&y);
				k -= b[x]/a[x];
				k += y/a[x];
				for(int i=b[x]%a[x];i>=0;i--) 
					sum[a[x]][i]--;
				for(int i=y%a[x];i>=0;i--)
					sum[a[x]][i]++;
				b[x] = y;
			}
			else{
				scanf("%d",&x);
				printf("%lld\n",cal(x+k));
			}
		}
	}
	return 0;
}