Codecraft-18 and Codeforces Round #458 (combined) D. Bash and a Tough Math Puzzle 线段树+二分+卡时间+优化

My Solution

题意：给出一个长度为n的序列，q个操作，每次询问区间[a,b]内最多改一个数，能不能变成gcd（a~b）== x；或者把第i个数改成y。

线段树单点修改区间查询+二分+卡时间+优化

用线段树单点修改区间查询来维护一段区间的gcd，

然后对于修改操作可以直接修改，

而对于询问操作则要二分出一个最大的区间[a,mid]满足gcd（gcd（a~mid），x） == x，

此时如果mid == b 或者 mid == b-1或者 gcd（gcd（mid+2~b），x） == x 则 Yes，否则No。

当mid不存在时，如果a == b，或者gcd（gcd（a+1~b），x）== x 则 Yes，否则No。

并且这题时间卡的比较紧，所以在二分的check需要优化，每次记录上次a~mid的gcd，这次直接从上次的mid到这次的mid进行查询，这样查询的复杂度远小于logn，此外1、用ios::sync_with_stdio(false); cin.tie(0);的cin cout 依然超时，换成scanf和printf就可以了；2、这里是定义一个全局变量findans，每次把合理的区间与findans进行合并，好像比带返回值的线段写法稍微快一点^_^。

时间复杂度 略大于O(nlogn) 远小于O(nlognlogn)

空间复杂度 O(n)

#include 
#include 

using namespace std;
typedef long long LL;
const int MAXN = 5e5 + 8;

inline int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}


int pot[4*MAXN], lazy[4*MAXN];
int findans;
int sz;
inline void _Query(int a, int b, int l, int r, int Ind){
    if(a <= l && r <= b){ findans = gcd(findans, pot[Ind]); return;} int mid = (l + r) >> 1;
    if(a <= mid) { _Query(a, b, l, mid, Ind<<1); } if(b > mid) { _Query(a, b, mid + 1, r, (Ind<<1) + 1); }
    //pot[Ind] = gcd(pot[Ind<<1] , pot[(Ind<<1)+1]); } inline void _Modify(int a, int b, int l, int r, int Ind, int d){ if(a == l && r == b){pot[Ind] = d; return; } int mid = (l + r) >> 1;
    if(a <= mid){ _Modify(a, b, l, mid, Ind<<1, d); } if(b > mid){ _Modify(a, b, mid + 1, r,(Ind<<1) + 1, d); }
    pot[Ind] = gcd(pot[Ind<<1] , pot[(Ind<<1)+1]);
}

inline void Query(int a, int b) { _Query(a, b, 1, sz, 1);}
inline void Modify(int a,int b,int d){ _Modify(a, b, 1, sz, 1, d);}

int aa[MAXN], x, ok;
inline bool check(int mid, int a){
    findans = aa[a];
    if(ok != -1 && ok + 1 <= a + mid - 1){ aa[ok + 1]; Query(ok + 1, a + mid - 1); } else Query(a, a + mid - 1); if(gcd(findans, x) == x){ ok = a + mid - 1; return true; } else return false; } int main() { #ifdef LOCAL freopen("d.txt", "r", stdin); //freopen("d.out", "w", stdout); int T = 2; while(T--){ #endif // LOCAL //ios::sync_with_stdio(false); cin.tie(0); int n, q, t, a, b, i, ans1, ans2, ans3; //cin >> n;
    scanf("%d", &n);
    sz = n;
    for(i = 1; i <= n; i++){ //cin >> aa[i];
        scanf("%d", &aa[i]);
        Modify(i, i, aa[i]);
    }
    int l, r, mid, f;
    //cin >> q;
    scanf("%d", &q);
    while(q--){
        //cin >> t;
        scanf("%d", &t);

        if(t == 1){
            //cin >> a >> b >> x;
            scanf("%d%d%d", &a, &b, &x);
            l = 0, r = b - a + 1 + 1; f = -1; ok = -1;
            while(l + 1 < r){ if(gcd(aa[a], x) != x) break; mid = (l + r) >> 1;
                if(check(mid, a)){
                    l = mid;
                    f = mid;
                }
                else{
                    r = mid;
                }
            }
            //cout <<"?" << f << endl;
            if(f == -1){
                //cout << a << " " << b << " " << x << endl;
                if(a == b){
                    //cout << "YESn";
                    printf("YESn");
                    continue;
                }
                findans = aa[a+1];
                Query(a+1, b);
                ans1 = findans;
                if(gcd(ans1, x) == x) printf("YESn");//cout << "YESn";
                else printf("NOn");//cout << "NOn";
            }
            else{
                findans = aa[a];
                Query(a, b);
                ans1 = findans;

                findans = aa[a];
                Query(a, a + f-1);
                ans2 = findans;
                //cout << "ans2 " << ans2 << endl;
                findans = aa[a + f + 1];
                if(f != b - a + 1){
                        if(f != b - a) Query(a + f + 1, b), ans3 = findans;
                        else ans3 = x;
                }
                else ans3 = 1;

                //cout << "ans3 " << ans3 << endl;
                if(ans1 == x) printf("YESn");//cout << "YESn";
                else if(gcd(ans1, x) == x) printf("YESn");//cout << "YESn";
                else if(gcd(gcd(ans2, ans3), x) == x){
                    printf("YESn");//cout << "YESn";
                }
                else{
                    printf("NOn");//cout << "NOn"; } } } else{ //cin >> a >> x;
            scanf("%d%d", &a, &x);
            aa[a] = x;
            Modify(a, a, x);
        }
    }

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

Thank you!

                                                                                                                                             ------from ProLightsfx