C.web of lies

先放题目链接：https://codeforces.com/contest/1549/problem/C

大体意思就是说这是一张有着n个节点的图，有m条边，如果一个节点所有与之连接的节点编号都比自己大，那么此节点就会被消灭掉，现在先给出初始的图，经过多次的增边或者是删边操作，查询当前图有多少存活点（随时都会有查询）。

这个嘛，如果经过观察我们会发现连成一团的连通图里，最小的会被消灭掉，然后次小的也会被消灭掉，就这样一个一个被消灭，最后整张图里面只有最大的可以存活下来，诶，这就好办了，我们可以断定如果一个节点只要连接到一个比自己大的节点就肯定会被消灭掉。那么这样事情就好办了，上代码吧

#include <bits/stdc++.h>
using namespace std;
int cnt[200005],ans;
int main(){
    int n,m;
    cin>>n>>m;
    ans=n;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        cnt[min(a,b)]++;
        if(cnt[min(a,b)]==1) ans--;
    }
    int q;
    cin>>q;
    while(q--){
        int opt;
        cin>>opt;
        if(opt==1){
            int a,b;
            cin>>a>>b;
            cnt[min(a,b)]++;
            if(cnt[min(a,b)]==1) ans--;
        }
        if(opt==2){
            int a,b;
            cin>>a>>b;
            cnt[min(a,b)]--;
            if(cnt[min(a,b)]==0) ans++;
        }
        if(opt==3) cout<<ans<<endl;
    }
    return 0;
}

D.Integers Have Friends

题目链接：https://codeforces.com/contest/1549/problem/D

题目大意就是给你一串数列，让你去找出这样一串子序列（连续），这串子序列每个数字对一个大于1的数字取模运算，最后结果都相等。假如说两个数字a和b对p同余，那么(a-b)%p=0，那我们扩展到三个数字a,b,c,如果a,b,c对p都同余的话，则必然存在(a-b)%p=0,(b-c)%p=0。gcd(a-b,b-c)=p。那么我们得出解法：先对数列差分，求区间gcd，区间gcd可用st表求解，如果区间gcd大于1则此子序列符合要求，固定区间左端点的情况下，区间越长，gcd会越小，由此单调性，我们可以选择二分区间长度。解题完毕

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll a[200005];
ll lgcd[200005][30];
ll gcd(ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
bool check(int len){
    int k=log2(len);
    for(int i=1;i+len-1<n;i++){
        ll m=gcd(lgcd[i][k],lgcd[i+len-1-(1<<k)+1][k]);
        if(m>=2) return 1;
    }
    return 0;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        
        cin>>n;
        
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) {a[i]=a[i+1]-a[i];a[i]=abs(a[i]);}
        for(int i=1;i<n;i++) lgcd[i][0]=a[i];
        if(n==1){cout<<1<<endl;continue;}
        int mx=log2(n);
        for(int i=1;i<=mx;i++){
            for(int j=1;j+(1<<i)-1<n;j++) lgcd[j][i]=gcd(lgcd[j][i-1],lgcd[j+(1<<(i-1))][i-1]);
        }
        int l=1,r=n-1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)) l=mid+1;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}