文档章节

洛谷P5211 [ZJOI2017]字符串(线段树+乱搞)

o
 osc_fmg49rzg
发布于 2019/03/20 09:14
字数 1378
阅读 6
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题面

传送门

题解

为什么大佬们全都是乱搞的……莫非这就是传说中的暴力能进队,乱搞能AC……

似乎有位大佬能有纯暴力+玄学优化$AC$(不算上$uoj$的$Hack$数据的话……这要是放到考场上就是切题的啊……)

整体思路呢,就是我们开一个线段树,线段树上的每一个区间维护“以这个区间右端点为结尾有可能成为后缀最小值的位置”

怎么合并呢

首先右儿子的所有节点都是可以加入的,因为它们后面也没有加上什么东西

然后对于左儿子来说它们相当于后面被整体怼了一个串,我们就要考虑它们是不是仍有可能成为后缀最小值了

首先比较两个位置的字典序大小,我们记$u$表示$s[u,r]$,$v$表示$s[v,r]$,假设$u$比$v$长,如果$v$不是$u$的前缀那么它们已经比较出了字典序大小,两个中肯定可以扔掉一个

然而如果$v$是$u$的前缀,事情就会变得比较辣手了

先给出结论:如果$v$是$u$的前缀,$v$就没有用了

为啥嘞?

因为它们都来自当前区间的左儿子,那么$v$的长度最短是$r-mid+1$,$u$的长度最长是$r-l+1$,根据我们正常线段树的写法$v$的长度绝对大于$u$的长度的一半

因为$v$的长度大于$u$的一半,同时$v$既是$u$的前缀也是它的后缀,那么我们发现$u$必定是一个有周期串,而且右儿子中至少有一个周期的开头$w$

所以现在$w$的字典序比它更小

那么加上新的字符之后$v$有没有可能变成后缀最小值呢?

答案是否定的,如果加的字符就是周期串上该有的字符,$w$比$v$小,如果加的字符小于该有的字符,$w$还是比$v$小,如果加的字符大于该有的字符,$u$就比$v$小,所以$v$无论如何都不可能再作为后缀最小值了

也就是说这个区间会把右儿子全都加上来,左端点最多加一个,那么一个节点上存的位置最多不会超过$O(\log n)$

所以我们只需要能在线段树上维护区间加以及判断字典序就行了

先说正解吧,判断字典序可以二分加哈希找到最后一个相等的位置再判断下一位的大小,不过我们要在区间加的状况下维护哈希值很困难,这样的话我们得把哈希值分块,一次修改就是$O(\sqrt{n})$了

正解的代码……去看$shadowice$巨巨的吧……才不是因为太长了不想打呢

于是这里区间加直接暴力,判断字典序也直接暴力……似乎是因为数据太水所以可以过……

而且我看了看$uoj$上这题排名前几的好像全都是打暴力的……跑得比正解快啊……

代码抄kcz的

//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
inline int getop(){R char ch;while((ch=getc())>'9'||ch<'0');return ch-'0';}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=2e5+5;
int s[N],n,q;
inline int cmp(const int &a,const int &b,const int &r){
	fp(i,0,r-max(a,b))if(s[a+i]!=s[b+i])return s[a+i]<s[b+i]?-1:1;
	return 0;
}
struct node{
	node *lc,*rc;int pos[21],cnt,l,r;
	inline void ins(R int x){pos[++cnt]=x;}
	void upd(){
		fp(i,1,rc->cnt)pos[i]=rc->pos[i];
		cnt=rc->cnt;
		fp(i,1,lc->cnt)
			while(233){
				int t=cmp(lc->pos[i],pos[cnt],r);
				if(t>0)break;
				if(!t){
					(((r-pos[cnt]+1)<<1)>r-lc->pos[i]+1)?--cnt:0,
					pos[++cnt]=lc->pos[i];
					break;
				}
				if(!--cnt){
					pos[++cnt]=lc->pos[i];
					break;
				}
			}
	}
}pool[N<<2],*rt;
int tot,ql,qr,res,d;
inline node* newnode(){return &pool[tot++];}
void build(node* &p,int l,int r){
	p=newnode(),p->l=l,p->r=r;
	if(l==r)return p->ins(l),void();
	int mid=(l+r)>>1;
	build(p->lc,l,mid),build(p->rc,mid+1,r);
	p->upd();
}
void update(node* p){
	if(ql<=p->l&&qr>=p->r)return;
	if(ql<=p->lc->r)update(p->lc);
	if(qr>p->lc->r)update(p->rc);
	p->upd();
}
void query(node* p){
	if(ql<=p->l&&qr>=p->r){
		R int i=1;!res?res=p->pos[i++]:0;
		for(;i<=p->cnt;++i)cmp(p->pos[i],res,qr)<0?res=p->pos[i]:0;
		return;
	}
	if(qr>p->lc->r)query(p->rc);
	if(ql<=p->lc->r)query(p->lc);
}
int main(){
//	freopen("testdata.in","r",stdin);
//	freopen("qwq.out","w",stdout);
	n=read(),q=read();
	fp(i,1,n)s[i]=read();
	build(rt,1,n);
	while(q--)if(getop()&1){
		ql=read(),qr=read(),d=read();
		if(qr-ql+1<=(n>>1))fp(i,ql,qr)s[i]+=d;
		else{
			fp(i,1,ql-1)s[i]-=d;
			fp(i,qr+1,n)s[i]-=d;
		}
		update(rt);
	}else{
		ql=read(),qr=read(),res=0;
		query(rt),print(res);
	}
	return Ot(),0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
模板柱(持续更新)

以下是本蒟蒻认为的NOIP范围内的所有模板,自认为写的又好懂又好记。按照的顺序编排,提供所有OJ模板题链接和代码。希望能帮助大家。 PDF链接 快速幂||取余运算 洛谷模板 三分法 洛谷模板 ST...

osc_3g985sb6
2018/10/17
2
0
[总结]2020年2月 OI学习/刷题记录

2020/2/1 LibreOJ #2098. 「CQOI2015」多项式 数论+高精度 POJ 2411 Mondriaan's Dream 插头DP HDU 1565 方格取数(1) 状压DP HDU 2167 Pebbles 插头DP Luogu 「ACOI2020」Assassination Cla......

osc_2w18qc4t
02/01
7
0
QAQorz的训练记录

感觉还是该从今天开始记下来 5.8日查询 870(查询系统) + 100(洛谷) + 100(牛客) = 1070题, 去重按1000题算 5.8 牛客寒训营 3F 双向搜索+处理前后缀积 牛客寒训营 5G 唯一分解, 埃氏筛法的理解...

osc_k0q149k0
2019/05/08
1
0
[BZOJ3682] Phorni

Description 有一个长度为 $len$ 的字符串和 $n$ 个幻影,每个幻影站在字符串的某个字符上,代表从该位置到字符串末尾的一个后缀。要求支持以下三个操作:在字符串开头添加一个字符 改变幻影...

osc_ertc0ko2
2019/01/21
1
0
线段树模板

sol:模板题就不解释了 洛谷-P3372-线段树1 线段树 #include "bits/stdc++.h"using namespace std;typedef long long LL;const int MAXN = 100010;struct Node { } segTree[MAXN * 4];void ......

osc_t8hom09j
2019/06/18
2
0

没有更多内容

加载失败,请刷新页面

加载更多

科技人文丨玻璃心:承受阈值与表达

大家好,我是SKODE。 有趣的灵魂,聊科技人文。 本系列博客地址:传送门 本文转载自B站:安慰记传送门 玻璃心是网络用语,意思是: 对负面事件的接受度很低 还有对别人可能给出的负面评价非常...

osc_u9mt0sus
1分钟前
0
0
迅睿CMS 游客不允许上传附件

游客不允许上传附件 迅睿CMS系统:https://www.xunruicms.com/ 本文档原文地址:https://www.xunruicms.com/doc/752.html...

迅睿CMS-PHP开源CMS程序
1分钟前
0
0
代理,注解,接口和实现类的小测验

* retention : 保留* policy : 策略 ps : 简单测试了一下手写代理,jdk动态代理,和cglib动态代理,根据其不同的结果分析其原理 一:测试目的 主要想看一下不同的代理模式对于目标类中方法上注...

岁一
2分钟前
0
0
V-Ray 5 For 3ds Max 正式发布:超越渲染 - 知乎

15个新功能,V-Ray5助你时间更节省,渲染更出色! 作者:ChaosGroup VRay 5 For 3ds Max 已正式发布! 2分钟视频,抢先预览新功能↓ 知乎视频 www.zhihu.com V-Ray 5 for 3ds Max 新增功能 ...

osc_o9u1um45
2分钟前
0
0
毕业的笑容和悲伤永远是校园的回忆

校园的风轻轻的拂过我的脸庞,风儿显得更加凉爽, 开满火红的凤凰树,染遍了校园的每个角落, 晚上那枝头蝉儿的竞相鸣奏,唱满了令人不舍的毕业歌, 它们彷彿告诉了我们要毕业了。 毕业典礼那...

瑾123
3分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部