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

前端之家收集整理的这篇文章主要介绍了Codecraft-18 and Codeforces Round #458 (combined) D. Bash and a Tough Math Puzzle 线段树+二分+卡时间+优化前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
D. Bash and a Tough Math Puzzle
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bash likes playing with arrays. He has an arraya1, a2, ...anofnintegers. He likes to guess the greatest common divisor (gcd) of different segments of the array. Of course,sometimes the guess is not correct. However,Bash will be satisfied if his guess isalmost correct.

Suppose he guesses that the gcd of the elements in the range[l, r]ofaisx. He considers the guess to be almost correct if he can changeat mostone element in the segment such that the gcd of the segment isxafter making the change. Note that when he guesses,he doesn't actually change the array — he just wonders if the gcd of the segment can be madex. Apart from this,he also sometimes makes changes to the array itself.

Since he can't figure it out himself,Bash wants you to tell him which of his guesses are almost correct. Formally,you have to processqqueries of one of the following forms:

  • 1 l r x— Bash guesses that the gcd of the rangex. Report if this guess is almost correct.
  • 2 i y— Bash setsaitoy.

Note:The array is1-indexed.

Input

The first line contains an integern(1 ≤ n ≤ 5·105) — the size of the array.

The second line containsnintegersn(1 ≤ ai ≤ 109) — the elements of the array.

The third line contains an integerq(1 ≤ q ≤ 4·105) — the number of queries.

The nextqlines describe the queries and may have one of the following forms:

  • 1 l r x(1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 109).
  • 2 i y(1 ≤ i ≤ n, 1 ≤ y ≤ 109).

Guaranteed,that there is at least one query of first type.

Output

For each query of first type,output"YES"(without quotes) if Bash's guess is almost correct and"NO"(without quotes) otherwise.

Examples
input
3
2 6 3
4
1 1 2 2
1 1 3 3
2 1 9
1 1 3 2
output
YES
YES
NO
5 1 2 3 4 5 6 1 1 4 2 2 3 6 1 1 4 2 1 1 5 2 2 5 10 1 1 5 2
NO YES NO YES
Note

In the first sample,the array initially is{2, 6, 3}.

For query1,the first two numbers already have their gcd as2.

For query2,we can achieve a gcd of3by changing the first element of the array to3. Note that the changes made during queries of type1are temporary and do not get reflected in the array.

After query3,the array is now{9,sans-serif;white-space:nowrap;">4,no matter which element you change,you cannot get the gcd of the range to be2.


Source

Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2,combined)

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 <iostream>
#include <cstdio>

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,mid + 1,r,(Ind<<1) + 1); }
    //pot[Ind] = gcd(pot[Ind<<1],pot[(Ind<<1)+1]);

}

inline void _Modify(int a,int Ind,int d){
    if(a == l && r == b){pot[Ind] = d; return; }
    int mid = (l + r) >> 1;
    if(a <= mid){ _Modify(a,Ind<<1,d); }
    if(b > mid){ _Modify(a,(Ind<<1) + 1,d); }
    pot[Ind] = gcd(pot[Ind<<1],pot[(Ind<<1)+1]);
}

inline void Query(int a,int b) { _Query(a,1,sz,1);}
inline void Modify(int a,int d){ _Modify(a,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,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,aa[i]);
    }
    int l,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 << "YES\n";
                    printf("YES\n");
                    continue;
                }
                findans = aa[a+1];
                Query(a+1,b);
                ans1 = findans;
                if(gcd(ans1,x) == x) printf("YES\n");//cout << "YES\n";
                else printf("NO\n");//cout << "NO\n";
            }
            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("YES\n");//cout << "YES\n";
                else if(gcd(ans1,x) == x) printf("YES\n");//cout << "YES\n";
                else if(gcd(gcd(ans2,ans3),x) == x){
                    printf("YES\n");//cout << "YES\n";
                }
                else{
                    printf("NO\n");//cout << "NO\n";
                }
            }
        }
        else{
            //cin >> a >> x;
            scanf("%d%d",&x);
            aa[a] = x;
            Modify(a,x);
        }
    }

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

Thank you!

------fromProLights

原文链接:https://www.f2er.com/bash/388840.html

猜你在找的Bash相关文章