题目
给你一个长为 (n) 的序列 (a)
每次两个操作:
修改 (x) 位置的值为 (y)
查询区间 ([l,r]) 是否可以重排为值域上连续的一段
分析
直接维护区间最大值和最小值,
若(sum p^x=sum p^{a_i}),
那么可以重排,此题卡常,要用zkw线段树
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=25000011,M=500011,mod=998244353;
int n,s[N],c[M],a[M],m;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline signed mo(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline signed min(int a,int b){return a<b?a:b;}
inline signed max(int a,int b){return a>b?a:b;}
struct zkw{
int w[2][M<<2],bas;
inline void build(int n){
for (bas=1;(bas<<=1)<n+2;);
for (rr int i=1;i<bas*2;++i) w[0][i]=N;
for (rr int i=bas+1;i<=bas+n;++i)
w[0][i]=a[i-bas],w[1][i]=a[i-bas];
for (rr int i=bas;i;--i)
w[0][i]=min(w[0][i<<1],w[0][i<<1|1]),
w[1][i]=max(w[1][i<<1],w[1][i<<1|1]);
}
inline void update(int x){
for (w[0][x+bas]=a[x],x+=bas,x>>=1;x;x>>=1)
w[0][x]=min(w[0][x<<1],w[0][x<<1|1]);
for (w[1][x+bas]=a[x],x+=bas,x>>=1;x;x>>=1)
w[1][x]=max(w[1][x<<1],w[1][x<<1|1]);
}
inline void query(int x,int y,int &mn,int &mx){
for (x+=bas-1,y+=bas+1;x^y^1;x>>=1,y>>=1){
if (!(x&1)) mn=min(mn,w[0][x^1]);
if (!(x&1)) mx=max(mx,w[1][x^1]);
if (y&1) mn=min(mn,w[0][y^1]);
if (y&1) mx=max(mx,w[1][y^1]);
}
}
}Tre;
inline void Update(int x,int y){
for (;x<=n;x+=-x&x) c[x]=mo(c[x],y);
}
inline signed Query(int x){
rr int ans=0;
for (;x;x-=-x&x) ans=mo(ans,c[x]);
return ans;
}
signed main(){
n=iut(),m=iut(),s[0]=1;
for (rr int i=1;i<N;++i) s[i]=331ll*s[i-1]%mod;
for (rr int i=1;i<N;++i) s[i]=mo(s[i-1],s[i]);
for (rr int i=1;i<=n;++i) a[i]=iut()+1;
for (rr int i=1;i<=n;++i) c[i]=mo(c[i-1],mo(s[a[i]],mod-s[a[i]-1]));
for (rr int i=n;i;--i) c[i]=mo(c[i],mod-c[i&(i-1)]);
Tre.build(n);
for (rr int i=1;i<=m;++i){
rr int opt=iut(),x=iut(),y=iut();
if (opt==1){
++y,Update(x,mo(mo(s[y],mod-s[y-1]),mod-mo(s[a[x]-1],mod-s[a[x]]))),
a[x]=y,Tre.update(x);
}else{
rr int mn=N,mx=0; Tre.query(x,y,mn,mx);
puts((mo(s[mx],Query(x-1))==mo(Query(y),s[mn-1]))?"damushen":"yuanxing");
}
}
return 0;
}
Sight Care is a natural supplement designed to improve eyesight and reduce dark blindness. With its potent blend of ingredients. https://sightcarebuynow.us/
SightCare supports overall eye health, enhances vision, and protects against oxidative stress. Take control of your eye health and enjoy the benefits of clear and vibrant eyesight with Sight Care. https://sightcarebuynow.us/