简要题意
给出一个长度为 \(n\) 的序列 \(a\)。有 \(m\) 个操作，支持：
1 x y将 \(a_x\) 修改为 \(y\)。2 l r判断 \(a[l:r]\) 排序后是否为公差为 \(1\) 的连续数列（即全体自然数数列的子串）。如果是输出damushen，否则输出yuanxing。
\(1 \leq n,m \leq 5 \times 10^5,1 \leq a_i \leq 2.5\times10^7,1 \leq x,y \leq n,1 \leq l \leq r \leq n\)。时间限制 \(2\text{s}\)，空间限制 \(125\text{MB}\)。
思路
本题属于一类另类哈希的应用。
这道题如果使用普通维护策略可以用树状数组套一个可持久化线段树维护区间不同元素个数。然后用一个普通线段树维护区间最大最小值。时间复杂度 \(O(m\log^2n)\)，空间复杂度 \(O(m\log n)\)。不可过。
我们还有一种方法。就是看成字串匹配。用哈希做。而且本题还有特殊性质，可以快速维护多类哈希值。然后用最小最大值定界。
本来是维护了区间和区间平方和区间立方和区间异或和的。但是这样子被卡空间了。后来我只维护区间和区间平方和就过了。
时间复杂度 \(O(n+m\log n)\)。
代码
#include<bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;
int n,m;
unsigned int valuemax;
struct node{
int mint,maxt;
unsigned int sumt,sqsumt;
node(unsigned int v=0){
mint=maxt=sumt=v;
sqsumt=v*v;
}
node operator+(const node &x) const {
node zbz;
zbz.mint=min(mint,x.mint);
zbz.maxt=max(maxt,x.maxt);
zbz.sumt=sumt+x.sumt;
zbz.sqsumt=sqsumt+x.sqsumt;
return zbz;
}
};
const int N = 5e5+5;
node t[N<<2];
inline void pushup(int i){
t[i]=t[ls]+t[rs];
}
inline void build(int i,int l,int r){
if(l==r){
unsigned int v;cin>>v;
valuemax=max(valuemax,v);
t[i]=node(v);return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
void update(int p,int v,int i,int l,int r){
if(l==r){
t[i]=node(v);return;
}
if(p<=mid) update(p,v,ls,l,mid);
else update(p,v,rs,mid+1,r);
pushup(i);
}
node query(int ql,int qr,int i,int l,int r){
if(ql<=l&&r<=qr) return t[i];
if(ql<=mid&&qr>mid) return query(ql,qr,ls,l,mid)+query(ql,qr,rs,mid+1,r);
if(ql<=mid) return query(ql,qr,ls,l,mid);
if(qr>mid) return query(ql,qr,rs,mid+1,r);
}
const int V = 2.5e7+5;
unsigned int sqsumt[V];
inline unsigned sumt(unsigned i){
return ((1ull+i)*i)/2;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
build(1,1,n);
assert(valuemax<=(2.5e7));
for(unsigned int i=1;i<=valuemax;i++){
sqsumt[i]=sqsumt[i-1]+i*i;
}
while(m--){
int op,x,y;
cin>>op>>x>>y;
if(op==1) update(x,y,1,1,n);
else{
node ans=query(x,y,1,1,n);
int l=ans.mint,r=ans.maxt;
if(ans.sqsumt==(sqsumt[r]-sqsumt[l-1])){
if(ans.sumt==(sumt(r)-sumt(l-1))){
cout<<"damushen\n";
}
else cout<<"yuanxing\n";
}
else cout<<"yuanxing\n";
}
}
return 0;
}