首页 > 其他分享 >区间推平,区间查询循环节

区间推平,区间查询循环节

时间:2024-10-30 19:09:47浏览次数:1  
标签:hash cov int 推平 LL rs 查询 区间 return

区间推平,区间查询循环节

题意

给定一个字符串 \(s\) , 请你支持两种操作:

\(1, l, r, c\):将 \([l,r]\) 之间的字符改为 \(c\)。

\(2, l, r, d\):询问 \([l,r]\) 之间是否有长度为 \(d\) 的循环节,有输出 YES,否则输出 NO

思路

使用线段树维护区间哈希值,区间推平使用等比数列计算。

区间 \([l,r]\) 有长度为 \(d\) 的循环节当且仅当 \([l,r-d]=[l+d,r]\),使用哈希判断。

时间复杂度:\(O(n+q\log n)\)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6 + 5;
using LL = long long;

const LL mod = 1e9 + 7;
const LL base = 17;

LL pw[N];
LL inv_base;

LL qpow(LL x, LL y, LL p) {
	LL res = 1;
	for (; y; y >>= 1, x = x * x % p)
		if (y & 1) res = res * x % p;
	return res;
}

LL inv(LL x, LL p) {
	return qpow(x, p - 2, p);
}

struct segt {
	struct node {
		int l, r, cov;
		LL hash;
		node() {
			l = r = 0;
			cov = -1;
			hash = 0;
		}
	} t[N << 2];
#define ls (p << 1)
#define rs (p << 1 | 1)
	friend node operator + (node x, node y) {
		node res;
		res.l = x.l, res.r = y.r;
		res.hash = (x.hash * pw[y.r - y.l + 1] % mod + y.hash) % mod;
		res.cov = -1;
		return res;
	}
	void build(int p, int l, int r, char *s) {
		t[p].l = l, t[p].r = r;
		t[p].cov = -1;
		if (l == r) {
			t[p].hash = s[l] - '0';
			return ;
		}
		int mid = (l + r) >> 1;
		build(ls, l, mid, s);
		build(rs, mid + 1, r, s);
		t[p] = t[ls] + t[rs];
	}
	
	void make_cov(int p, int v) {
		t[p].hash = v * (pw[t[p].r - t[p].l + 1] - 1) % mod * inv_base % mod;
		t[p].hash = (t[p].hash % mod + mod) % mod;
		t[p].cov = v;
	}
	
	void push_down(int p) {
		if (~t[p].cov) {
			make_cov(ls, t[p].cov);
			make_cov(rs, t[p].cov);
			t[p].cov = -1;
		}
	}
	
	void cov(int p, int l, int r, int c) {
		if (l <= t[p].l && t[p].r <= r) {
			make_cov(p, c);
			return ;
		}
		push_down(p);
		if (l <= t[ls].r) cov(ls, l, r, c);
		if (r >= t[rs].l) cov(rs, l, r, c);
		t[p] = t[ls] + t[rs];
	}
	
	node query(int p, int l, int r) {
		if (l > r) return node();
		if (l <= t[p].l && t[p].r <= r) return t[p];
		push_down(p);
		if (r <= t[ls].r) return query(ls, l, r); 		
		if (l >= t[rs].l) return query(rs, l, r);
		return query(ls, l, r) + query(rs, l, r);
	}
} T;

int n, m;
char s[N];

void init() {
	pw[0] = 1;
	for (int i = 1; i <= 1e6 + 2; i ++) 
		pw[i] = pw[i - 1] * base % mod;
	inv_base = inv(base - 1, mod);
	T.build(1, 1, n, s);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	cin >> (s + 1);
	init();
	while (m --) {
		int op, l, r, d, c;
		cin >> op >> l >> r;
		if (op == 1) {
			cin >> c;
			T.cov(1, l, r, c);
		}
		if (op == 2) {
			cin >> d;
			auto res1 = T.query(1, l, r - d);
			auto res2 = T.query(1, l + d, r);
			if (res1.hash == res2.hash) return cout << "YES\n", 1;
			else cout << "NO\n";
		}
	}
	return 1;
}

标签:hash,cov,int,推平,LL,rs,查询,区间,return
From: https://www.cnblogs.com/maniubi/p/18516414

相关文章

  • Python——查询IP地址地理位置与设备信息
    在这个数字化时代,IP地址不仅是设备与互联网通信的桥梁,它还蕴含着丰富的信息,比如地理位置、ISP(互联网服务提供商)和设备类型等。这些信息对于网络安全、用户行为分析以及个性化服务提供等方面都具有重要意义。本文将介绍一个Python脚本,它可以帮助用户查询指定IP地址的地理位置信......
  • 58. 区间和
    题目本人一开始是这样写的:#include<iostream>usingnamespacestd;constintN=100010;intn;ints[N];intmain(){cin>>n;for(inti=1;i<=n;i++){intx;cin>>x;s[i]=s[i-1]+x;}......
  • [Python学习日记-58] 开发基础练习1——员工信息查询
    [Python学习日记-58]开发基础练习1——员工信息查询简介题目答案简介        该练习结合了函数和一些常用的模块开发了一个使用命令行交互的员工信息查询程序,可以巩固实践之前学习的内容。题目一、程序需求        现要求你写⼀个简单的员⼯信息增删......
  • 推荐一些常用的api接口,包括天气、物流、IP查询等
    AI绘画文生图API:输入文本描述,生成符合文本描述的图像。AI绘画图生图API:输入图片和文本描述,生成符合图片参考和文本描述的图像人像照片转动漫API:直接用预置的风格和人像照片URL生成对应的动漫风格图片。AI图片高清(超高分辨率)API:对目标图填充细节并输出高清图(宽、......
  • 快递鸟查询订单实例
    <?php/***@技术QQ群:可登录官网https://www.kdniao.com/右侧查看技术群号*@see:https://kdniao.com/api-track*@copyright:深圳市快金数据技术服务有限公司*ID和Key请到官网申请:https://kdniao.com/reg*即时查询接口*此接口用于向快递公司实时查询物流......
  • 智能优化揭秘——GaussDB数据库查询重写的自动挖掘与生成
    ​在数据库世界里,查询重写是提升性能的关键环节。WeTune作为一款革命性工具,能自动发现新重写规则,打破现有系统依赖人工发现重写规则的局限,大幅提升数据库查询性能。上海交通大学软件学院副院长王肇国和高斯实验室GaussDB数据库优化器专家Ethan联手开展了一场以《智能优化揭秘—......
  • 千万级数据深分页查询SQL性能优化实践
    作者:京东零售曹志飞一、系统介绍和问题描述如何在Mysql中实现上亿数据的遍历查询?先来介绍一下系统主角:关注系统,主要是维护京东用户和业务对象之前的关注关系;并对外提供各种关系查询,比如查询用户的关注商品或店铺列表,查询用户是否关注了某个商品或店铺等。但是最近接到了一个新......
  • st求区间
    点击查看代码/*台州第一深情*/#include<bits/stdc++.h>usingnamespacestd;usingi64=long;usingll=longlong;typedefpair<int,int>PII;constintN=1e5+5;intn,t;inta[N],max1[N][25],min1[N][25];//max1[i][j]表示以i结尾,长度为2^j的子序列......
  • 代码随想录算法训练营day30| 452. 用最少数量的箭引爆气球 435. 无重叠区间 763.
    学习资料:https://programmercarl.com/0452.用最少数量的箭引爆气球.html重叠区域问题最远位置问题452.用最少数量的箭引爆气球(重叠区域;按左边界排序;i区间的左边界与i-1区间的右边界比较来确定是否重叠;更新i的右边界,取i与i-1区域右边界的最小值)点击查看代码classSolution(ob......
  • C语言中实现一个包含开卡、查询内容、存钱、取钱、转账和修改密码的银行服务系统
       大家好,我是带我去滑雪,每天教你一个小技巧!   本次在C语言中实现一个包含开卡、查询内容、存钱、取钱、转账和修改密码的银行服务系统,下面开始代码实战。目录一、功能模块设计(1)开卡功能(2)查询内容(3)存钱功能(4)取钱功能(5)转账功能(6)修改密码功能二、数据结构......