CodeChef CLONEME Cloning (主席树+HASH)_综合

题意：

一个数列，q次查询，每次给你 $l_1,r_1,l_2,r_2$ ，问你将 $l_1到r_1,l_2到r_2$ 这两个区间的数排序后，如果一个位置不同或者全部相同则称为相似，对于每次询问，回到是否相似

思路：

    排序后比较，就是比较数字出现个数是否相同，如果要实现快速比较，hash+主席树即可实现。如果我们忽略是否一位不同这个条件，我们只需要比较这两段的hash值是否相同即可。
     我们想一下如果两个数列如果有一位不用，假设在 $l_1,r_1$ 中出现的是x，在 $l_2,r_2$ 中出现的是y，那么x-1之前的hash值，y+1之后的hash值，x+1到y-1之间的hash值，在两个区间里应该都完全相同。最后，我们只需要再确定下x这个位置上两区间的差值是不是等于p[x]或mod-p[x]（y同理）即可
     具体的做法就是，寻找最左边的为x，最右边为y，然后看看满不满足上面的性质即可

错误及反思：

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson l,m
#define rson m+1,r
const long long mod = 998244353;
const int N = 100010;
const int base= 100007;
long long has[N*20],p[N];
int val[N],ls[N*20],rs[N*20],n,q,cnt,root[N];void init(){cnt=0;
}int build(int l,int r){int rt=++cnt;ls[rt]=rt; rs[rt]=rt; has[rt]=0;if(l==r) return rt;int m=l+r>>1;ls[rt]=build(lson);rs[rt]=build(rson);return rt;
}int update(int pre,long long val,int pos,int l,int r){int rt=++cnt;has[rt]=(has[pre]+val)%mod; ls[rt]=ls[pre]; rs[rt]=rs[pre];if(l==r) return rt;int m=l+r>>1;if(m>=pos) ls[rt]=update(ls[pre],val,pos,lson);else rs[rt]=update(rs[pre],val,pos,rson);return rt;
}int judge1(int l1,int r1,int l2,int r2,int l,int r){if(l==r){if(1ll*(has[r1]-has[l1]+mod)%mod!=1ll*(has[r2]-has[l2]+mod)%mod)return l;return l+1;}int m=l+r>>1;if(1ll*(has[ls[r1]]-has[ls[l1]]+mod)%mod!=1ll*(has[ls[r2]]-has[ls[l2]]+mod)%mod)return judge1(ls[l1],ls[r1],ls[l2],ls[r2],lson);return judge1(rs[l1],rs[r1],rs[l2],rs[r2],rson);
}int judge2(int l1,int r1,int l2,int r2,int l,int r){if(l==r){if(1ll*(has[r1]-has[l1]+mod)%mod!=1ll*(has[r2]-has[l2]+mod)%mod)return l;return l+1;}int m=l+r>>1;if(1ll*(has[rs[r1]]-has[rs[l1]]+mod)%mod!=1ll*(has[rs[r2]]-has[rs[l2]]+mod)%mod)return judge2(rs[l1],rs[r1],rs[l2],rs[r2],rson);return judge2(ls[l1],ls[r1],ls[l2],ls[r2],lson);
}long long query(int r1,int r2,int L,int R,int l,int r){if(L<=l&&R>=r)return (has[r2]-has[r1]+mod)%mod;int m=l+r>>1;long long ans=0;if(m>=L) ans=(ans+query(ls[r1],ls[r2],L,R,lson))%mod;if(m<R) ans=(ans+query(rs[r1],rs[r2],L,R,rson))%mod;return ans;
}int main(){p[0] = 1;for(int i = 1; i < N; i ++) p[i] = (p[i-1] * base)%mod;int T;scanf("%d",&T);while(T--){init();scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) scanf("%d",&val[i]);root[0]=build(1,100000);for(int i=1;i<=n;i++)root[i]=update(root[i-1],p[val[i]],val[i],1,100000);while(q--){int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);if(1ll*(has[root[r1]]-has[root[l1-1]]+mod)%mod==1ll*(has[root[r2]]-has[root[l2-1]]+mod)%mod) {printf("YES\n");continue;}int L = judge1(root[l1-1],root[r1],root[l2-1],root[r2],1,100000);int R = judge2(root[l1-1],root[r1],root[l2-1],root[r2],1,100000);long long s1=0,s2=0;if(L+1<R){s1=query(root[l1-1],root[r1],L+1,R-1,1,100000);s2=query(root[l2-1],root[r2],L+1,R-1,1,100000);}long long t1=(query(root[l1-1],root[r1],L,L,1,100000)-query(root[l2-1],root[r2],L,L,1,100000)+mod)%mod;long long t2=(query(root[l1-1],root[r1],R,R,1,100000)-query(root[l2-1],root[r2],R,R,1,100000)+mod)%mod;if((t1==p[L]||mod-t1==p[L])&&(t2==p[R]||mod-t2==p[R])&&s1==s2&&s1==0)printf("YES\n");else printf("NO\n");}}
}