首页 > 其他分享 >2024.11.3 鲜花

2024.11.3 鲜花

时间:2024-11-03 16:21:12浏览次数:1  
标签:2024.11 ma 鲜花 int long 人偶 z1 out

浅谈 RMQ

비밀 인형극 II
  • 어느 한적한 마을 골목 안의 허름한 건물

  • 在某个僻静村庄胡同的破旧建筑里

  • 문을 열고 들어가면 작은 극장이 있죠

  • 开门进去便会见到一个小剧场

  • 솜씨 좋은 인형사가 연극을 마치고 떠나면

  • 一个手艺不错的人偶师演完戏离开的时候

  • 인형들은 극장 창고 안에 남겨져있죠

  • 人偶们便会留在剧场的仓库里

  • 밤이 되어 극장 안에 사람이 사라질 때쯤

  • 每当夜幕降临 人们离开剧场之时

  • 인형들은 조심 조심 혼자 움직이면서

  • 人偶们便会小心翼翼地开始行动

  • "오늘도 수고 많았어, 파티를 시작해볼까"

  • "今天也很辛苦了, 来开个派对吧"

  • 하며 아무도 없는 무대 위에 불을 밝히죠

  • 然后在无人的舞台上点亮闪烁的灯光

  • 군악대 병정 인형이 두둠칫 하며 북을 울리면

  • 军乐队的士兵人偶咚咚地敲着鼓

  • 다른 인형들은 리듬에 맞춰 춤추고 노래를 부르죠

  • 其他的人偶也在随着节奏起舞歌唱

  • 라랏타 흥이 넘치는 이곳은 비밀 무도회

  • 啦啦哒 兴致勃勃的这里是场秘密舞会

  • 힘들었던 일들일랑 잠시 잊고 즐겨 볼까요?

  • 先暂时忘掉那些劳累的事来一起享受一下吧?

  • 라라랏탓타 어서 오세요 비밀의 인형극에

  • 啦啦啦哒哒 欢迎来到这场秘密人偶剧

  • 그댈 얽매는 모든 것을 두고 춤을 춰봐요

  • 在这里放下束缚你的一切来尽情共舞吧

  • 그대가 어떤 존재였는지 누구도 묻지 않으니

  • 没有人会询问你到底是什么样的存在

  • 인형의 몸과 음악 위에 당신을 맡겨 보아요

  • 就将你自己托付给那人偶的身躯和音乐吧

  • 라라랏탓타 함께 불러요 비밀의 인형극

  • 啦啦啦哒哒 一起歌唱吧 就在这秘密人偶剧

  • 어느 한적한 마을 골목을 떠도는 작은 유령들

  • 在某个僻静村庄胡同里游荡的小幽灵们

  • 갈곳 없는 망령들은 거리 곳곳을 헤맸죠

  • 那些无处可归的亡灵们也在街上到处游荡

  • 삶에 미련이 남아 사라지지 못하는 그들은

  • 他们无法抛弃对生活的无尽向往

  • 작은 극장 한켠의 인형 속에 숨어버렸죠

  • 便都藏在了小剧场的人偶里

  • 밤이 되어 극장 안에 사람이 사라질 때쯤

  • 每当夜幕降临 人们离开剧场之时

  • 인형들은 조심 조심 각자 움직이면서

  • 人偶们便会小心翼翼地开始行动

  • "춤추고 놀다 보며는 미련을 잊을 수 있어"

  • "只要尽情地跳舞玩耍就能够忘记对生活的向往"

  • 하며 밤마다 그들만의 작은 축제를 열죠

  • 于是每天晚上都会举行他们自己的小庆典

  • 인형의 몸이 불편해 발이 꼬이고 넘어져도

  • 就算人偶的身体不好使 扭到脚便会摔倒

  • 다른 이들과 함께한다면 그마저 즐거운 일이죠

  • 但倘若能与他人共度时光 也会是很愉快的事啊

  • 라랏타 흥이 넘치는 이곳은 인형 무도회

  • 啦啦哒 兴致勃勃的这里是场秘密舞会

  • 힘들었던 일들일랑 잠시 잊고 즐겨 볼까요?

  • 先暂时忘掉那些劳累的事来一起享受一下吧?

  • 라라랏탓타 어서 오세요 비밀의 인형극에

  • 啦啦啦哒哒 欢迎来到这场秘密人偶剧

  • 그댈 얽매는 모든 것을 두고 춤을 춰봐요

  • 在这里放下束缚你的一切来尽情共舞吧

  • 그대가 어떤 존재였는지 누구도 묻지 않으니

  • 没有人会询问你到底是什么样的存在

  • 인형의 몸과 음악 위에 당신을 맡겨 보아요

  • 就将你自己托付给那人偶的身躯和音乐吧

  • 라라랏탓타 밤이 끝나고 태양이 떠오르면

  • 啦啦啦哒哒 夜晚消逝 太阳又照常升起

  • 파티는 막을 내리고 인형은 멈추겠지만

  • 派对会落下帷幕 人偶也会逐渐停下来

  • 그대가 가진 아픈 기억을 조금이라도 덜어냈다면

  • 但若能从痛苦的记忆中抹除一些的话

  • 내일 밤에도 찾아오기를 기대해도 되겠죠?

  • 也很期待你明天晚上还会再来吧?

  • 라라랏탓타 함께 불러요 비밀의 인형극

  • 啦啦啦哒哒 一起歌唱吧 就在这秘密人偶剧

考虑优秀的复杂度算法。

四毛子:

大体分为四步:

  1. 建立笛卡尔树,复杂度 \(O(n)\)。

  2. 维护一个以欧拉序为下标深度为值的数组,复杂度 \(O(n)\)。

考虑性质,发现相邻两个之间的差之多为一,问题变成了 \(\pm1\) RMQ,考虑维护。

  1. 将原序列分块,块长为 \(\log(n)\),对于每块求出最值,前后缀最值,块间用 ST 表维护,复杂度 \(O(n)\),于是我们可以 \(O(1)\) 查询端点在不同块之间的询问。

  2. 考虑端点在同一块的询问,发现对于一个左端点固定的长度至多为 \(\log(n)\) 的序列,其至多有 \(\sum\limits_{i=1}^{\log(n)} 2^{i-1} \le n\) 种方案,所以暴力预处理出所有情况,预处理块间差分,每次查表即可。复杂度 \(O(n)+O(1)\)

发现其实现难度和代码常数过于巨大,于是有了一下简单做法。

二毛子:

名字取自 P3793 由乃救爷爷 的一篇题解。

考虑直接去掉四毛子的前两步,考虑维护块间。

其实直接再上一个 ST 表就可以做到 \(O(n\log\log n)+O(1)\) 的,常数也不小,但是实现难度大大降低。

发现长度 \(\log n\) 一般不会超过 \(64\),考虑状压。

具体的,用单调栈维护最值,用 unsigned long long 压栈内元素状态,查询时用位运算拆掉 \(<l\) 做 \(lowbit\) 即可。

复杂度依然是 \(O(n)+O(1)\),并且因为位运算和 \(n\) 的大小的原因,常数巨小。

然而还有一种暴力:

对于块内的询问直接暴力,发现其基本不会落在这个区间,也可以通过微调块长来避免。

既然暴力就暴力到底,直接每 \(\sqrt{n}\) 分一块,每次直接暴力即可,期望是 \(O(n)+O(1)\) 的,通过微调块长依然不太会被卡,常数也很小。

放一下由乃救爷爷的代码,均没卡常:

暴力分块 17.12 s
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
	FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
	FILE *InFile=stdin,*OutFile=stdout;
#endif

namespace GenHelper{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_(){
	    b=((z1<<6)^z1)>>13; z1=((z1&4294967294U)<<18)^b;
	    b=((z2<<2)^z2)>>27; z2=((z2&4294967288U)<<2)^b;
	    b=((z3<<13)^z3)>>21; z3=((z3&4294967280U)<<7)^b;
	    b=((z4<<3)^z4)>>12; z4=((z4&4294967168U)<<13)^b;
	    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x){using namespace GenHelper;z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read(){
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

const int N=2e7+3,L=4480;
int n,m,s,c[N],id[N],bg[L],ed[L],cma[L][L],pm[N],nm[N],bl,B; unsigned long long ans;

int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m>>s; srand(s); B=max(2,int(sqrt(n)));
	bg[++bl]=1; for(int i=1;i<=n;++i) c[i]=read(),((i%B==0)&&(ed[bl]=i-1,bg[++bl]=i)),id[i]=bl; ed[bl]=n;
	for(int i=1;i<=bl;++i){
		int ma=0; for(int j=bg[i];j<=ed[i];++j) ma=max(ma,c[j]),pm[j]=ma;
		ma=0; for(int j=ed[i];j>=bg[i];--j) ma=max(ma,c[j]),nm[j]=ma;
		cma[i][i]=ma;
	}
	for(int i=1;i<=bl;++i){
		int ma=cma[i][i];
		for(int j=i-1;j;--j) ma=max(ma,cma[j][j]),cma[j][i]=ma;
	}
	for(int i=1;i<=m;++i){
		int l=read()%n+1,r=read()%n+1; if(l>r) swap(l,r);
		if(id[l]==id[r]){
			int ma=0; for(int i=l;i<=r;++i) ma=max(ma,c[i]);
			ans+=ma;
		}else ans+=max({cma[id[l]+1][id[r]-1],nm[l],pm[r]});
	}
	cout<<ans<<endl;
}
状压 11.24 s
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
	FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
	FILE *InFile=stdin,*OutFile=stdout;
#endif

namespace GenHelper{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_(){
	    b=((z1<<6)^z1)>>13; z1=((z1&4294967294U)<<18)^b;
	    b=((z2<<2)^z2)>>27; z2=((z2&4294967288U)<<2)^b;
	    b=((z3<<13)^z3)>>21; z3=((z3&4294967280U)<<7)^b;
	    b=((z4<<3)^z4)>>12; z4=((z4&4294967168U)<<13)^b;
	    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x){using namespace GenHelper;z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read(){
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

const int N=2e7+3,B=64,L=N/B+3;
#define id(p) (p+63>>6)
#define bl(i) (i-1<<6|1)
#define br(i) (i<<6)
int n,m,s,c[N],pm[N],nm[N],bln; unsigned long long ans,sta[N];

class St{
private: const static int LG=19; int o[LG+3][L];
public:
	int &operator[](int p){return o[0][p];}
	void In(int l){for(int i=1;i<=LG;++i) for(int j=1;j+(1<<i)-1<=l;++j) o[i][j]=max(o[i-1][j],o[i-1][j+(1<<i-1)]);}
	int operator()(int l,int r){if(l>r) return 0; int k=__lg(r-l+1); return max(o[k][l],o[k][r-(1<<k)+1]);}
}st;

void In(){
	int stk[N],*top;
	for(int i=1;i<=bln;++i){
		int ma=0; for(int j=bl(i);j<=br(i);++j) ma=max(ma,c[j]),pm[j]=ma;
		ma=0; for(int j=br(i);j>=bl(i);--j) ma=max(ma,c[j]),nm[j]=ma;
		st[i]=ma; top=stk;
		for(int j=bl(i);j<=br(i);++j){
			if(j!=bl(i)) sta[j]=sta[j-1];
			while(top!=stk&&c[*top]<=c[j]) sta[j]^=1ull<<(*top--)-bl(i);
			*++top=j,sta[j]|=1ull<<j-bl(i);
		}
	} st.In(bln);
}

int Ma(int l,int r){
	int il=id(l),ir=id(r);
	if(il==ir) return c[l+__builtin_ctzll(sta[r]>>l-bl(il))];
	else return max({st(il+1,ir-1),nm[l],pm[r]});
}

int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m>>s; srand(s);
	for(int i=1;i<=n;++i) c[i]=read(); bln=id(n),In();
	for(int i=1;i<=m;++i){int l=read()%n+1,r=read()%n+1; if(l>r) swap(l,r); ans+=Ma(l,r);}
	cout<<ans;
}

Kaguya 和 critno 他们好像搞了个支持修改的,但是做法过于优秀,感觉只有 YY 的作用了。

标签:2024.11,ma,鲜花,int,long,人偶,z1,out
From: https://www.cnblogs.com/xrlong/p/18522436

相关文章

  • 2024.11.2 2024ICPC成都站
    Solved:7/13Penalty:793Rank:40Rank(ucup):152L.RecoverStatistics输出50个P50、45个P95,4个P99和1个P99+1即可。#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(0);cin.tie(0);inta,b,c;cin>>a>&g......
  • 2024.11.2 模拟赛
    2024.11.2模拟赛T1P11242碧树把\(n\)个点往外连即可。最终答案为\(n-\max_{i=1}^na_i+1\)T2P11243繁花感觉我的做法麻烦了,而且随机复杂度()显然的,从左往右看可以分层,遇到一次大于号分一次。对于每段,遍历一遍,每遇到一次小于号计算一次答案。如果不考虑等于号,这段的......
  • 【开题报告】基于Springboot+vue网上鲜花销售平台设计与实现(程序+源码+论文) 计算机毕
    本系统(程序+源码)带文档lw万字以上文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着互联网技术的迅猛发展和电子商务的普及,人们的购物方式发生了翻天覆地的变化。传统的鲜花销售模式依赖于实体花店,时间和空间上的限制使得消费者在......
  • 2024.11.02模拟赛
    挂了至少30分!!不——开——心——钢哥说,大家要休息好,于是模拟赛晚点,变成了3小时3道题。T1打的正解(但没调出来版),T2T3打的暴力(但全挂了版),预计总分120+,但实际总分80。小小总结一下:昨晚多睡了一小时,今天思路确实感觉更清晰了(但也有可能是因为题目不难……)。但今天时间没分配......
  • 鲜花:基于位运算的 A+B Problem
    前置知识:二进制、按位与&、按位异或^、左移<<。按位异或的本质是二进制下不进位的加法,也就是对于每一位将值相加再直接对\(2\)取模。由于^和+有相同之处,考虑什么时候两者不同,很明显是二进制下需要进位的时候,那么什么时候需要进位呢?枚举可知,只有两个数该位都为\(1\)是该位需要......
  • 日记 2024.11.1:2024 syzx 秋季训练 4
    E令\(m=s/2\)。将\(r<m\)的区间称作A类,\(m<l\)的B类,\(l\leqm\leqr\)的C类。A、B类可以互相匹配,过程如下:将B翻转,假如A类都叫\([l_i,r_i]\),B类对称翻转后叫作\([l_j,r_j]\),将\(l_i,r_j\)混合从小到大排序,维护一个升序的set,遇到\(l_i\)时将\(r_i\)插......
  • 2024.11.01模拟赛
    唉不——开——心——有些话就不说了。T1打假了,打了T3、T4的特殊样例(共10分),原本是抱着爆0的心态的,结果没想到T1数据水到直接给了我70分——但T3T4爆掉了,总分70分。差点爆0,不——开————心——————题目小链接T1【二分图匹配】题目大意:给出两个长度分别为n,m(1......
  • 2024.11.1 test
    B维护长度为二的次幂的数组,支持单点修改,区间和,全局执行以下三种操作之一:for(inti=0;i<n;i++)b[i]=0;for(inti=0;i<n;i++)b[i()x]+=a[i];for(inti=0;i<n;i++)a[i]=b[i];()里为或,且,异或中的一种。\(n\le2^{19}\)。考虑线段树维护。注意到如果为或/且,那么相当于对......
  • 2024.11.1总结
    本文于github博客同步更新。OI相关:A:分为两种情况处理:\(u\)到\(lca\)和\(lca\)到\(v\)。我的做法是先树剖,将每条链单独拿出来拉出来,根据\(a_i\)和\(b_i\)连边,正反各建一棵树,维护一下\(k\)级祖先。然后从\(u\)到\(v\)的时候每次根据从dfs序由小到大还是由......
  • MindSponge分子动力学模拟——增强采样(2024.11)
    技术背景关于增强采样(EnhancedSampling)算法的具体原理,这里暂不做具体介绍,感兴趣的童鞋可以直接参考下这篇综述文章:Enhancedsamplinginmoleculardynamics。大致的作用就是,通过统计力学的方法,使得目标分子的CV(CollectiveVariables)具有一个尽可能大的采样子空间,并且可以将其还......