10.2笔记

晨曦时雨 · 2022-10-02 15:20:21 · 个人记录

~~我不会告诉你因为受不了昨天那个老师讲课而听的稀里糊涂，而且下午考试，直接裂开，今天好好学习，因为换了个老师……~~

另：集训发奶茶祭

数据结构

数据结构：存储数据的结构（废话）

一句很有道理的话

不会有一种算法完全优于另一种算法，不然你就不会学它 
                                                ——zhx

~~对于数组和链表~~

单调队列

int q[maxn];
int head=1,tail=0;//head队列头 tail队列尾 
void push(int i)//要把z[i]加入队列 {
    while(head<=tail&&z[q[tail]]>=z[i])
        tail--;
    tail++;
    q[tail]=i;
}
cin>>n>>k;
for(int i=1;i<=n;i++)
    cin>>z[i];
for(int i=1;i<=k;i++)
    push(i);
cout<<z[q[head]]<<endl;
//O(n)
for(int i=k+1;i<=n;i++){
    push(i);//加入第i个数
    if (q[head] == i-k) head++;//删除第i-k个数
    cout<<z[q[head]]<<endl;
}

堆

插入一个数
删除一个数
询问当前堆里面有几个元素

C++里的优先队列（STL）

#include<queue>
using namespace std;
priority_queuw<int> heap;

heap.push(233);
heap.push(2333); //加入一个数
heap.top();//询问最大值
heap.pop()//删除最大值 
headp.size();//询问堆里面有几个元素

手写堆

struct dui{
    int n;//堆里面的元素 
    int z[maxn];
    int top(){
        return z[1];//返回最大值 
    }
    void push(int x){
        n++;
        z[n]=x;//放到最后一个位置 
        int p=n;
        while(p!=1){
            if(z[p]>z[p/2]){//如果当前点的权值大于它的父节点的权值 
                swap(z[p],z[p/2]);//交换 
                p=p/2;//跳上去 
            }
            else{
                break;//不然就不用动 
            }
        } 
    }
    void pop(){
        swap(z[1],z[n]);
        n--;
        int p=1;
        while(p*2<=n){//代表p还有左儿子 
            int pp=p*2;
            if(pp+1<=n && z[pp+1]>z[pp]) pp=pp+1;//pp就是左右儿子中比较大的哪一个 
            if(z[p]<z[pp]){//不满足性质 
                swap(z[p],z[pp]);//交换 
                p=pp;//跳 
            }
            else{
                break;
            }
        }
    } 
};

线段树

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define root 1,n,1
struct node{//线段树上的节点信息 
    int l,r;//这个节点的左端点和又断电所维护的区间 
    int sum;//当前这个区间的和 
    int maxv; //当前区间最大值 
    int minv;//当前区间的最小值 
    int sum2;//|a[l]-a[l+1]|+|a[l+1]-a[l+2|+……+|a[r-1]-a[r]|
    int lv,rv;//lv代表最左边的数，rv代表最右边的数 
    int ans;
    node(){
        l=r=sum=0;
    } 
}z[];
node operator+(const node &l,const node &r){
    node ans;
    ans.l=l.l;
    ans.r=r.r;
    ans.sum=l.sum+r.sum;
    ans.maxv=max(l.maxv,r.maxv); 
    int minv=min(l,minv,r,minv);
    ans.sum2=l.sum2+r.sum2+abs(l.rv-r.lv) ;
    ans.lv=l.lv;
    ans.rv=r.rv;
    ans.ans=max(l.ans,r.ans,l.maxv-v.minv);
    return ans;
}
void update(int rt){//合并 
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
void build(int l,int r,int rt){//建树 当前线段树节点编号为rt，而且当前区间喂l~r 
    if(l==r){//到最底层
        z[rt].l=z[rt].r=l;
        z[rt].sum=y[l];//这段区间的和就等于低l个数 
        return ;
    }
    int m=(l+r)>>1;
    //左儿子所对应的区间[l,m]右儿子所对应的区间[m+1,r] 
    build(lson);//build(l,m,rt*2)
    build(rson);//build(m+1,r,rt*2+1)
    update(rt);//更新rt这个节点 
}
node query(int l,int r,int rt,int nowl,int nowr){
    //当前线段树的节点所对应的区间l~r
    //当前线段树节点编号是rt
    //询问的区间是nowl~nowr
    if (nowl <= l && r <= nowr) return z[rt];
    int m=(l+r)>>1;
    if(nowl<=m){//询问区间的左儿子 
        if(m<nowr){
            return query(lson,nowl,nowr)+query(rson,nowl,nowr);//和做儿子和有儿子都有交集 
        }
        else return query(lson,nowl,nowr); //只和做儿子有交集 
    }
    else return query(rson,nowl,nowr);//只和有儿子有交集 
}
build(root);
int l,r;
node ans=query(root,l,r);