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#define Add(x,y) (x+y>=mod)?(x+y-mod)x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#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=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'9'){        if(c=='-')          f=-1;        c=getchar();    }    while(c>='0'&&c