E - Coprime

给你一个整数序列，判断是否两两互质，整个序列互质（整个序列的公因数为\(1\)），或者不满足先前两种情况。

首先先判断是否整个序列互质，这个单独判断方便一点，就求出整个序列的最大公因数。

那么再判断是否两两互质，我们对每个数分解质因数，记录它包含了哪些质因子（不论那个质因子被乘了多少次）。假如有多于一个的数包含同一个质因子，那么这个序列就不是两两互质的。

#include
using namespace std;

inline int gcd(int a,int b){
    while(b){
        a=a%b;
        swap(a,b);
    }
    return a;
}

int n,a[1000005],u[1000005];

int main(){

    scanf("%d",&n);
    int g=0;
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        g=gcd(g,a[i]);
        for(int j=2;j*j<=a[i];j++){
            if(a[i]%j==0){
                u[j]++;
                while(a[i]%j==0)a[i]/=j;
            }
        }
        u[a[i]]++;
    }
    if(g>1){
        cout<<"not coprime\n";
        return 0;
    }
    for(int i=2;i<=(int)1e6;i++){
        if(u[i]>1){
            cout<<"setwise coprime\n";
            return 0;
        }
    }
    cout<<"pairwise coprime\n";


    return 0;
}

F - I hate Shortest Path Problem

给你一个高\(H+1\)，宽\(W\)的矩形，第\(i\)行第\(A_i\)个位置到第\(B_i\)个位置下方有挡板，特别地，底部的一行下方没有挡板。

你可以从顶部一行的任意一个位置开始行动，每一步可以向下或向右走一格，要求不能走出矩形或者穿过挡板。问你走到第\(2, 3, \dots, H\)行各最少需要多少步，无法达到输出-1。

我们首先需要观察到，除了起始位置的选择不一定尽量靠前外，否则能向下走就直接向下走，不然向右走一格，再尝试向下走，这么持续下去一定是最优的一种考虑。

我们可以模拟走到某一行某一个位置最少需要多少步。

为了维护方便，我们反向考虑如何走到这个格子。这个格子一定是上一个格子向右移动了某些步数（可能移动零步），然后向下移动一格走到的。向下移动后，我们不需要考虑再向右移动的情况了。因为在转移到下一行时，之前描述的“向右移动了某些步数，然后向下移动一格”包含了这个情况。同时这样也可以保证对此行答案的贡献最优。

我们可以考虑使用数据结构来优化。那么此时我们需要分类一下：

1. 对于上方没有挡板的格子，我们可以直接从上向下转移，假如这个走法不是最优的，可以证明它对答案没有影响。
2. 对于上方有挡板的格子，直接把它的答案设成正无穷大，因为无法走到。假如这个走法不是最优的，也可以证明它对答案没有影响。
3. 对于左上方有挡板的格子，可以从上方的格子所有左边的格子转移来。

感性理解，每一个格子继续行动时，它的贡献一定会通过以上三种转移方式继续向下传下去，所以可以保证是最优的。

然后我们就可以使用两棵线段树维护了，假如我们定义当前行的位置\(i\)的答案为\(ans_i\)，一棵维护真实的最小值\(ans_i\)，一棵维护\(ans_i+W-i\)，用于做第三种更新。需要先做第三种更新，因为我们此时的转移都做在同一个线段树内，顺序会相互影响。

#include
using namespace std;

struct SegTree{

    int sz;
    vector dat,laz;

    SegTree(){
        sz=1<<18;
        dat.resize(sz<<1);
        laz.resize(sz<<1);
    };

    void upd(int id,int l,int r,int ql,int qr,long long val){
        if(qr>1,ql,qr,val);
        upd(id<<1|1,(l+r>>1)+1,r,ql,qr,val);
        dat[id]=min(dat[id<<1],dat[id<<1|1]);
    }

    long long qry(int id,int l,int r,int ql,int qr){
        if(qr>1,ql,qr),qry(id<<1|1,(l+r>>1)+1,r,ql,qr));
    }

    void upd(int l,int r,long long d){
        upd(1,1,sz,l,r,d);
    }

    long long qry(int l,int r){
        return qry(1,1,sz,l,r);
    }
};

int n,m;
int a[200005],b[200005];
SegTree upd,qry;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=m;i++)upd.upd(i,i,m-i);
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        qry.upd(b[i]+1,b[i]+1,min(upd.qry(1,b[i])-(m-b[i]-1)-qry.qry(b[i]+1,b[i]+1),0ll));
        upd.upd(b[i]+1,b[i]+1,min(upd.qry(1,b[i])-upd.qry(b[i]+1,b[i]+1),0ll));
        qry.upd(a[i],b[i],1e9);
        upd.upd(a[i],b[i],1e9);
        qry.upd(1,m,1);
        upd.upd(1,m,1);
        if(qry.qry(1,m)>=1e9)cout<<"-1\n";
        else cout<