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

原题链接

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

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

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

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

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

#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(u<<1,x,v);
else modify(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]<-y
int 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[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;
}

原文地址：https://blog.csdn.net/summ1ts/article/details/142728701

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！