本文主要是介绍Master of Sequence HDU - 5441，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=6274
借鉴张图片
想了很久 就是没想到把公式转化一下 智障啊
除数与模数分开处理 对于1000个模数每一个都开一个1000的树状数组维护b[i]%a[i]即可
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int maxm=1e3+10;struct node
{ll pre[maxm];
};node tree[maxm];
ll a[maxn],b[maxn],book[maxm];
ll n,m,q,sum;template <class T>
inline void _cin(T &ret)
{char c;ret = 0;while((c = getchar()) < '0' || c > '9');while(c >= '0' && c <= '9'){ret = ret * 10 + (c - '0');c = getchar();}
}ll lowbit(ll x)
{return x&(-x);
}void update(ll *gou,ll tar,ll val)
{ll i;for(i=tar;i<=m;i+=lowbit(i)) gou[i]+=val;
}ll query(ll *gou,ll tar)
{ll res,i;res=0;for(i=tar;i>0;i-=lowbit(i)) res+=gou[i];return res;
}bool judge(ll k,ll t)
{ll ans,i;ans=-sum;for(i=1;i<=m;i++) ans+=book[i]*(t/i);for(i=1;i<=m;i++) ans-=(book[i]-query(tree[i].pre,t%i+1));if(ans>=k) return 1;else return 0;
}int main()
{ll k,l,r,mid,ans;ll t,i,op,x,y;m=1e3;//scanf("%d",&t);_cin(t);while(t--){//scanf("%d%d",&n,&q);_cin(n),_cin(q);for(i=1;i<=n;i++) _cin(a[i]);for(i=1;i<=n;i++) _cin(b[i]);for(i=1;i<=m;i++) memset(tree[i].pre,0,sizeof(tree[i].pre));memset(book,0,sizeof(book));sum=0;for(i=1;i<=n;i++){sum+=b[i]/a[i];book[a[i]]++;update(tree[a[i]].pre,b[i]%a[i]+1,1);}while(q--){_cin(op);if(op==1){_cin(x),_cin(y);sum-=b[x]/a[x],sum+=b[x]/y;book[a[x]]--;book[y]++;update(tree[a[x]].pre,b[x]%a[x]+1,-1);update(tree[y].pre,b[x]%y+1,1);a[x]=y;}else if(op==2){_cin(x),_cin(y);sum-=b[x]/a[x],sum+=y/a[x];update(tree[a[x]].pre,b[x]%a[x]+1,-1);update(tree[a[x]].pre,y%a[x]+1,1);b[x]=y;}else{_cin(k);l=1,r=5e9,ans=0;//while(l<=r){mid=(l+r)/2;if(judge(k,mid)) r=mid-1,ans=mid;else l=mid+1;}printf("%lld\n",ans);}}}return 0;
}
这篇关于Master of Sequence HDU - 5441的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
