讲解 P10785 [NOI2024] 集合。

首先要注意到两个区间等价的充要条件，然后发现单调性，可以用双指针提前预处理每个左端点能延申到的最远右端点，使用双哈希快速判断。

思路：

容易发现，区间 \([l,r]\) 中 \(A\) 与 \(B\) 等价的充分必要条为：

• 两个序列中所有元素对于在区间 \([l,r]\) 内的出现集合组成的集合相等。

• 这样才可以使得存在一种对应的映射方案使得等价。

考虑哈希判定。

设 \(S_i\) 表示 \(i\) 出现的位置的集合，则设 \(\operatorname{Hash}(S_x) = \sum\limits_{i \in S_x} base^i\)，\(\operatorname{Hash}(A/B) = \sum\limits_{i=1}^m \operatorname{Hash}(S_i)\)。

固定左端点 \(l\) 时，容易发现 \(r\) 具有单调性，考虑求出 \(len_l\) 表示以 \(l\) 为左端点的最长等价区间，使用双指针算法；

设当前加入的数为 \(a_i\)，则重新计算下 \(\operatorname{Hash}(S_{a_i})\) 即可，删除同理。

因为当前是单哈希，且基本都是加法哈希，可以双哈希 \(\operatorname{Hash}(S_i)\) 稳固一下。

时间复杂度为 \(O(N+Q)\)。

完整代码：

<code>#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

#define For(i,l,r) for(int i=l;i<=r;i++)

#define _For(i,l,r) for(int i=r;i>=l;i--)

using namespace std;

typedef long double lb;

typedef double db;

typedef unsigned long long ull;

typedef long long ll;

bool Begin;

const ll N=2e5+10,M=6e5+10;

const ull base=127;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

mt19937_64 R(time(0));

ull h1,h2;

int n,m,q,p,l,r;

int len[N],a[N][3],b[N][3];

ull f[N],s1[M],s2[M];

inline ull Hash(ull x){

return x*f[x%(N-1)+1];

}

inline void insert1(int x,int id){

h1-=Hash(s1[x]);

s1[x]+=f[id];

h1+=Hash(s1[x]);

}

inline void insert2(int x,int id){

h2-=Hash(s2[x]);

s2[x]+=f[id];

h2+=Hash(s2[x]);

}

inline void del1(int x,int id){

h1-=Hash(s1[x]);

s1[x]-=f[id];

h1+=Hash(s1[x]);

}

inline void del2(int x,int id){

h2-=Hash(s2[x]);

s2[x]-=f[id];

h2+=Hash(s2[x]);

}

inline void insert(int x){

For(i,0,2){

insert1(a[x][i],x);

insert2(b[x][i],x);

}

}

inline void del(int x){

For(i,0,2){

del1(a[x][i],x);

del2(b[x][i],x);

}

}

bool End;

int main(){

//open("A.in","A.out");

n=read(),m=read(),q=read();

f[0]=1;

For(i,1,N-1)

f[i]=f[i-1]*base;

For(i,1,n)

For(j,0,2)

a[i][j]=read();

For(i,1,n)

For(j,0,2)

b[i][j]=read();

for(int l=1,r=0;l<=n;){

while(r<l){

++r;

insert(r);

}

while(r<=n&&h1==h2){

r++;

insert(r);

}

del(r--);

len[l]=r;

del(l++);

}

while(q--){

l=read(),r=read();

if(r>len[l])

puts("No");

else

puts("Yes");

}

cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";

return 0;

}