首页 > 其他分享 >数据结构专题总结

数据结构专题总结

时间:2022-11-03 22:00:52浏览次数:56  
标签:总结 rt 专题 int prime pos include 数据结构

打了一天的数据结构,感觉码力上升的很快,而且也学会了许多方法,但总体来说今天大部分的题很多都是看完题解以后才会的,无论怎么想也想不出来,还是要提高一下想题的能力,不要走神,不要急躁,仔细思考,不要颓废,还是要抓紧数据结构题的暴力,一般都很多,所以想不出正解一定要打暴力啊。

\(A\)

求区间 \(lcm\)。

对于 \(lcm\) 的数学性质的分析,我们发现我们只需要对于一个数每一个质因子(质数,质数的次幂在此均算质因子)在之前的出现位置上除以一个他的质数,(即在形如 \(p^k\) 的上一次出现的位置除去一个 \(p\)),就可以保证将重复的部分除去了(设 \(i<j\),如果 \(p^k \mid a_i \land p^{k+1} \mid a_j\),那么我们将在处理到 \(j\) 时,对于 \(i\) 位置的 \(p\) 的 \([1,k]\) 次方,除去 \(k\) 个 \(p\),我们再将 \(p^{k+1}\) 插入 \(j\) 位置,这样保证当区间左端点小于 \(i\) 时,即我们要求的 \(lcm\) 的元素包含 \(a_i\) 时,可以除去多余元素,当不包含时,保留这部分答案),那么我们只需要处理 \([l,r]\) 的积即可,我们发现如果离线,我们可以处理到区间右端点时统计答案,但本题强制在线,所以我们用主席树来维护。

\(code\)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define lson(rt) (tree[rt].ls)
#define rson(rt) (tree[rt].rs)
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int root[N];
int pos[N<<1];
int a[N],n,Q;
long long ans=0;
struct Prisident_Tree{
    struct Pri{
        int ls,rs,sum;
        Pri(){ls=0,rs=0,sum=1;}
    }tree[40000000];
    int tot;
    void pushup(int rt){tree[rt].sum=(1ll*tree[lson(rt)].sum*tree[rson(rt)].sum%mod);}
    int insert(int rt,int l,int r,int pos,long long val){
        int k=++tot;
        tree[k]=tree[rt];
        if(l==r){
            tree[k].sum=1ll*tree[rt].sum*val%mod;
            return k;
        }
        int mid=(l+r)>>1;
        if(pos<=mid)lson(k)=insert(lson(rt),l,mid,pos,val);
        else rson(k)=insert(rson(rt),mid+1,r,pos,val);
        pushup(k);
        return k;
    }
    long long ask(int rt,int l,int r,int pos){
        if(l>=pos)return 1ll*tree[rt].sum;
        if(r<pos)return 1;
        int mid=(l+r)>>1;
        return 1ll*ask(lson(rt),l,mid,pos)*ask(rson(rt),mid+1,r,pos)%mod;
    }
}T;
int prime[N<<1],not_prime[N<<1],min_prime[N<<1];
long long ny[N<<1];
void init(){
    ny[1]=1;
    for(int i=2;i<=200000;i++)ny[i]=1ll*(mod-mod/i)*ny[mod%i]%mod;
    not_prime[1]=1;
    min_prime[1]=0;
    for(int i=2;i<=200000;i++){
        if(!not_prime[i])prime[++prime[0]]=i,min_prime[i]=i;
        for(int j=1;j<=prime[0];j++){
            if(i*prime[j]>200000)break;
            int k=i*prime[j];
            not_prime[k]=1;
            min_prime[k]=prime[j];
            if(i%prime[j]==0)break; 
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    init();
    for(int i=1;i<=n;i++){
        root[i]=root[i-1];
        while(min_prime[a[i]]){
            int k=min_prime[a[i]],t=1;
            while(a[i]%k==0){
                t*=k,a[i]/=k;
                if(pos[t])root[i]=T.insert(root[i],1,n,pos[t],ny[k]);
                pos[t]=i;
            }
            root[i]=T.insert(root[i],1,n,i,t);
        }
    }
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++){
        int s1=0,s2=0;
        scanf("%d%d",&s1,&s2);
        s1=(s1+ans)%n+1,s2=(s2+ans)%n+1;
        if(s1>s2)swap(s1,s2);
        ans=T.ask(root[s2],1,n,s1)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

标签:总结,rt,专题,int,prime,pos,include,数据结构
From: https://www.cnblogs.com/hxqasd/p/16855999.html

相关文章

  • 数据结构之线性表的顺序表示和实现1
    #defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefcharElemType;//一些数据......
  • MyBatis初学心得和收获总结
    首先MyBatis是一个优秀的大型持久层框架,用于简化JDBC的开发,javaee分为表现层、业务层和持久层三层架构。框架是一个半成品软件。利用MyBatis可以简化JDBC的书写,在后续的开......
  • 数据结构 玩转数据结构 6-4 深入理解递归终止条件
    0课程地址https://coding.imooc.com/lesson/207.html#mid=13456 1重点关注1.1代码草图   1.2二分搜索树添加元素代码简化......
  • 今日总结
    498.对角线遍历设置一个标志,控制右上还是左下;首先正常的移动你的坐标;然后判断有没有你变换后的坐标,有没有越界;如果越界了,就变换一下;这里变换右上有两种;左下有两种;w......
  • #yyds干货盘点# 动态规划专题:打家劫舍(二)
    1.简述:描述你是一个经验丰富的小偷,准备偷沿湖的一排房间,每个房间都存有一定的现金,为了防止被发现,你不能偷相邻的两家,即,如果偷了第一家,就不能再偷第二家,如果偷了第二家,那么就......
  • 11月3日内容总结——对象之动静态方法、继承及相关知识点、类中名称查找顺序及经典类
    目录一、动静态方法动态方法静态方法二、面向对象之继承的概念面向对象三大特性1.继承的含义2.继承的目的3.继承解决了什么问题4.多继承的优缺点5.继承的实操三、继承的本......
  • Java实现ip属地功能开发教程 | ip2region2.x使用总结
    ip属地功能开发-ip2region2.x使用总结一、前言如今许多软件如B站、微博、抖音等都加上IP归属地防止恶意评论,境外用户显示的是国家,国内的用户显示的省份。兴致一起,我便......
  • 计算机二级python备考刷题知识点总结(二)
    1、center()语法:str.center(width,fillchar)注:fillchar必须要用引号引起了center()返回一个原字符串居中,并使用填充字符填充到长度为width的新字符串,默认填充字符为空格......
  • 《上帝掷骰子吗》总结
    目录总结波粒大战的三个节点经典物理学的“两朵乌云”大统一理论总结简单说,书是围绕“光是波还是粒子”之争展开的物理学科普。光,是我们每个人见得最多的东西。自古就被......
  • Java String常用API总结
    Stringname;用于字符串拼接StringBuildersb=newStringBuilder();获取字符串长度name.length());指定字符在此字符串中第一次出现的索引name.indexOf('z'));nam......