首页 > 其他分享 >日记和编辑器

日记和编辑器

时间:2023-11-17 13:15:51浏览次数:36  
标签:le return idx int 编辑器 now 日记 op

日记和编辑器

\(n\) 个操作,5类:

  1. 在某个位置后插入一个字符串。
  2. 区间删除。
  3. 区间修改为一个字符串(长度可以不等)。
  4. 查询一段区间某种字符的出现次数
  5. 查询一段区间匹配模式串 \(P\) 的次数(\(P\) 固定)

\(1\le n\le 10^5,|s|\le 10^5,\sum|s|\le 10n,|P|\le 20\)。

对于前4个操作,考虑 fhq-treap

  1. 按照 \(siz\) 分裂,对于插入串建好树,然后缝合。
  2. 先分裂出 \(1\sim r\),再分裂出 \(1\sim l-1,l\sim r\),直接合并需要的两段。
  3. 先2后1
  4. 记录在节点信息中,每个节点的字母26种信息,首先是子树内的,自己再额外增加一个字符。
  5. 不太懂,考虑将树分裂出来,然后中序遍历转换成序列,然后跑KMP。

可以得到 \(22/25\)。

#include<iostream>
#include<random>
#include<cstring>
using namespace std;
random_device rnd;
mt19937 rd(rnd());
const int N=100010,M=30,K=10*N;
int n,rt,l[K],r[K],sz[K],idx,pri[K],cnt[K][M],cur,ne[M],plen;
char s[K],op[10],v[K],p[M];
void up(int p){
	for(int i=0;i<26;++i)cnt[p][i]=cnt[l[p]][i]+cnt[r[p]][i];
	cnt[p][v[p]-'a']++;
	sz[p]=sz[l[p]]+sz[r[p]]+1;
}
void split(int p,int &x,int &y,int k){
	if(!p){
		x=y=0;
		return;
	}
	if(sz[l[p]]+1<=k){
		x=p;
		split(r[p],r[p],y,k-sz[l[p]]-1);
	}
	else{
		y=p;
		split(l[p],x,l[p],k);
	}
	up(p);
}
int merge(int x,int y){
	if(!x|!y)return x|y;
	if(pri[x]>=pri[y]){
		r[x]=merge(r[x],y);
		up(x);
		return x;
	}
	else{
		l[y]=merge(x,l[y]);
		up(y);
		return y;
	}
}
int node(int k){
	v[++idx]=k;
	sz[idx]=1;
	pri[idx]=rd();
	cnt[idx][k-'a']++;
	return idx;
}
int build(int L,int R){
	if(L>R)return 0;
	// cout<<L<<' '<<R<<' '<<s[L+R>>1]<<"\n";
	if(L==R)return node(s[L]);
	int mid=L+R>>1,now=node(s[mid]);
	l[now]=build(L,mid-1);
	r[now]=build(mid+1,R);
	up(now);
	// printf("sz[%d]=%d,cnta=%d,cntb=%d\n",now,sz[now],cnt[now][0],cnt[now][1]);
	return now;
}
void ins(int p){
	int x,y,len=strlen(s+1);
	split(rt,x,y,p);
	int z=build(1,len);
	// printf("z=%d,x=%d,y=%d\n",z,x,y);
	rt=merge(merge(x,z),y);
}
struct sy{
	int x,y,z;
};
sy sp(int l,int r){
	int x,y;
	split(rt,x,y,r);
	int z;
	split(x,x,z,l-1);
	// cout<<x<<' '<<y<<' '<<z<<'\n';
	return {x,y,z};
}
void del(int l,int r){
	sy sys=sp(l,r);
	rt=merge(sys.x,sys.y);
}
void me(sy A){
	rt=merge(merge(A.x,A.z),A.y);
}
void expand(int p){
	if(l[p])expand(l[p]);
	s[++cur]=v[p];
	if(r[p])expand(r[p]);
}
void print(int p){
	// if(l[p])print(l[p]);
	// // up(p);
	// printf("#%d:sz=%d,v=%c\n",p,sz[p],v[p]);
	// for(int i=0;i<26;++i)
	// 	if(cnt[p][i])printf("letter %c:%d\n",i+'a',cnt[p][i]);
	// puts("\n");
	// if(r[p])print(r[p]);
}
void init(){
	plen=strlen(p+1); 
	for(int i=2,j=0;i<=plen;++i){
		while(j&&p[j+1]!=p[i])j=ne[j];
		if(p[j+1]==p[i])++j;
		ne[i]=j;
//		printf("ne[%d]=%d\n",i,j);
	}
}
void KMP(){
//	cout<<"plen="<<plen<<'\n';
	int ans=0;
	for(int i=1,j=0;i<=cur;++i){
		while(j&&p[j+1]!=s[i])j=ne[j];
		if(p[j+1]==s[i]){
			++j;
//			cout<<"up to "<<j<<'\n';
			if(j==plen)++ans,j=ne[j];
		}
	}
	cout<<ans<<'\n';
}
int main(){
	#ifndef ONLINE_JUDGE
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	#endif
	cin>>n>>p+1;
	init();
	while(n--){
		cin>>op;
		int l,r,p;
		if(*op=='I'){
			cin>>p>>s+1;
			ins(p);
			print(rt);
		}
		else if(*op=='D'){
			cin>>l>>r;
			del(l,r);
		}
		else if(*op=='R'){
			cin>>l>>r>>s+1;
			del(l,r);
			ins(l-1);
		}
		else if(*op=='C'){
			cin>>l>>r>>s+1;
			sy syn=sp(l,r);
			cout<<cnt[syn.z][s[1]-'a']<<'\n';
			me(syn);
			print(rt);
		}
		else{
			cin>>l>>r;
			cur=0;
			sy syn=sp(l,r);
			expand(syn.z);
			s[cur+1]=0;
// 			cout<<s+1<<'&'<<::p+1<<'\n'; 
			KMP();
			me(syn);
		}
	}
	return 0;
}

标签:le,return,idx,int,编辑器,now,日记,op
From: https://www.cnblogs.com/wscqwq/p/17770100.html

相关文章

  • 一篇文章搞定Cocos Creator中动画编辑器的使用
    在CocosCreator游戏开发中,动画特效的使用非常频繁,而动画特效的操作对初学者来说又相对复杂,所以,初学者一定要引起重视。对惹,这里有一个游戏开发交流小组,希望大家可以点击进来一起交流一下开发经验呀~动画编辑器使用1:创建一个节点;2:为这个节点添加一个动画组件cc.Anima......
  • Docker部署微信公众号排版编辑器
    绿联DX4600为例,首先我们打开Docker管理器,进入镜像管理,然后在镜像仓库中搜索wcjiang/wxmp​,选择latest​版本并下载。​​下载完成后,我们在本地镜像中找到刚刚下载的镜像,点击创建容器,起一个英文名,勾选创建后启动容器,点击下一步。​​在基础设置中,重启策略选择“容器退出......
  • 十三:文件操作类&编辑器&上传下载删除读写
    文件获取操作:1functiongetfilename()2{3$dir=getcwd();4$file=scandir($dir);5foreach($fileas$value)6{7if($value!='.'&&$value!='..')8{9$arr[]=$value;1......
  • windows系统使用终端和goland编辑器打包golang程序方法
    上一篇文章说了,windows系统,如何使用goland编辑器打包exe和linux程序,这篇文章再补充一下,使用终端和goland编辑器打包的对比情况。这里的终端可以是,cmd、WindowsPowerShell、MINGw64这里,我使用goland编辑器里面的Terminal,也就是WindowsPowerShelll来操作1、goland编辑器打......
  • Vue轻量级富文本编辑器-Vue-Quill-Editor
    先看效果图:女神镇楼1.下载Vue-Quill-Editornpminstallvue-quill-editor--save2.下载quill(Vue-Quill-Editor需要依赖)npminstallquill--save3.代码<template><divclass="edit_container"><quill-editorv-model="cont......
  • 富文本编辑器的内容转换成图片
    需求:pc端通过富文本编辑器,编辑商品详情页,然后生成图片,用于移动端展示之用。用到的库:wangEditor5和Dom-to-image(后者没找到官网,使用方法可自行百度,相关博客还是比较多的)常规科普: 1.wangEditor编辑器绑定的valueHtml即为字符串形式的dom结构。我们解码后可直接预览效果; 2.......
  • Linux Ubuntu部署C++环境与VS Code编辑器
      本文介绍在LinuxUbuntu操作系统下,配置VisualStudioCode软件与C++代码开发环境的方法。  在文章VMware虚拟机中安装LinuxUbuntu操作系统中,我们介绍了LinuxUbuntu操作系统的下载、安装方法;本文则基于前述基础,继续介绍在LinuxUbuntu操作系统中配置VisualStudioCode软......
  • 11.13日记
    默认情况下,Azure机器学习笔记本中提供了无服务器Spark计算。若要在笔记本中访问它,请从“计算”选择菜单的“Azure机器学习无服务器Spark”下选择“无服务器Spark计算”。笔记本UI还为无服务器Spark计算提供了Spark会话配置选项。配置Spark会话:   选择屏幕顶......
  • 11.12日记
    度器根据容量、队列等限制条件(如每个队列分配一定的资源,最多执行一定数量的作业等),将系统中的资源分配给各个正在运行的应用程序。调度器仅根据各个应用程序的资源需求进行资源分配,而资源分配单位用一个抽象概念“资源容器”(ResourceContainer,简称Container)表示,Container是一个动......
  • 11.11日记
    二叉查找树在频繁的动态更新过程中,可能会出现树的高度远大于log2n的情况,从而导致各个操作的效率下降。极端情况下,二叉树会退化为链表,时间复杂度会退化到O(n)。我上一节说了,要解决这个复杂度退化的问题,我们需要设计一种平衡二叉查找树,也就是今天要讲的这种数据结构。很多书籍里,但凡......