70pts平衡树
```cpp
#include<bits/stdc++.h>
#define int __int128
using namespace std;
mt19937 rnd(time(0));
void read(int &x){
int flg=1;
x=0;char c=getchar();
while(c<'0' || c>'9'){
if(c=='-')flg=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=x*10+c-'0';
c=getchar();
}
x*=flg;
}
void write(int x){
if(x==0){putchar(48);return;}
int len=0,dg[105];
while(x>0){dg[++len]=x%10;x/=10;}
for(int i=len;i>=1;i--)putchar(dg[i]+48);
putchar('\n');
}
int t,n,m,tot,a[100005],p[100005],giv[100005],atk[100005],b[100005];
struct fhq_Treap{
struct node{
int siz,rnk,val,lc,rc;
}tree[400005];
void update(int cur){
tree[cur].siz=tree[tree[cur].lc].siz+tree[tree[cur].rc].siz+1;
return;
}
void split(int cur,int &a,int &b,int val){
if(cur==0){
a=b=0;
return;
}
if(tree[cur].val<=val){
a=cur;
split(tree[cur].rc,tree[cur].rc,b,val);
}
else{
b=cur;
split(tree[cur].lc,a,tree[cur].lc,val);
}
update(cur);
return;
}
void merge(int &cur,int a,int b){
if(!a||!b){
cur=a+b;
return;
}
if(tree[a].rnk<tree[b].rnk){
cur=a;
merge(tree[a].rc,tree[a].rc,b);
}
else{
cur=b;
merge(tree[b].lc,a,tree[b].lc);
}
update(cur);
return;
}
int find_num(int cur,int x){
while(tree[tree[cur].lc].siz+1!=x){
if(tree[tree[cur].lc].siz>=x){
cur=tree[cur].lc;
}
else{
x-=tree[tree[cur].lc].siz+1;
cur=tree[cur].rc;
}
}
return tree[cur].val;
}
int add_node(int val){
tree[++tot]={1,rnd(),val,0,0};
return tot;
}
void insert(int &cur,int val){
int a=0,b=0,c=add_node(val);
split(cur,a,b,val);
merge(a,a,c);
merge(cur,a,b);
return;
}
void del(int &cur,int val){
int a=0,b=0,z=0;
split(cur,a,b,val);
split(a,a,z,val-1);
merge(z,tree[z].lc,tree[z].rc);
merge(a,a,z);
merge(cur,a,b);
}
int find_rnk(int &cur,int val){
int a=0,b=0;
split(cur,a,b,val-1);
int tmp=tree[a].siz+1;
merge(cur,a,b);
return tmp;
}
int pre(int &cur,int val){
int a=0,b=0;
split(cur,a,b,val-1);
int tmp=find_num(a,tree[a].siz);
merge(cur,a,b);
return tmp;
}
int suf(int &cur,int val){
int a=0,b=0;
split(cur,a,b,val);
int tmp=find_num(b,1);
merge(cur,a,b);
return tmp;
}
}fhq;
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,x,y),_x=x,_y=y;
x=_y;
y=_x-(a/b)*_y;
return d;
}
int maxn;
int excrt(){
int ans=0,lcm=1,x,y,gcd,A,B,C;
for(int i=1;i<=n;++i) {
A=(__int128)b[i]*lcm%p[i];
B=p[i];
C=(a[i]-b[i]*ans%p[i]+p[i])%p[i];
gcd=exgcd(A,B,x,y);
x=(x%B+B)%B;
if(C%gcd)return (__int128)-1;
ans+=(__int128)(C/gcd)*x%(B/gcd)*lcm%(lcm*=B/gcd);
ans%=lcm;
}
if(ans<maxn)ans+=((maxn-ans-1)/lcm+1)*lcm;
return ans;
}
signed main(){
int rt=0;
read(t);
while(t--){
tot=rt=maxn=0;
read(n);read(m);
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<=n;++i)read(p[i]);
for(int i=1;i<=n;++i)read(giv[i]);
for(int i=1;i<=m;++i)read(atk[i]),fhq.insert(rt,atk[i]);
for(int i=1;i<=n;++i){
if(fhq.find_num(rt,1)<a[i])b[i]=fhq.pre(rt,a[i]);
else b[i]=fhq.find_num(rt,1);
fhq.del(rt,b[i]);
fhq.insert(rt,giv[i]);
maxn=max(maxn,(a[i]-1)/b[i]+1);
}
// write();
int ans=excrt();
if(ans==-1)puts("-1");
else write(ans);
}
return 0;
}
```
multiset AC
```cpp
#include<bits/stdc++.h>
#define int __int128
using namespace std;
mt19937 rnd(time(0));
void read(int &x){
int flg=1;
x=0;char c=getchar();
while(c<'0' || c>'9'){
if(c=='-')flg=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=x*10+c-'0';
c=getchar();
}
x*=flg;
}
void write(int x){
if(x==0){putchar(48);return;}
int len=0,dg[105];
while(x>0){dg[++len]=x%10;x/=10;}
for(int i=len;i>=1;i--)putchar(dg[i]+48);
putchar('\n');
}
int t,n,m,tot,a[100005],p[100005],giv[100005],atk[100005],b[100005];
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,x,y),_x=x,_y=y;
x=_y;
y=_x-(a/b)*_y;
return d;
}
int maxn;
int excrt(){
int ans=0,lcm=1,x,y,gcd,A,B,C;
for(int i=1;i<=n;++i) {
A=(__int128)b[i]*lcm%p[i];
B=p[i];
C=((a[i]-b[i]*ans%p[i])%p[i]+p[i])%p[i];
gcd=exgcd(A,B,x,y);
x=(x%B+B)%B;
if(C%gcd)return (__int128)-1;
ans+=(__int128)(C/gcd)*x%(B/gcd)*lcm%(lcm*=B/gcd);
ans%=lcm;
}
if(ans<maxn)ans+=((maxn-ans-1)/lcm+1)*lcm;
return ans;
}
multiset<int>s;
signed main(){
// freopen("P4774_5.in","r",stdin);
// freopen("P4774_5.ans","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
int rt=0;
read(t);
while(t--){
tot=rt=maxn=0;
read(n);read(m);
s.clear();
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<=n;++i)read(p[i]);
for(int i=1;i<=n;++i)read(giv[i]);
for(int i=1;i<=m;++i)read(atk[i]),s.insert(atk[i]);
for(int i=1;i<=n;++i){
auto pos=s.upper_bound(a[i]);
if(pos!=s.begin())pos--;
b[i]=*pos;
s.erase(pos);
s.insert(giv[i]);
// if(fhq.find_num(rt,1)<a[i])b[i]=fhq.pre(rt,a[i]);
// else b[i]=fhq.find_num(rt,1);
// fhq.del(rt,b[i]);
// fhq.insert(rt,giv[i]);
maxn=max(maxn,(a[i]-1)/b[i]+1);
}
// write();
int ans=excrt();
if(ans==-1)puts("-1");
else write(ans);
}
return 0;
}
```
by Forever1507 @ 2023-05-04 19:54:21
@[Forever1507](/user/359614) 直线->实现
by Forever1507 @ 2023-05-04 19:54:58