树状数组+哈希+二分

超、凢脫俗 2022-09-10 13:17 185阅读 0赞

#include <bits/stdc++.h>
    using namespace std;
    #define ull unsigned long long
    #define in __int128_t
    #define lowbits(x) x&-x
    
    const int X = 133331;
    const int N = 1e5 + 10;
    in mod;
    
    string s;
    ull f[N], c[N];
    int n, m;
    
    inline void add(int x, ull y){ for(;x<=n;x+=lowbits(x)) c[x]+=y;}
    inline ull ask(int x) { ull sum=0;for(;x;x-=lowbits(x)) sum+=c[x];return sum;}
    inline ull get(int l, int r) {  return (ask(r) - ask(l-1) + mod);}
    
    void init() { f[0] = 1; for(int i=1;i<N;i++)f[i]=f[i-1]*X;}
    
    bool comp(int l1,int r1,int l2,int r2)  
    { 
    	return (get(l1,r1)*f[l2-l1] == get(l2,r2)); // 略有不同
    }
    
    bool dfs(int l1, int r1, int l2, int r2) { 
        if (l1 == r1) return true;
        int mid1 = (l1 + r1) >> 1;
        int mid2 = (l2 + r2) >> 1;
    
        bool f1 = comp(l1, mid1, l2, mid2);
        bool f2 = comp(mid1 + 1, r1, mid2 + 1, r2);
        if (!f1 && !f2) return false;
        if (!f1) return dfs(l1, mid1, l2, mid2);
        else return dfs(mid1 + 1, r1, mid2 + 1, r2);
    }
    
    int main()
    { 
        mod = 1;
        ull a = 2;
        int b = 64;
        while(b)
        { 
            if(b&1) mod = a * mod;
            a = a * a;
            b >>= 1;
        }
    
    	init();
    	
    	cin >> n >> m >> s;
    	
    	s = " " + s;
    	
    	for(int i=1; i<=n; i++) add(i,f[i]*s[i]);
    	
    	bool flag = true;
        
        while(m--)
        { 
            int op; 
            cin >> op;
            if(op==1)
            {  
                int pos;
                char tmp; 
                cin >> pos >> tmp;
                ull p = (tmp - s[pos] + mod);
                add(pos, p*f[pos]);
                s[pos] = tmp;
            }
            else
            { 
                bool f = false;
                int l1, r1, l2, r2;
                cin >> l1 >> r1 >> l2 >> r2;
                if(abs(r1-l1) != abs(r2-l2)) goto gotoflag;
                if(l1 > l2) swap(l1,l2), swap(r1,r2);
            	if(comp(l1,r1,l2,r2)) {  
                    f = true;goto gotoflag;
                }
                if (dfs(l1, r1, l2, r2)) f = true;
                
            gotoflag:   
                
                if(f) cout << "YES\n";
                else cout << "NO\n";
            } 
            
        }
    	
    	return 0;
    }