ToB企服应用市场:ToB评测及商务社交产业平台

标题: P10785 [NOI2024] 集合 [打印本页]

作者: 金歌 时间: 2024-8-28 15:14
标题: 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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)