Description

Input

Output

Data Constraint

Solution

• 設前綴和 g[i][j] 表示 A 為 i 、B 為 j 的數量。

• 這樣就能 O(1) 算出 t 的值，值改變時暴力維護即可。

• 時間復雜度 O(T?M?MaxAi) 。

Code

#include<cstdio> #include<cstring> using namespace std; const int N=1e5+1,M=1001; int n,m,mx; long long num; long long g[M][M]; int a[N],b[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void write(long long x){if(x>9) write(x/10);putchar(x%10+'0');} inline int max(int x,int y){return x>y?x:y;} inline long long check(long long t) {long long sum=-num,all;for(int i=1;i<=mx;i++)if(all=g[i][i-1]) sum+=t/i*all-(all-g[i][t%i]);return sum; } int main() {int T=read();while(T--){n=read(),m=read(),num=mx=0;memset(g,0,sizeof(g));for(int i=1;i<=n;i++) mx=max(mx,a[i]=read());for(int i=1;i<=n;i++) num+=(b[i]=read())/a[i],g[a[i]][b[i]%a[i]]++;for(int i=1;i<=mx;i++)for(int j=1;j<=mx;j++) g[i][j]+=g[i][j-1];while(m--){int type=read();if(type==1){int x=read(),y=read();for(int i=b[x]%a[x];i<a[x];i++) g[a[x]][i]--;num-=b[x]/a[x];mx=max(mx,a[x]=y);num+=b[x]/y;for(int i=b[x]%y;i<a[x];i++) g[y][i]++;}elseif(type==2){int x=read(),y=read();for(int i=b[x]%a[x];i<a[x];i++) g[a[x]][i]--;num-=b[x]/a[x];b[x]=y;num+=y/a[x];for(int i=y%a[x];i<a[x];i++) g[a[x]][i]++;}else{int k=read();long long l=0,r=1e12+1e9;while(l<r){long long mid=(l+r)>>1;if(check(mid)<k) l=mid+1; else r=mid;}write(l),putchar('\n');}}}return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的JZOJ 5439. 【NOIP2017提高A组集训10.31】Calculate的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。