周期串查询

周期串查询（哈希加线段树或灵性做法）

题目大意

有一个串只包含数字字符。串的长度为n，下标从1开始。
有两种操作方式：
1 l r c (1≤l≤r≤n, c是数字字符)，表示将l到r这一段的字符全部改成c字符；
2 l r d (1≤l≤r≤n, 1≤d≤r-l+1)，表示询问l到r这一段区间内的子串是否是以d为周期的串。
字符串s是以x (1≤x≤|s|),为周期的串的条件是：对于所有的 i从1到|s|-x， si = si + x 都成立。

输入格式

单组测试数据。

第一行有两个整数n, m ,k (1≤n≤10^5, 1≤m+k≤10^5)，表示字符串长度和修改次数和询问次数。
第二行给出原始的串包含n位数字字符。
接下来m+k行，每行一个操作。
有两种形式：
1 l r с (1≤l≤r≤n, c是数字字符)；
2 l r d (1≤l≤r≤n, 1≤d≤r-l+1)。

输出格式

对于每一个询问，如果该段子串是以d为周期的，输出YES，否则输出NO。

样例

样例输入

样例输出

NO
YES

算法分析

线段树区间修改区间查询线段树的节点存子节点中最大值
其实这个线段树主要是优化的作用如果要求的这个区间中最大值与最小值相等那么肯定就是一样的最后以d为周期查找一下就好
关于瞎搞的话………… memset 与 memcpy

Code

Code1


// 比下面那种算法慢 但是很锻炼码力（自闭症患者慎入）
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
char s[maxn];
int v[maxn];
int cnt;
int cur[maxn];

struct node{
	int rt,l,r,Max,Min,lazy;
}a[maxn << 2];

void build(int rt,int l,int r){
	a[rt].l = l;a[rt].r = r;
	if(a[rt].l == a[rt].r){a[rt].Max = a[rt].Min = v[l];return;}
	int mid = l + r >> 1;
	build(rt << 1,l,mid);
	build(rt << 1 | 1,mid + 1,r);
	a[rt].Max = max(a[rt << 1].Max,a[rt << 1 | 1].Max);
	a[rt].Min = min(a[rt << 1].Min,a[rt << 1 | 1].Min);
}

void updata(int rt,int k){
	a[rt].Max = a[rt].Min = k;
	a[rt].lazy = k;
}

void pushdown(int rt){
	updata(rt << 1,a[rt].lazy);
	updata(rt << 1 | 1,a[rt].lazy);
	a[rt].lazy = 0;
}

void change(int rt,int l,int r,int k){
	if(a[rt].l >= l && a[rt].r <= r){
		a[rt].Max = a[rt].Min = k;
		a[rt].lazy = k;
		return;
	}
	if(a[rt].lazy)pushdown(rt);
	int mid = a[rt].l + a[rt].r >> 1;
	if(l <= mid)change(rt << 1,l,r,k);
	if(r > mid)change(rt << 1 | 1,l,r,k);
	a[rt].Max = max(a[rt << 1].Max,a[rt << 1 | 1].Max);
	a[rt].Min = min(a[rt << 1].Min,a[rt << 1 | 1].Min);
}

int askmax(int rt,int l,int r){
	if(a[rt].l >= l && a[rt].r <= r){
		if(a[rt].lazy)pushdown(rt);
		return a[rt].Max;
	}
	if(a[rt].lazy)pushdown(rt);
	int mid = a[rt].l + a[rt].r >> 1;
	if(r <= mid)return askmax(rt << 1,l,r);
	if(l > mid)return askmax(rt << 1 | 1,l,r);
	return max(askmax(rt << 1,l,r),askmax(rt << 1 | 1,l,r));
}

int askmin(int rt,int l,int r){
	if(a[rt].l >= l && a[rt].r <= r){
		if(a[rt].lazy)pushdown(rt);
		return a[rt].Min;
	}
	if(a[rt].lazy)pushdown(rt);
	int mid = a[rt].l + a[rt].r >> 1;
	if(r <= mid)return askmin(rt << 1,l,r);
	if(l > mid)return askmin(rt << 1 | 1,l,r);
	return min(askmin(rt << 1,l,r),askmin(rt << 1 | 1,l,r));
}

void first(int rt,int l,int r,int k){
	if(a[rt].lazy)pushdown(rt);
	if(a[rt].l == a[rt].r){cur[++cnt] = a[rt].Max;return;}
	int mid = a[rt].l + a[rt].r >> 1;
	if(l <= mid)first(rt << 1,l,r,k);
	if(r > mid)first(rt << 1 | 1,l,r,k);
}

bool check(int k){
	if(k > cnt)return 0;
	for(int i = 1;i <= cnt - k;++i)if(cur[i] != cur[i + k])return 0;
	return 1;
}

int main(){
	//freopen("Data.in","r",stdin);
	//freopen("c.out","w",stdout);
	int n,m,K;scanf("%d%d%d",&n,&m,&K);
	scanf("%s",s+1);
	for(int i = 1;i <= n;++i)v[i] = s[i] - '0';
	build(1,1,n);
	for(int i = 1;i <= m + K;++i){
		int flag,l,r,k;scanf("%d%d%d%d",&flag,&l,&r,&k);
		if(flag == 1)change(1,l,r,k);
		if(flag == 2){
			cnt = 0;
			first(1,l,r,k);
			if(askmax(1,l,r) == askmin(1,l,r)){
				printf("YES
");
				continue;
			}
			if(check(k))printf("YES
");
			else printf("NO
");
		}
	}
	return 0;
}

Code2

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
char s[maxn];
int a[maxn],h[maxn];

int main(){
	int n,m,k;scanf("%d%d%d",&n,&m,&k);
	scanf("%s",s+1);
	k += m;
	while(k--){
		int flag,l,r,k;scanf("%d%d%d%d",&flag,&l,&r,&k);
		if(flag == 1)memset(s + l,k + '0',r - l + 1);
		if(flag == 2 && memcmp(s + l,s + l + k,r - l - k + 1))printf("NO
");
		else if(flag == 2)printf("YES
");
	}
	return 0;
}

如初见与初见