题解 P6688 【可重集】
Piwry
·
·
题解
先提前码好题解等开放通道了交
话说今天讲课时有听到一道类似的题目
然后底下就有人提到 "luogu月赛"，于是我就去月赛翻了翻，然后找到了这道题qwq
解析
题目相当于是询问两个数列区间排序后对应的相邻元素的差是否完全相等，并且支持单点修改
想要比较区间是否相等，有一个思路就是将所有元素分别乘一个 \text{base} 值的幂并求和，用哈希比较。一般来说 \text{base} 的幂是按元素在序列内位置来决定的
但题目还要求我们将这些元素排序。这时就可以想到在 \text{base} 的幂上做手脚；具体来说，因为此时元素在序列内的位置不再重要，我们不按元素在序列内位置，而是按元素的值来决定 \text{base} 的幂
例如设 \text{base} 为 3，则序列 1, 1, 4, 5, 1, 4 的哈希值就为 3^1+3^1+3^4+3^5+3^1+3^4
至于 "相邻元素的差"，我们再维护一个区间最小值，在比较前给最小值较小的区间的哈希值乘上一个补偿值，使得它们哈希值式子的最小幂次相等，这样就可以比较了
CODE
代码方面没什么好说的，标准线段树就行了
另外注意有几个点有点卡常，可以每次查询一次性查区间哈希和最小值，节省些常数
```cpp
#include <cstdio>
#include <iostream>
using std::min;
using std::pair;
using std::swap;
typedef pair<int, int> pad;
const int MAXN =1e6+50;
const int X =2, M =1e9+7;
/*------------------------------Seg------------------------------*/
int mn[MAXN<<2], sum[MAXN<<2], pow[MAXN];
int N =1;
inline void pushup(int x){
mn[x] =min(mn[x<<1], mn[(x<<1)|1]);
sum[x] =(sum[x<<1]+sum[(x<<1)|1])%M;
}
void modify(int pos, int val, int x =1, int nl =1, int nr =N){
if(nl == nr){
mn[x] =val;
sum[x] =pow[val];
return;
}
int mid =(nl+nr)>>1;
if(pos <= mid) modify(pos, val, x<<1, nl, mid);
else modify(pos, val, (x<<1)|1, mid+1, nr);
pushup(x);
}
/*first -> mn, second -> sum*/
pad query(int l, int r, int x =1, int nl =1, int nr =N){
if(l == nl && r == nr)
return pad(mn[x], sum[x]);
int mid =(nl+nr)>>1;
if(r <= mid) return query(l, r, x<<1, nl, mid);
else if(l >= mid+1) return query(l, r, (x<<1)|1, mid+1, nr);
else{
pad ret1 =query(l, mid, x<<1, nl, mid),
ret2 =query(mid+1, r, (x<<1)|1, mid+1, nr);
(ret1.second +=ret2.second) %=M;
ret1.first =min(ret1.first, ret2.first);
return ret1;
}
}
/*------------------------------Main------------------------------*/
inline int read(){
int x =0; char c =getchar();
while(c < '0' || c > '9') c =getchar();
while(c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (48^c), c =getchar();
return x;
}
inline void prepow(){
pow[0] =1;
for(int i =1; i < MAXN; ++i)
pow[i] =1ll*pow[i-1]*X%M;
}
int main(){
prepow();
int n =read(), m =read();
while(N < n) N <<=1;
for(int i =N; i < N+n; ++i)
mn[i] =read(), sum[i] =pow[mn[i]];
for(int i =N-1; i >= 1; --i)
pushup(i);
for(int i =0; i < m; ++i){
int op =read();
if(op == 0){
int x =read(), y =read();
modify(x, y);
}
else{
int l1 =read(), r1 =read(), l2 =read(), r2 =read();
pad q1 =query(l1, r1), q2 =query(l2, r2);
if(q1.first > q2.first)
swap(q1, q2);
if(1ll*q1.second*pow[q2.first-q1.first]%M == q2.second)
puts("YES");
else
puts("NO");
}
}
}
```