Submission #48136280

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define mz 998244353
using namespace std;
char s[1000005];
int a[1000005];
long long  bas[2],mod[2],init[2][1000006];
struct Nodes{
  long long h[2];
  int l;
  bool friend operator ==(Nodes x1,Nodes x2){
    for(int i=0;i<2;i++)
      if(x1.h[i]!=x2.h[i]) return 0;
    if(x1.l!=x2.l)
      return 0;
    return 1;
  }
  Nodes friend operator +(Nodes x1,Nodes x2){
    Nodes x3;
    x3.l=x1.l+x2.l;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
#define mz 998244353

using namespace std;

char s[1000005];
int a[1000005];
long long  bas[2],mod[2],init[2][1000006];
struct Nodes{
	long long h[2];
	int l;
	bool friend operator ==(Nodes x1,Nodes x2){
		for(int i=0;i<2;i++)
			if(x1.h[i]!=x2.h[i]) return 0;
		if(x1.l!=x2.l)
			return 0;
		return 1;
	}
	Nodes friend operator +(Nodes x1,Nodes x2){
		Nodes x3;
		x3.l=x1.l+x2.l;
		for(int i=0;i<2;i++)
			x3.h[i]=(x1.h[i]*init[i][x2.l]+x2.h[i])%mod[i];
		return x3;
	}
};
struct Node{
	int l,r,mid;
	pair<Nodes,Nodes> s;
}tre[4000005];

void build(int x,int l,int r){
	tre[x].l=l;
	tre[x].r=r;
	tre[x].mid=(l+r)/2;
	if(l==r){
		Nodes now;
		now.l=1;
		now.h[0]=now.h[1]=a[l];
		(tre[x].s).first=now;
		(tre[x].s).second=now;
	}
	else{
		build(x*2,l,tre[x].mid);
		build(x*2+1,tre[x].mid+1,r);
		(tre[x].s).first=(tre[x*2].s).first+(tre[x*2+1].s).first;
		(tre[x].s).second=(tre[x*2+1].s).second+(tre[x*2].s).second;
	}
}
void gg(int x,int p){
	if(tre[x].l==tre[x].r){
		Nodes now;
		now.l=1;
		now.h[0]=now.h[1]=a[p];
		(tre[x].s).first=now;
		(tre[x].s).second=now;
	}
	else{
		if(p<=tre[x].mid)
			gg(x*2,p);
		else
			gg(x*2+1,p);
		(tre[x].s).first=(tre[x*2].s).first+(tre[x*2+1].s).first;
		(tre[x].s).second=(tre[x*2+1].s).second+(tre[x*2].s).second;
	}
}
pair<Nodes,Nodes> ask(int x,int l,int r){
	if(tre[x].l==l && tre[x].r==r)
		return tre[x].s;
	else if(r<=tre[x].mid)
		return ask(x*2,l,r);
	else if(l>tre[x].mid)
		return ask(x*2+1,l,r);
	else{
		pair<Nodes,Nodes> t1,t2,t3;
		t1=ask(x*2,l,tre[x].mid);
		t2=ask(x*2+1,tre[x].mid+1,r);
		t3.first=t1.first+t2.first;
		t3.second=t2.second+t1.second;
		return t3;
	}
}

int main(){
	int n,q,t,l,r;
	pair<Nodes,Nodes> tp;
	scanf("%d%d",&n,&q);
	bas[0]=37;
	bas[1]=41;
	mod[0]=1000000007;
	mod[1]=998244353;
	init[0][0]=init[1][0]=1;
	for(int j=0;j<2;j++)
		for(int i=1;i<=n;i++)
			init[j][i]=(init[j][i-1]*bas[j])%mod[j];
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
		a[i]=s[i]-'a'+3;
	build(1,1,n);
	while(q--){
		scanf("%d",&t);
		if(t==1){
			scanf("%d%s",&l,s);
			a[l]=s[0]-'a'+3;
			gg(1,l);
		}
		else{
			scanf("%d%d",&l,&r);
			tp=ask(1,l,r);
			if(tp.first==tp.second)
				printf("Yes\n");
			else
				printf("No\n");
		}
	}
	return 0;
} 
/*
11
5

*/

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:87:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   87 |         scanf("%d%d",&n,&q);
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp:96:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   96 |         scanf("%s",s+1);
      |         ~~~~~^~~~~~~~~~
Main.cpp:101:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  101 |                 scanf("%d",&t);
      |                 ~~~~~^~~~~~~~~
Main.cpp:103:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  103 |                         scanf("%d%s",&l,s);
      |                         ~~~~~^~~~~~~~~~~~~
Main.cpp:108:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  108 |                         scanf("%d%d",&l,&r);
      |                         ~~~~~^~~~~~~~~~~~~~

Judge Result