题意

两个1e5的数组a,b，定义\(S(t)=\left \lfloor \frac{t-b_i}{a_i} \right \rfloor\)，有三个操作

1 x y：将\(a[x]\)变为\(y\)

2 x y：将\(b[x]\)变为\(y\)

3 x：求使得\(S(t)\geq k\)的最小\(k\)

其中\(a_i\leq 1000\),\(b_i,k\leq 1e9\)

思路

这题主要突破口在于\(a_i\leq 1000\)

我们先从下整除下手，

\(\left \lfloor \frac{t-b_i}{a_i} \right \rfloor=\left \lfloor \frac{k_1a_i+c_1-k_2a_i-c_2}{a_i} \right \rfloor=k_1-k_2+\left \lfloor \frac{c_1-c_2}{a_i} \right \rfloor\)

其中

\(c_1=t\bmod a_i\)

\(c_2=b_i \bmod a_i\)

\(k_1=t/ a_i\)

\(k_2=b_i/ a_i\)

\(\left \lfloor \frac{c_1-c_2}{a_i} \right \rfloor=\left\{\begin{matrix}
-1,c_1<c_2\\ 0,c_1\geq c_2
\end{matrix}\right.\)

那么

\(S(t)=ret+\sum_{i=1}^{1000}(\frac{t}{i}cnt[i]-f[i][t\bmod i+1])\)

其中

\(f[x][y]\)表示\(a_i=x\)时，\(y \leq c_2 \leq 1000\)的个数

\(cnt[x]\)表示\(a_i=x\)的个数，即\(f[x][0]\)

\(ret\)表示所有数\(k_2\)的和

这题就做完了。。

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-6;

const int mod = 998244353;

const int maxn = 2e6+100;

const int maxm = 2e6+100;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

int n,m;

ll a[maxn],b[maxn];

ll f[1111][1111];

ll ret;

ll S(ll t){

	ll ans = 0;

	for(int i = 1; i <= 1000; i++){

		ans+=t/i*f[i][0]-f[i][t%i+1];

	}

	return ans-ret;

}

int main() {

    int T;

    scanf("%d", &T);

    while(T--){

    	scanf("%d %d", &n, &m);

    	for(int i = 1; i <= n; i++){

    		scanf("%lld",&a[i]);

    	}

    	for(int i = 1; i <= n; i++){

    		scanf("%lld", &b[i]);

    	}

    	mem(f,  0);

    	ret = 0;

    	for(int i = 1; i <= n; i++){

    		ret+=b[i]/a[i];

    		f[a[i]][b[i]%a[i]]++;

    	}

    	for(int i = 1; i <= 1000; i++){

    		for(int j = i-1; j >= 0; j--){

    			f[i][j]+=f[i][j+1];

    		}

    	}

    	while(m--){

    		int op,x;

    		ll y;

    		scanf("%d",&op);

    		if(op<=2){

    			scanf("%d %lld", &x ,&y);

    			if(op==1){

	    			ret-=b[x]/a[x];

	    			ret+=b[x]/y;

	    			for(int i = b[x]%a[x]; i >= 0; i--)f[a[x]][i]--;

	    			for(int i = b[x]%y; i >= 0; i--)f[y][i]++;

	    			a[x]=y;

    			}

    			else if(op==2){

    				ret-=b[x]/a[x];

    				ret+=y/a[x];

    				for(int i = b[x]%a[x]; i >= 0; i--)f[a[x]][i]--;

    				for(int i = y%a[x]; i >= 0; i--)f[a[x]][i]++;

    				b[x]=y;

    			}

    		}

    		else{

    			ll ans = 0;

    			scanf("%lld", &y);

    			ll l = 0,r = 1e13;

    			while(l<=r){

    				ll mid = l+r>>1;

    				if(S(mid)>=y){

    					ans=mid;r=mid-1;

    				}

    				else l=mid+1;

    			}

    			printf("%lld\n",ans);

    		}

    	}

    }

    return 0;

}

/*

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

 */

巴特西

HDU 6274 Master of Sequence (暴力+下整除)

题意

思路

代码

最新文章

热门文章