P3792 由乃与大母神原型和偶像崇拜

原题链接

不愧是 lxl，硬控我一个半小时。最终也是极限卡过了。

这道题题解区有许多用哈希思想做的，可能实现方式略有不同。而我还是喜欢写保证了正确性的做法。具体说，就是用线段树维护区间最大最小值，因为是一段连续的数，区间极差肯定与区间长度相等。再就是确保区间内无重复数字。

所以问题关键是如何判断区间内是否有重复数字。这里有一个常用的 trick，我们可以维护每个数前驱（一个数的前驱就是与它相等的最近的那个位置），然后只需要查询区间中前驱最大值即可。若前驱最大值在左端点外，则区间内无重复数字，你可以画图手玩一下，原因其实很好理解。

但是又有新问题了，因为题中带单点修改，所以我们还要考虑修改对前驱的影响。自然可以想到先离散化，然后对每个数都建一个 set，维护这个数出现的所有下标，接下来就很好维护了。

大常数 $5e5,O(nlogn)$，lxl 只给 $1s$。不过勉强还能过，下面是我的最劣解代码qwq

update:代码有误TAT，数据原来这么水，错的代码都能放过。。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}
int n,m,a[N],tot,pre[N];
set<int> s[N];set<int>::iterator it;map<int,int> mp;
struct node{int l,r,Mn,Mx,mx;
}tr[N*4];
struct question{int opt,x,y;
}q[N];
void pushup(int u){tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);tr[u].Mx=max(tr[u<<1].Mx,tr[u<<1|1].Mx);tr[u].Mn=min(tr[u<<1].Mn,tr[u<<1|1].Mn);
}
void build(int u,int l,int r){if(l==r) tr[u]={l,r,a[l],a[l],pre[l]};else{tr[u].l=l,tr[u].r=r;int mid=(l+r)>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}
}
void modify(int u,int x,int v){if(tr[u].l==x&&tr[u].r==x) tr[u].mx=v;else{int mid=(tr[u].l+tr[u].r)>>1;if(x<=mid) modify(u<<1,x,v);else modify(u<<1|1,x,v);pushup(u);}
}
void modify_val(int u,int x,int v){if(tr[u].l==x&&tr[u].r==x) tr[u].Mn=tr[u].Mx=v;else{int mid=(tr[u].l+tr[u].r)>>1;if(x<=mid) modify_val(u<<1,x,v);//这里原来是modifyelse modify_val(u<<1|1,x,v);//pushup(u);}
}
int query(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mx;int mid=(tr[u].l+tr[u].r)>>1,ans=0;if(l<=mid) ans=max(ans,query(u<<1,l,r));if(r>mid) ans=max(ans,query(u<<1|1,l,r));return ans;
}
int query_mx(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r) return tr[u].Mx;int mid=(tr[u].l+tr[u].r)>>1,ans=0;if(l<=mid) ans=max(ans,query_mx(u<<1,l,r));if(r>mid) ans=max(ans,query_mx(u<<1|1,l,r));return ans;	
}
int query_mn(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r) return tr[u].Mn;int mid=(tr[u].l+tr[u].r)>>1,ans=1e9;if(l<=mid) ans=min(ans,query_mn(u<<1,l,r));if(r>mid) ans=min(ans,query_mn(u<<1|1,l,r));return ans;	
}
void Modify(int i,int y){//a[i]<-yint x=mp[a[i]];it=s[x].find(i);it++;if(it!=s[x].end()){pre[*it]=pre[i];modify(1,*it,pre[*it]);}it--;s[x].erase(it);a[i]=y;x=mp[y],s[x].insert(i);it=s[x].find(i);it--;pre[i]=*it;it++,it++;if(it!=s[x].end()){pre[*it]=i;modify(1,*it,pre[*it]);}modify(1,i,pre[i]),modify_val(1,i,a[i]);
}
int main(){n=read(),m=read();for(int i=1;i<=n;i++){a[i]=read();if(!mp[a[i]]) mp[a[i]]=++tot,s[tot].insert(0);pre[i]=*(--s[mp[a[i]]].end());s[mp[a[i]]].insert(i);}build(1,1,n);for(int i=1;i<=m;i++){int opt=read(),x=read(),y=read();if(opt==1){if(!mp[y]) mp[y]=++tot,s[mp[y]].insert(0);//这里原来是s[y].insert(0)Modify(x,y);}else{int res=query(1,x,y),mn=query_mn(1,x,y),mx=query_mx(1,x,y);if(mx-mn==y-x&&res<x) puts("damushen");else puts("yuanxing");}}return 0;
}