11.8
P6688 可重集
考虑给每个序列生成一个特征值，对于在 \(a\) 序列上的区间 \([l, r]\)，记他的区间特征值为\(sum\)：
\[\sum_{i = l}^{r}{X ^ {a_i}}
\]
对于两个序列，令他们的特征值从小到大分别为 \(sum1\) 和 \(sum2\)，比对时将特征值小的通过乘上 \(X^{两个序列的最小值之差}\) 来补齐，判断是否相等即可。
注意到单点修改，区间查询，所以可以用线段树来维护区间最小值和 \(sum\)，单模哈希就能过。
#include
using namespace std;
#define int long long
const int N = 1e6 + 5;
const int Base = 13331;
const int mod = 1e9 + 7;
int n, a[N], pw[N], q;
struct SegmentTree
{int mn[N << 2], sum[N << 2];void pushup(int u){mn[u] = min(mn[u * 2], mn[u * 2 + 1]);sum[u] = sum[u * 2] + sum[u * 2 + 1];sum[u] = (sum[u] >= mod) ? sum[u] - mod : sum[u];}void build(int u, int l, int r){if(l == r){mn[u] = a[l], sum[u] = pw[a[l]];return ;}int mid = l + r >> 1;build(u * 2, l, mid); build(u * 2 + 1, mid + 1, r);pushup(u);}void update(int u, int l, int r, int k, int val){if(l == r){mn[u] = val, sum[u] = pw[val];return ;}int mid = l + r >> 1;if(k <= mid) update(u * 2, l, mid, k, val);else update(u * 2 + 1, mid + 1, r, k, val);pushup(u);}pair query(int u, int l, int r, int L, int R){if(l >= L && r <= R) return make_pair(mn[u], sum[u]);int mid = l + r >> 1; pair res = {1e9, 0};if(L <= mid){pair Q = query(u * 2, l, mid, L, R);res = {min(res.first, Q.first), (res.second + Q.second) % mod};}if(R > mid){pair Q = query(u * 2 + 1, mid + 1, r, L, R);res = {min(res.first, Q.first), (res.second + Q.second) % mod};}return res;}
}tr;
void makePow()
{pw[0] = 1;for(int i = 1; i < N; i ++) pw[i] = (pw[i - 1] * Base) % mod;
}
signed main()
{scanf("%lld %lld", &n, &q);makePow();for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);tr.build(1, 1, n);while(q --){int op; scanf("%lld", &op);if(op == 0){int x, y; scanf("%lld %lld", &x, &y);a[x] = y;tr.update(1, 1, n, x, y);}if(op == 1){int l1, r1, l2, r2; scanf("%lld %lld %lld %lld", &l1, &r1, &l2, &r2);pair Q1 = tr.query(1, 1, n, l1, r1), Q2 = tr.query(1, 1, n, l2, r2);if(Q1.first > Q2.first) swap(Q1, Q2);// cout << Q1.second << " " << Q2.second << endl;if((Q1.second * pw[Q2.first - Q1.first]) % mod == Q2.second) printf("YES\n");else printf("NO\n");}}
}