absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] ARC073E
[破碎的状态] cf 917C

[破碎的状态] cf 914D

absi2011 posted @ Jan 26, 2018 10:29:20 PM in 刷题记录 with tags 线段树 小高考 CF 分块 Div.2 Div.1 瞎搞 , 674 阅读

题意:

给你n个数,两个操作

1,询问区间内的gcd是否可以在修改最多一个数的情况下为x

2,修改一个数

n<=5e5 q<=4e5

=============

做法1:

线段树

区间维护,查询的时候只要看区间内是否gcd %x==0

如果不为0,则继续查询里面(如果已经有一个%x!=0的那就直接返回答案错误)

我写的比较差,好像复杂度O(n log^3 n)

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int gcd(int x,int y)
{
    if (y==0) return x;
    return gcd(y,x%y);
}
int val[1<<20];
int a[500005];
void build_tree(int num,int l,int r)
{
    if (l==r-1)
    {
        val[num]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build_tree(num*2+1,l,mid);
    build_tree(num*2+2,mid,r);
    val[num]=gcd(val[num*2+1],val[num*2+2]);
}
void change(int num,int l,int r,int l0,int k)
{
    if (l==r-1)
    {
        val[num]=k;
        return;
    }
    int mid=(l+r)/2;
    if (l0<mid)
    {
        change(num*2+1,l,mid,l0,k);
    }
    else
    {
        change(num*2+2,mid,r,l0,k);
    }
    val[num]=gcd(val[num*2+1],val[num*2+2]);
}
int query_ans(int num,int l,int r,int l0,int r0)
{
    if ((l0<=l)&&(r<=r0))
    {
        return val[num];
    }
    int mid=(l+r)/2;
    int ans=0;
    if (l0<mid) ans=gcd(query_ans(num*2+1,l,mid,l0,r0),ans);
    if (mid<r0) ans=gcd(query_ans(num*2+2,mid,r,l0,r0),ans);
    return ans;
}
int query(int num,int l,int r,int l0,int r0,int x)
{
    if (query_ans(num,l,r,l0,r0)%x==0)
    {
        return 0;
    }
    if (l==r-1)
    {
        return 1;
    }
    int mid=(l+r)/2;
    int t=0;
    if (l0<mid)
    {
        if (query_ans(num*2+1,l,mid,l0,r0)%x!=0)
        {
            t+=query(num*2+1,l,mid,l0,r0,x);
            if (t>=2) return t;
        }
    }
    if (mid<r0)
    {
        if (query_ans(num*2+2,mid,r,l0,r0)%x!=0)
        {
            if (t==1) return 2;
            t+=query(num*2+2,mid,r,l0,r0,x);
            if (t>=2) return t;
        }
    }
    return t;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    int q;
    scanf("%d",&q);
    build_tree(0,0,n);
    for (i=0;i<q;i++)
    {
        int oper;
        int x;
        scanf("%d",&oper);
        if (oper==1)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            l--;
            scanf("%d",&x);
            if (query(0,0,n,l,r,x)>1)
            {
                puts("NO");
            }
            else
            {
                puts("YES");
            }
        }
        else
        {
            int t;
            scanf("%d",&t);
            t--;
            scanf("%d",&x);
            change(0,0,n,t,x);
        }
    }
    return 0;
}

做法2:

三级分块?

分成50个大块,每个大块里面100个小块,每个小块里面100个数字

暴力修改,分块一样的查询

复杂度O(n sqrt_3(n))

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int block=100;
inline int gcd(int x,int y)
{
    if (y==0) return x;
    return gcd(y,x%y);
}
int a[500005];
int gcds[55];
int gcd_mid[5005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    int j,k;
    for (i=0;i<50;i++)
    {
        gcds[i]=0;
        for (j=0;j<block;j++)
        {
            gcd_mid[i*100+j]=0;
            for (k=0;k<block;k++)
            {
                gcd_mid[i*100+j]=gcd(a[i*10000+j*100+k],gcd_mid[i*100+j]);
            }
            gcds[i]=gcd(gcd_mid[i*100+j],gcds[i]);
        }
    }
    int q;
    scanf("%d",&q);
    for (i=0;i<q;i++)
    {
        int oper;
        scanf("%d",&oper);
        if (oper==1)
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            l--;
            int sum=0;
            for (;;)
            {
                if (l>=r) break;
                if (l%10000==0)
                {
                    if (l+10000<=r)
                    {
                        if (gcds[l/10000]%x==0)
                        {
                            l+=10000;
                            continue;
                        }
                        else
                        {
                            if (sum==1)
                            {
                                sum++;
                                break;
                            }
                        }
                    }
                }
                if (l%100==0)
                {
                    if (l+100<=r)
                    {
                        if (gcd_mid[l/100]%x==0)
                        {
                            l+=100;
                            continue;
                        }
                        else
                        {
                            if (sum==1)
                            {
                                sum++;
                                break;
                            }
                        }
                    }
                }
                if (a[l]%x!=0)
                {
                    sum++;
                    if (sum==2) break;
                }
                l++;
            }
            if (sum>=2)
            {
                puts("NO");
            }
            else
            {
                puts("YES");
            }
        }
        else
        {
            int pos,x;
            scanf("%d%d",&pos,&x);
            pos--;
            a[pos]=x;
            int t=pos/100*100;
            int j;
            gcd_mid[t/100]=x;
            for (j=t;j<t+100;j++)
            {
                gcd_mid[t/100]=gcd(a[j],gcd_mid[t/100]);
            }
            t/=100;
            t=t/100*100;
            gcds[t/100]=0;
            for (j=t;j<t+100;j++)
            {
                gcds[t/100]=gcd(gcd_mid[j],gcds[t/100]);
            }
        }
    }
    return 0;
}
Grade 5 Result Rajsh 说:
Aug 29, 2022 10:48:39 PM

Government of the People’s Republic of Bangladesh, Directorate of Primary Education (DPE), is going to announce PSC Result 2022 in student wide on 30th December 2022 for all divisional Grade 5 exam result with Ebtedayee Result 2022 for annual final terminal examinations, The Primary School Certificate Examination Result 2022 will be announced for both of General and Madhrsah students in division wise to all education board known as Prathomik Somaponi Result 2022. Grade 5 Result Rajshahi BoardThe DPE has successfully conducted the class 5th grade PSC and Ebtedayee Examination tests from 17th to 24th November 2022 under all education boards of Dhaka, Chittagong, Comilla, Rajshahi, Sylhet, Barisal, Jessore, Dinajpur and Madrasah Board, and the DPE Grade-5 exams are successfully conducted at all 7,194 centers across the country.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter