E

线段树

每次从$b_i$开始，给长度为$a_i$的子数组都加1，这是个循环数组，超过n了会回到开头。

每次加的元素$a_i$是从数组里取的，也就是需要动态修改，查询。

$a_i$很大的话，其实加操作就是一个后缀，一个前缀，加中间多段完整的，每段完整的都一样，三次区间加即可。线段树维护。

struct Tree{
    struct Node{
        int l,r;
        ll sum,add;
    }tr[N<<2];
     
    void pushup(int u){
        tr[u].sum=tr[ls].sum+tr[rs].sum;
    }
     
    void pushdown(int u){
        if(tr[u].add){
            tr[ls].sum+=tr[u].add;
            tr[rs].sum+=tr[u].add;
            tr[ls].add+=tr[u].add;
            tr[rs].add+=tr[u].add;
            tr[u].add=0;
        }
    }
     
    void build(int u,int l,int r){
        tr[u]={l,r,0,0};
        if(l==r){
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);    build(rs,mid+1,r);
        pushup(u);
    }
     
    void modify(int u,int l,int r,int val){
        if(tr[u].l>=l&&tr[u].r<=r){   
            tr[u].sum+=val;
            tr[u].add+=val;
            return ;
        }
        else{
            int mid=(tr[u].l+tr[u].r)>>1;
            pushdown(u);
            if(mid>=l)   modify(ls,l,r,val);
            if(r>mid) modify(rs,l,r,val);
            pushup(u);  
        }
    }
     
    ll query(int u,int l,int r){
        if(r<tr[u].l||tr[u].r<l)  return 0;
        if(l<=tr[u].l&&tr[u].r<=r)    return  tr[u].sum;
        pushdown(u);
        return query(ls,l,r)+query(rs,l, r);
    }
}t;
void solve(void){ 
	int n,m;
	cin>>n>>m;
	t.build(1,1,n);
	rep(i,1,n){
		int x;
		cin>>x;
		t.modify(1,i,i,x);
	}
	rep(i,1,m){
		int x;
		cin>>x;
		x++;
		int b=t.query(1,x,x);
		t.modify(1,x,x,-b);
		t.modify(1,1,n,b/n);
		b-=b/n*n;
		if(b){
			int l=x+1,r=x+b;
			if(l>n)l-=n;
			if(r>n)r-=n;
			if(r>=l){
				t.modify(1,l,r,1);
			} 
			else{
				t.modify(1,l,n,1);
				t.modify(1,1,r,1);
			}
		}
	}
	rep(i,1,n){
		cout<<t.query(1,i,i)<<' ';
	} 
}

F

计算几何 exgcd

给整点$(x,y)$，问能否找到一个整点$(a,b)$，$(0,0)(x,y)(a,b)$组成的三角形面积为1.

首先考虑这个条件能转化成什么式子

也就是要解一个方程$|ay-bx|=2$。显然绝对值不重要，得到一组解之后取反就是绝对值相反的解。

也就是找到一组$ay-bx=2$的可行解。可以$exgcd$找到$ay-bx=gcd(y,-x)$的一组可行解，设为$c$的话，带入可得$ay-by=2$的解就是$2c/gcd(y,-x)$

当然这需要能整除，所以根据$gcd$分讨。如果$gcd>2$，显然怎么线性组合也只能得到$gcd$的倍数，不可能凑出来$2$，无解。

一般的$exgcd$实现，就是返回$gcd$，而解通过传引用的方式返回

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll tx, ty, g = exgcd(b, a % b, tx, ty);
    x = ty, y = tx - a / b * ty;
    return g;
}
void solve(void){ 
	ll a, b;
    cin >> a >> b;
	if(gcd(a,b)>2){
		cout<<-1;
		return;
	} 
		ll x,y;
		exgcd(a,b,y,x);
		if(gcd(a,b)==1){
			cout<<-x*2<<' '<<y*2;
		}
		else{
			cout<<-x<<' '<<y;
		}
	
}