链接：P4774

---

前言：

交了18遍最后发现是多组数据没清空/ll

---

题意：

其实就是个扩中。

---

分析过程：

首先发现根据题目描述的选择剑的方式，每条龙对应的剑都是固定的，有查询前驱，后继（在该数不存在前驱时，最小值即为后继），和插入，删除操作，所以想到平衡树维护每条龙的剑的攻击力，记为b[i]。建议使用非旋treap，非常之好写。

---

根据题目描述，a[i]为每条龙生命值，p[i]为每条龙回复量。发现能够击杀这条龙的条件可以列成一个方程：

\(xb[i]-yp[i]=a[i]\)

\(x\) 为攻击次数，\(y\) 为回复次数，转化为同余方程的形式为：

\(xb[i]\equiv a[i]\pmod {p[i]}\)

所以题目就被我们转化成了一个一元 \(n\) 次的不定方程组：

\(\begin{cases}xb[1]\equiv a[1]\pmod {p[1]} \\ xb[2]\equiv a[2]\pmod {p[2]}\\ \vdots\\ xb[n]\equiv a[n]\pmod {p[n]}\end{cases}\)

求 \(x\) 的最小非负整数解。

这样的形式虽然不满足CRT和exCRT的形式，但我们可以从exCRT的思想得到启发。我们记录下前 \(m-1\) 个方程的通解 \(x=x_0+t*M\)，也就是说我们已知 \(x_0\) 和 \(M\)。

对于第 \(m\) 个方程 \(xb[m]-yp[m]=a[m]\) ，将上述 \(x\) 带入，有

\((x_0+t*M)b[i]-yp[i]=a[i]\)

即 \(x_0b[i]+t*M*b[i]-yp[i]=a[i]\)

由于\(x_0,b[i],M,p[i],a[i]\) 全部都已知，所以化为

\(t*Mb[i]-y*p[i]=a[i]-x_0b[i]\)

设 \(ta=Mb[i],tb=p[i],tc=a[i]-x_0b[i]\)

就有 \(t*ta-y*tb=tc\)

可以用扩展欧几里得求解 \(t=t_0+q*\frac{tb}{\gcd(ta,tb)}\)。

如果 \(t\) 无解那显然此题就无解。

为了这里看起来简洁一些，设 \(r=\frac{tb}{\gcd(ta,tb)}\)。

则 \(t=t_0+q*r\)

发现我们不停带入化简求出了前 \(m-1\) 个方程的解 \(x=x_0+t*M\) 中 \(t\)的范围，所以再将 \(t\) 带入该式，有：

\(x=x_0+(t_0+q*r)*M\)

即 \(x=x_0+t_0*M+q*r*M\)

还看不出来吗？那就再括起来：

\(x=(x_0+t_0*M)+q*(r*M)\)

这个写法是不是和 \(x=x_0+t*M\) 有点像？没错，这就是合并了两个方程之后的解。

发现我们完全通过柿子和推导得出了合并方程的方法，只需要做一次扩展欧几里得。那么对于第一个方程怎么办呢，我们当然可以特殊处理第一个方程，求出它的解。还有另一种巧妙的办法，就是将 \(x\) 一开始的取值范围设为 \(\mathbb{Z}\)，只需将 \(M\) 设为 \(1\)，即 \(x=x_0+t*1\) ,这里的 \(x_0\) 对结果应该没有影响，我测试了几个不同的初值都能过，这样就不用单独处理第一个方程了。

---

坑1：

注意我们转化方程 \(xb[i]-yp[i]=a[i]\) 的过程是有缺陷的，根据题意，这里的 攻击次数 \(x\) 和回复次数 \(y\) 显然都应该是非负数而且有一定限制，翻译成人话就是说你砍出来的伤害至少要大于这条龙的血量。再翻译成数学语言就是：

\(\forall i\ (i\in \left [ 1,n \right ]),xb[i]\geq a[i]\)

转化不等式：\(x\geq \frac{a[i]}{b[i]}\)

所以用double类型记录最大的 \(\frac{a[i]}{b[i]}\)，把最后的解处理一下即可。

---

坑2：

因为此题数据范围较大，long long会溢出，所以需要在各种地方取模并使用龟速乘防止溢出。由于我们记录的一直是通解，所以\(x_0\) 的值并不要求最小，只是为了避免溢出所以让 \(x_0\) 每次对 \(M\) 取模。

---

坑3：

就是我亲身踩了17次的注意平衡树每次会有剩下的剑还在树中，注意清空。

---

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;

int read(){
    int p=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return p*f;
}

//treap-------------------
#define v(x) kin[x].v
#define lc(x) kin[x].lc
#define rc(x) kin[x].rc
#define siz(x) kin[x].siz
#define rnd(x) kin[x].rnd
struct k{
    int v,lc,rc,siz,rnd;
}kin[2*maxn];
int rt,cnt;
int newnode(int x){
    rnd(++cnt)=rand();
    siz(cnt)=1;
    v(cnt)=x;
    lc(cnt)=rc(cnt)=0;
    return cnt;
}
void pushup(int x){
    siz(x)=siz(lc(x))+siz(rc(x))+1;
}
int merge(int x,int y){
    if(!x||!y)return x|y;
    if(rnd(x)<rnd(y)){
        rc(x)=merge(rc(x),y);
        pushup(x);
        return x;
    }
    else{
        lc(y)=merge(x,lc(y));
        pushup(y);
        return y;
    }
}
void split(int p,int k,int &x,int &y){
    if(!p){x=y=0;return ;}
    if(v(p)<=k){
        x=p;
        split(rc(p),k,rc(p),y);
        pushup(p);
    }
    else{
        y=p;
        split(lc(p),k,x,lc(y));
        pushup(p);
    }
}
void insert(int v){
    int x,y,z;
    x=y=z=0;
    split(rt,v,x,z);
    y=newnode(v);
    rt=merge(merge(x,y),z);
}
void del(int v){
    int x,y,z;
    x=y=z=0;
    split(rt,v,x,z);
    split(x,v-1,x,y);
    y=merge(lc(y),rc(y));
    rt=merge(merge(x,y),z);
}
int getb(int a){
    int x,y;
    x=y=0;
    split(rt,a,x,y);
    if(x){
        int now=x;
        while(rc(now))now=rc(now);
        now=v(now);
        rt=merge(x,y);
        del(now);
        return now;
    }
    else{
        int now=y;
        while(lc(now))now=lc(now);
        now=v(now);
        rt=merge(x,y);
        del(now);
        return now;
    }
}
//treap----------------------------

int exgcd(int a,int b,int &x,int &y){
    if(a<b)return exgcd(b,a,y,x);
    if(a%b==0){
        x=0;y=1;
        return b;
    }
    else{
        int tx,ty;
        int d=exgcd(b,a%b,tx,ty);
        x=ty;
        y=tx-a/b*ty;
        return d;
    }
}
int gsc(int ta,int tb,int mod){
    if(!ta||!tb)return 0;
    int ans=0,f=1;
    if(ta<0)ta=-ta,f*=-1;
    if(tb<0)tb=-tb,f*=-1;
    ta%=mod;
    tb%=mod;
    while(tb){
        if(tb&1)ans=(ans+ta)%mod;
        ta=(ta+ta)%mod;
        tb>>=1;
    }
    return ans*f;
}
int T;
int n,m;
int a[maxn],p[maxn],q[maxn],b[maxn];
int x0,M;
signed main(){
    T=read();
    while(T--){
        cnt=0,rt=0;
        n=read(),m=read();
        for(int i=1;i<=n;i++)
            a[i]=read();
        for(int i=1;i<=n;i++)
            p[i]=read();
        for(int i=1;i<=n;i++)
            q[i]=read();
        for(int i=1;i<=m;i++){
            int temp=read();
            insert(temp);
        }
        for(int i=1;i<=n;i++){
            b[i]=getb(a[i]);
            insert(q[i]);
        }
        x0=0,M=1;
        int ta,tb,tc,t,y,d,flag=1;
        double mx=0;
        for(int i=1;i<=n;i++){
            ta=M*b[i],tb=p[i],tc=a[i]-x0*b[i];
            d=exgcd(ta,tb,t,y);
            if(tc%d!=0){
                printf("-1\n");
                flag=0;
                break;
            }
            ta/=d,tb/=d,tc/=d;
            t=(t%tb+tb)%tb;
            x0+=gsc(gsc(tc,t,M*tb),M,M*tb);
            M*=tb;
            x0=(x0%M+M)%M;
            if(double(a[i])/b[i]>mx)
                mx=double(a[i])/b[i];
        }
        while(x0<mx)x0+=M;
        if(flag)
            printf("%lld\n",x0);
    }
    return 0;
}

---

题外话：

做完感觉自己就是屠龙勇士，另外感觉这道题很好的揭示了平衡树这一工具人的作用