Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define ll unsigned long long
- #define mod 1000000007
- #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- using namespace std;
- const ll m = 1e9+9;
- const ll p = 131;
- ll hashString(string s) {
- ll ans = 0;
- ll p_pow = 1;
- for(ll i=0; i<s.size(); i++) {
- ans = (ans + (s[i]-'a'+1)*p_pow)%m;
- p_pow = (p_pow*p)%m;
- }
- return ans;
- }
- ll modpow(ll x, ll y) {
- ll res = 1;
- x = x % m;
- if (x == 0) return 0;
- while (y > 0)
- {
- if (y & 1)
- res = (res*x) % m;
- y = y>>1;
- x = (x*x) % m;
- }
- return res;
- }
- ll combine1(ll s1, ll s2, ll l1, ll l2) {
- // cout<<l1<<" "<<l2<<"::\n";
- ll val = modpow(p, l1);
- return ((s2*val)%mod+s1)%mod;
- }
- ll combine2(ll s1, ll s2, ll l1, ll l2) {
- ll val = modpow(p, l2);
- return ((s1*val)%mod+s2)%mod;
- }
- struct segmentTree {
- vector<ll> t1, t2;
- string s;
- ll n;
- segmentTree(ll n) {
- this->n = n;
- t1.resize(4*n);
- t2.resize(4*n);
- }
- segmentTree(string s) : segmentTree(s.size()) {
- this->s = s;
- build(1, 0, n-1);
- }
- void build(ll v, ll tl, ll tr) {
- if(tl==tr) {
- t1[v] = s[tl]-'a'+1;
- t2[v] = t1[v];
- }
- else {
- ll tm = (tl+tr)/2;
- build(v*2, tl, tm);
- build(v*2+1, tm+1, tr);
- if(tm-tl+1==0) {
- t1[v] = t1[v*2+1];
- t2[v] = t2[v*2+1];
- }
- else if(tr-tm==0) {
- t1[v] = t1[v*2];
- t2[v] = t2[v*2];
- }
- else {
- t1[v] = combine1(t1[v*2], t1[v*2+1], tm-tl+1, tr-tm);
- t2[v] = combine2(t2[v*2], t2[v*2+1], tm-tl+1, tr-tm);
- }
- }
- // cout<<tl<<" "<<tr<<" "<<t1[v]<<" "<<t2[v]<<" "<<"::\n";
- }
- void update(ll v, ll tl, ll tr, ll pos, char new_val) {
- if(tl==tr) {
- // cout<<new_val<<"::\n";
- t1[v] = (new_val-'a'+1);
- t2[v] = t1[v];
- }
- else {
- ll tm = (tl+tr)/2;
- if(pos<=tm)
- update(v*2, tl, tm, pos, new_val);
- else
- update(v*2+1, tm+1, tr, pos, new_val);
- if(tm-tl+1==0) {
- t1[v] = t1[v*2+1];
- t2[v] = t2[v*2+1];
- }
- else if(tr-tm==0) {
- t1[v] = t1[v*2];
- t2[v] = t2[v*2];
- }
- else {
- t1[v] = combine1(t1[v*2], t1[v*2+1], tm-tl+1, tr-tm);
- t2[v] = combine2(t2[v*2], t2[v*2+1], tm-tl+1, tr-tm);
- }
- }
- }
- vector<ll> sum(ll v, ll tl, ll tr, ll l, ll r) {
- if(l>r)
- return {0, 0, 0};
- if(l==tl && r==tr)
- return {t1[v], t2[v], r-l+1};
- ll tm = (tl+tr)/2;
- vector<ll> a = sum(v*2, tl, tm, l, min(r, tm));
- vector<ll> b = sum(v*2+1, tm+1, tr, max(l, tm+1), r);
- if(a[2]==0)return {
- b[0],
- b[1],
- a[2]+b[2]
- };
- else if(b[2]==0)return {
- a[0],
- a[1],
- a[2]+b[2]
- };
- else
- return {
- combine1(a[0], b[0], a[2], b[2]),
- combine2(a[1], b[1], a[2], b[2]),
- a[2]+b[2]
- };
- }
- };
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- #endif
- // fast;
- ll t = 1;
- // cin>>t;
- while(t--) {
- ll n, m;
- cin>>n>>m;
- string s; cin>>s;
- segmentTree tree(s);
- // cout<<"end::\n";
- // assert(s.size()==tree.sum(1, 0, n-1, 0, n-1)[2]);
- // cout<<hashString(s)<<" "<<tree.sum(1, 0, n-1, 0, n-1)[0]<<"::\n";
- // cout<<(hashString(s)==tree.sum(1, 0, n-1, 0, n-1)[0])<<"::\n";
- ll q, k, a, b;
- char x;
- for(ll i=0; i<m; i++) {
- cin>>q;
- if(q==1) {
- cin>>k>>x;
- // cout<<x<<"::\n";
- tree.update(1, 0, n-1, k-1, x);
- }
- else {
- cin>>a>>b;
- vector<ll> value = tree.sum(1, 0, n-1, a-1, b-1);
- assert(value[2]==b-a+1);
- if(value[0]==value[1]) {
- cout<<"YES\n";
- }
- else {
- cout<<"NO\n";
- }
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement