题解 P3792 【由乃与大母神原型和偶像崇拜】

首先我先轻轻的斥责一下这题卡一个 $nlog(n)$ 算法常数的暴行…… 容易发现一段区间合法当且仅当一段区间的 $Max$ 减去一段区间的 $Min$ 等于区间的长度，但是只满足这个我们是没法保证他一定是对的……因为可能存在重复的数字 考虑一段区间如果每个数字的 $next$ 即下一次出现的位置都 $>r$ 则一定没有重复的数字，这是经典套路【划掉 那么我们线段树维护一下区间每一个数字的 $next$ 的最小值就行辣 注意到需要动态修改前驱和后继，所以我们需要大力对每个元素开一个平衡树维护出所有元素他的位置，这样就能快速查询前驱和后继了，当然需要离散权值。 我当时考试的时候大力写了一发然后交上去 $MLE$ 了，非常绝望，可能是 STL 的锅吧……但是注意到这个算法是能保证正确性是完全正确的。 虽然我后来交的也是 hash 过掉的本题但是只维护和，平方和是肯定不行的，这个概率其实撞上的还是挺大的，毕竟是一坨数字，为了保证正确其实可以维护一坨数字的异或和等等等等 放一个第一个做法的代码供对此算法感兴趣的同学学习借鉴,当然，并不能过，只有 70pts ```cpp #include <set> #include <map> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; const int inf = 1e9+7; const int N = 500000+5; const int M = 1048576+5; inline int read() { int x=0,f=1;char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();} while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();} return x*f; } int Max[M], Min[M], tr[M], nxt[M], last[M]; int a[N]; map <int,int> mp; set <int> s[M]; inline void build(int k,int l,int r) { if(l==r) { Max[k] = Min[k] = a[l]; tr[k] = nxt[l]; return; } int mid = (l+r) >> 1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); Max[k] = max(Max[k<<1], Max[k<<1|1]); Min[k] = min(Min[k<<1], Min[k<<1|1]); tr[k] = min(tr[k<<1], tr[k<<1|1]); } inline void change(int k,int l,int r,int pos,int val,int _temp) { if(l==r) { Max[k] = Min[k] = val; tr[k] = _temp; return; } int mid = (l+r) >> 1; if(pos <= mid) change(k<<1,l,mid,pos,val,_temp); else change(k<<1|1,mid+1,r,pos,val,_temp); Max[k] = max(Max[k<<1], Max[k<<1|1]); Min[k] = min(Min[k<<1], Min[k<<1|1]); tr[k] = min(tr[k<<1], tr[k<<1|1]); } void ask(int k,int l,int r,int x,int y,int &temp1,int &temp2,int &temp3) { // Max Min nxt_Min if(x <= l && r <= y) { if(temp1 < Max[k]) temp1 = Max[k]; if(temp2 > Min[k]) temp2 = Min[k]; if(temp3 > tr[k]) temp3 = tr[k]; return; } int mid = (l+r) >> 1; if(x <= mid) ask(k<<1, l, mid, x, y, temp1, temp2, temp3); if(y > mid) ask(k<<1|1, mid+1 , r, x, y, temp1, temp2, temp3); } int cnt; int main() { // freopen("tt.in","r",stdin); int n = read(), m = read(); for(int i=1;i<=n;++i) a[i] = read(); for(int i=n;i>=1;--i) { if(!mp[a[i]]) { mp[a[i]] = ++cnt; last[cnt] = n + 1; s[cnt].insert(0); s[cnt].insert(n+1); } nxt[i] = last[mp[a[i]]]; last[mp[a[i]]] = i; } for(int i=1;i<=n;++i) s[mp[a[i]]].insert(i); build(1,1,n); set <int> :: iterator it; for(int i=1;i<=m;++i) { int opt = read(); if(opt == 1) { int x = read(), y = read(), temp = mp[a[x]], temp2, temp3; s[temp].erase(s[temp].find(x)); it = s[temp].upper_bound(x); temp3 = (*it); it --; temp2 = (*it); // temp2 x temp3 if(temp2 > 0) change(1,1,n,temp2,a[temp2],temp3); a[x] = y; if(!mp[y]) { mp[y] = ++cnt; s[cnt].insert(0); s[cnt].insert(n+1); } temp = mp[y]; it = s[temp].upper_bound(x); temp3 = (*it); it --; temp2 = (*it); // temp2 x temp3 if(temp2 > 0) change(1,1,n,temp2,a[temp2],x); s[temp].insert(x); change(1,1,n,x,a[x], temp3); } else { int temp1 = 0, temp2 = inf, temp3 = inf; int x = read(), y = read(); ask(1,1,n,x,y,temp1,temp2,temp3); if(temp1 - temp2 + 1 == y - x + 1 && temp3 > y) puts("damushen"); else puts("yuanxing"); } } } ```