首页 > 其他分享 >20240201-高级数据结构随记

20240201-高级数据结构随记

时间：2024-02-03 09:45:18浏览次数：36  
标签：rt lb la int mid 20240201 数据结构 sumb 随记 

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    int mn=sum[0];
    for(int i=1;i<=n;i++){//枚举右端点
        if(sum[i]-mn>ans)ans=sum[i]-mn;
        if(mn>sum[i])mn=sum[i];
    }
}

最优贸易简化版 倍增

    3 --> 16
    走13步=8+4+1

    走1步 3 --> 4
    走4步 4 --> 8
    走8步 8 --> 16

    需要预处理每个向后走2^i步的最优解

    [3,4][4,5]
    f[3][0]+f[4][0]=f[3][1]

    [  L  ][  R  ]

更快的跳跃，从L走到R，需要走R-L步，把步数用二进制表示。
如果L到R需要走14步，L先走8步，到达L+8后再走4步，到达L+12后再走2步，到达R。
通过二进制数跳跃，每次跳过一段区间时，与分块类似。
需要预处理好每个点向后走2^j步的信息。
最小买入价格Mi[i][j]=min(Mi[i][j−1],Mi[i+2^(j−1)][j−1]);
最大卖出价格Mx[i][j]=max(Mx[i][j−1],Mx[i+2^(j−1)][j−1]);
最大收益F[i][j]=max{F[i][j−1],F[i+2^(j−1)][j−1],Mx[i+2^(j−1)][j−1]−Mi[i][j−1]};
单次询问的复杂度O(log n)

#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,k,c[500005],ans[500005],v[500005][21],mi[500005][21],mx[500005][21];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    for(int i=1;i<+n;i++) mi[i][0]=mx[i][0]=c[i];
    for(int i=1;(1<<i)<=n;i++){
        for(int j=1;j<=n-(1<<i)+1;j++){
            mi[j][i]=min(mi[j][i-1],mi[j+(1<<(i-1))][i-1]);
            mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
            v[j][i]=max(max(v[j][i-1],v[j+(1<<(i-1))][i-1]),mx[j+(1<<(i-1))][i-1]-mi[j][i-1]);
        }
    }
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        int res=0,step=r-l,mn=c[l];
        l++;
        for(int j=0;(1<<j)<=step;j++){
            if(step&(1<<j)){
                res=max(res,max(v[l][j],mx[l][j]-mn));
                mn=min(mn,mi[l][j]);
                l+=1<<j;
            }
        }
        printf("%d\n",res);
    }
    return 0;
}

最优贸易简化版 分块

把[L, R]分成很多块，枚举在每块中卖出，在之前的块中买入或者在当前块中买。
买入卖出发生在两个块时，需要知道第一块的最小值和第二个块的最大值,发生在一个块时，就需要知道这个块内最大值和最小值之差。
所以每个块就需要知道最大值、最小值、块内最大收益。
       L                            R
... 〇〇|〇〇〇 〇〇〇〇〇 〇〇〇〇〇 〇〇|〇〇〇 ...
    |_______| |_______| |______| |______|
块的大小为√n,两端最多扫描2√n个点，最多扫描√n个完整的块, 单次询问的复杂度为O(√n)。

#include<bits/stdc++.h>
int res;
int ma[n],mi[n],key[n];//数组下标代表其本身所代表组数的数据  key为当前组内本身能获得的最高利润
int job(int a,int b,int x,int a[]){
    int qq=a/x;//起点所在区
    int ww=b/x;//终点所在区
    if(qq==ww){
        int mi2=a[a];
        for(int i=a+1,i<=b;i++){
            res=max(res,a[i]-mi2);
            mi=min(mi,a[i]);
        }
    }
    else{
        int mi2=a[a];
        for(int i=a,i<(qq+1)*s){
            res=max(res,a[i]-mi2);
            mi=min(mi,a[i]);
        }
        for(int i=(qq+1)*s;i<=ww*s;i++){
            res=max(max(key[x],res),ma[x]-mi2);
            mi2=min(mi2,mi[x]);
        }
        for(int i=ww*s,i<=b,i++){
            res=max(res,a[i]-mi2);
            mi=min(mi,a[i]);
        }
    }
int main(){
    int a[n];
    int min=100000000,q;
    res=0;
    q=sqrt(n);
for(int i=0;i<=n;i++){
    int x=n/q;//x是当前所计算数据所属组数
    key[x]=max(key[x],a[i]-mi[x]）;
    mi[x]=min(min[x],a[i])
    ma[x]=max(ma[a],a[i]);
}

最优贸易简化版 线段树

前两种做法，都是把这个区间划分成好几块，进行跳跃完成交易。
考虑分治，对于询问的区间，可以把区间分成[L,x]和[x+1,R]。
最终的答案肯定是这3种情况中的一种：
（1）在[L, x]中进行买卖
（2）[x + 1, R]中进行买卖
（3）在[L, x]中买入，在[x + 1, R]中卖出。
可以在线段树上把区间分开并且合并。存储的信息也是最小值，最大值和最优值。
单次询问的复杂度O(log n)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
	int l,r,mx,lm,rm;
}tree[100005<<2];
int n,m,t;
int a[100005];
void up(int rt){
	tree[rt].lm=tree[rt<<1].lm;
	tree[rt].rm=tree[rt<<1|1].rm;
	tree[rt].mx=max(tree[rt<<1].mx,tree[rt<<1|1].mx);
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(a[mid]<a[mid+1]){
		if (tree[rt<<1].lm==mid-tree[rt].l+1) tree[rt].lm+=tree[rt<<1|1].lm;
		if (tree[rt<<1|1].rm==tree[rt].r-mid) tree[rt].rm+=tree[rt<<1].rm;
		tree[rt].mx=max(tree[rt].mx,tree[rt<<1].rm+tree[rt<<1|1].lm);
	}
}
void build(int rt,int l,int r){
	tree[rt].l=l;
	tree[rt].r=r;
	if(l==r){
		tree[rt].mx=tree[rt].lm=tree[rt].rm=1;
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	up(rt);
}
void update(int rt,int val,int p){
	if (tree[rt].l==tree[rt].r){
		a[p]=val;
		return;
	}
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if (p<=mid)	update(rt<<1,val,p);
	else update(rt<<1|1,val,p);
	up(rt);
}
int query(int rt,int l,int r){
	if (l<=tree[rt].l&&tree[rt].r<=r) return tree[rt].mx;
	int mid=(tree[rt].l+tree[rt].r)>>1;
	int s=0;
	if (l<=mid)	s=max(s,query(rt<<1,l,r));
	if (r>mid) s=max(s,query(rt<<1|1,l,r));
	if (a[mid]<a[mid+1]){
		s=max(s,min(tree[rt<<1].rm,mid-l+1)+min(tree[rt<<1|1].lm,r-mid));
    }
	return s;
}
signed main(){
	cin>>t;
	while (t--) {
		cin>>n>>m;
		for (int i=1;i<=n;i++) cin>>a[i];
		build(1,1,n);
		while (m--){
			string s;
			int x,y;
			cin>>s>>x>>y;
			if (s[0]=='Q')
				cout<<query(1,x+1,y+1)<<endl;
			else update(1,y,x+1);
		}
	}
	return 0;
}

新能源汽车厂

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char op[100005];
ll a[100005],b[100005],ans;
int n,m;
ll suma[400005],sumb[400005],la[400005],lb[400005];
void builda(int l,int r,int rt){
    if(l==r){
        suma[rt]=a[l];
        return;
    }
    int mid=(l+r)/2;
    builda(l,mid,2*rt);
    builda(mid+1,r,2*rt+1);
    suma[rt]=suma[2*rt]+suma[2*rt+1];
}
ll querya(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R) return suma[rt];
    int mid=(l+r)/2;
    if(la[rt]>0){
        la[2*rt]+=la[rt];
        suma[2*rt]+=la[rt]*(mid-l+1);
        la[2*rt+1]+=la[rt];
        suma[2*rt+1]+=la[rt]*(r-mid-1+1);
        la[rt]=0;
    }
    ll res=0,ret=0;
    if(L<=mid) res=querya(L,R,l,mid,2*rt);
    if(R>=mid+1) ret=querya(L,R,mid+1,r,2*rt+1);
    return res+ret;
}
void updatea(int L,int R,int l,int r,int rt,ll val){
    if(L<=l&&r<=R){
        la[rt]+=val;
        suma[rt]+=val*(r-l+1);
        return;
    }
    int mid=(l+r)/2;
    if(la[rt]>0){
        la[2*rt]+=la[rt];
        suma[2*rt]+=la[rt]*(mid-l+1);
        la[2*rt+1]+=la[rt];
        suma[2*rt+1]+=la[rt]*(r-mid-1+1);
        la[rt]=0;
    }
    if(L<=mid) updatea(L,R,l,mid,2*rt,val);
    if(R>=mid+1) updatea(L,R,mid+1,r,2*rt+1,val);
    suma[rt]=suma[2*rt]+suma[2*rt+1];
}
void buildb(int l,int r,int rt){
    if(l==r){
        sumb[rt]=b[l];
        lb[rt]=b[l];
        return;
    }
    int mid=(l+r)/2;
    buildb(l,mid,2*rt);
    buildb(mid+1,r,2*rt+1);
    sumb[rt]=sumb[2*rt]+sumb[2*rt+1];
}
ll queryb(int L,int R,int l,int r,int rt){
    if(L<=l && r<=R) return sumb[rt];
    int mid=(l+r)/2;
    if(lb[rt]>0){
        lb[2*rt]=lb[rt];
        sumb[2*rt]=(mid-l+1)*lb[rt];
        lb[2*rt+1]=lb[rt];
        sumb[2*rt+1]=(r-mid-1+1)*lb[rt];
        lb[rt]=0;
    }
    ll res=0,ret=0;
    if(L<=mid) res=queryb(L,R,l,mid,2*rt);
    if(R>=mid+1) ret=queryb(L,R,mid+1,r,2*rt+1);
    return res+ret;
}
void updateb(int L,int R,int l,int r,int rt,ll val)
{
    if(L<=l && r<=R){
        lb[rt]=val;
        sumb[rt]=val*(r-l+1);
        return ;
    }
    int mid=(l+r)/2;
    if(lb[rt]>0){
        lb[2*rt]=lb[rt];
        sumb[2*rt]=(mid-l+1)*lb[rt];
        lb[2*rt+1]=lb[rt];
        sumb[2*rt+1]=(r-mid-1+1)*lb[rt];
        lb[rt]=0;
    }
    if(L<=mid) updateb(L,R,l,mid,2*rt,val);
    if(R>=mid+1) updateb(L,R,mid+1,r,2*rt+1,val);
    sumb[rt]=sumb[2*rt]+sumb[2*rt+1];
}
void handle(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R){
        if(lb[rt]>0){
            ans-=lb[rt]*querya(l,r,1,n,1);
            return;
        }
    }
    int mid=(l+r)/2;
    if(lb[rt]>0){
        lb[2*rt]=lb[rt];
        sumb[2*rt]=(mid-l+1)*lb[rt];
        lb[2*rt+1]=lb[rt];
        sumb[2*rt+1]=(r-mid-1+1)*lb[rt];
        lb[rt]=0;
    }
    if(L<=mid) handle(L,R,l,mid,2*rt);
    if(R>=mid+1) handle(L,R,mid+1,r,2*rt+1);
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld %lld",&a[i],&b[i]);
        ans+=a[i]*b[i];
    }
    builda(1,n,1);
    buildb(1,n,1);
    while(m--){
        int l,r;ll x;
        scanf("%s %d %d %lld",op,&l,&r,&x);
        if(strcmp(op,"Add")==0){
            ll cnt=queryb(l,r,1,n,1);
            ans+=cnt*x;
            updatea(l,r,1,n,1,x);
        }
        else{
            handle(l,r,1,n,1);
            ans+=x*querya(l,r,1,n,1);
            updateb(l,r,1,n,1,x);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

标签：rt,lb,la,int,mid,20240201,数据结构,sumb,随记
From： https://www.cnblogs.com/Firepaw-cattery/p/18004362

相关文章

  • 20240202-训练赛随记
    机场检录//二分#include<bits/stdc++.h>usingnamespacestd;longlongn,m,a[100005];boolcheck(longlongx){longlongt=0;for(inti=1;i<=n;i++)t+=(x/a[i]);returnt>=m;}intmain(){cin>>n>>m;for(inti=1;i<......
  • 20240201-高级数据结构总结
    待办：倍增并查集线段树合并set逆序对树动态开点线段树套用模版#include<bits/stdc++.h>usingnamespacestd;#defineM100005#definelllonglongstructnode{ intL,R,cnt,vis;}tree[400005];inta[M],b[M],c[M],f[M];voidbuild(intp,intl,intr){ tre......
  • Python数据结构与算法03-单循环链表
    单循环链表classListNode:def__init__(self,val,next=None):self.val=valself.next=nextclassSingleLoopLinkList:def__init__(self,node=None):self.__head=nodeifnode:#如果不是空链表node.next=node......
  • 20240201
    Activity相关知识笔记Activity的基本用法手动创建Activity的方法创建和加载布局xml文件在AndroidMainifest中注册Activity，这一步通常是自动完成的。主Activity，启动器Activity在Activity中添加Menu，添加Toast通知销毁Activity使用Intent在Activity之间穿梭显式Intentvali......
  • 代数最值与函数随记
    代数式\(ax^2+bx+c\)的最值是(),（）时有最大值，()有最小值。代数解\[ax^2+bx+c\]\[=a(x^2+\frac{b}{a}x)+c\]\[=a[(x^2+\frac{b}{a}x+(\frac{b}{2a})^2]+c-\frac{b^2}{4a^2}·a\]\[=a(x+\frac{b}{2a})^2+\frac{4ac-b^2}{4a}\]\(\therefore\)易得，当\(x=-\fr......
  • python的十大数据结构之堆队列heapq(heap queue)
    heapqueque（堆队列），是一个完全二叉树，并且满足一个条件：每个节点（叶节点除外）的值都大于等于（或小于等于）它的子节点。提供了构建小顶堆的方法和一些小顶堆的基本操作方法（如入堆、出堆等），可以用于实现堆排序算法。创建堆的两种方法：importheapqlists=[3,10,20,52,2,83,52......
  • Redis 基础数据结构
    string（字符串）字符串string是Redis最简单的数据结构。Redis所有的数据结构都是以唯一的key字符串作为名称，然后通过这个唯一key值来获取相应的value数据。不同类型的数据结构的差异就在于value的结构不一样。字符串结构使用非常广泛，一个常见的用途就是缓存用户信息......
  • 【学习笔记】 - 可持久化数据结构初步：可持久化线段树
    前置知识：权值线段树权值线段树每个节点不再是区间，而是值在某个范围内的个数可以用于求区间第\(k\)大值动态开点一个点只有在需要时才被创建正文什么是可持久化数据结构就是说这个数据结构能保留每一个历史版本且支持操作可持久化线段树又称函数式线段树/主席树......
  • 文件系统(二)：分区、格式化数据结构
    liwen012024.01.28前言生活中，我们买回来的SD卡、TF卡、硬盘等存储设备一般是可以直接使用，如果要改变存储设备上的文件系统格式，我们一般直接在电脑上右键格式化就可以实现。买回来能直接用，是因为存储设备在出厂前厂家就已经做了分区和格式化操作。为什么存储设备需要分区格式......
  • 理解Set集合数据结构
    一、Set的基本概念Set是一种包含不重复元素的集合。与List（列表）不同，Set中的元素是无序的，不能通过索引来访问。Set中的每个元素都是唯一的，重复的元素将被自动剔除。二、Set的常见操作1.添加元素：使用add()方法向Set中添加新元素。如果添加的元素已经存在于Set中，则不会有任何改变......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99