树状数组+哈希+二分

#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;
}
上一篇:【操作系统】—死锁


下一篇:2021年R2移动式压力容器充装新版试题及R2移动式压力容器充装找解析