要求
1.修改x位置的值为y
2.查询区间l，r是否可以重排为值域上连续的一段
可以，很lxl
然后一开始思考合并区间，但是发现可以重排序，GG
然后想了特殊性质，比如求和，但是显然可以被叉
这时候我觉得要把每个数都尽量特殊化，让不同数字差异化之后和尽量不同，考虑维护一个立方和
求1到n的立方和有这样的公式
\({( \frac{n*(n+1)}{2}) }^2\)
然后就维护立方和，为了防止爆long long取模
注意
- 除2要乘2的逆元
- 维护sum要取模
然后没了
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MOD = 1e9+7;
long long sum[500100<<2],minx[500100<<2],maxx[500100<<2],a[500100],n,m;
struct ansNode{long long s,MIN,MAX;
};
void pushup(int o){sum[o]=(sum[o<<1]+sum[o<<1|1])%MOD;minx[o]=min(minx[o<<1],minx[o<<1|1]);maxx[o]=max(maxx[o<<1],maxx[o<<1|1]);
}
void build(int l,int r,int o){if(l==r){maxx[o]=a[l];minx[o]=a[l];sum[o]=a[l]%MOD*a[l]%MOD*a[l]%MOD;return;}int mid=(l+r)>>1;build(l,mid,o<<1);build(mid+1,r,o<<1|1);pushup(o);
}
void set(int L,int R,int o,int pos,int c){if(L==R){maxx[o]=c;minx[o]=c;sum[o]=c%MOD*c%MOD*c%MOD;return;}int mid=(L+R)>>1;if(pos<=mid)set(L,mid,o<<1,pos,c);elseset(mid+1,R,o<<1|1,pos,c);pushup(o);
}
ansNode query(int L,int R,int l,int r,int o){//first sum second minif(L<=l&&r<=R){return (ansNode){sum[o],minx[o],maxx[o]};}int mid=(l+r)>>1;ansNode ans;ans.s=0;ans.MIN=1e9;ans.MAX=0;if(L<=mid){ansNode midx;midx=query(L,R,l,mid,o<<1);ans.s=(ans.s+midx.s)%MOD;ans.MIN=min(ans.MIN,midx.MIN);ans.MAX=max(ans.MAX,midx.MAX);}if(R>mid){ansNode midx;midx=query(L,R,mid+1,r,o<<1|1);ans.s=(ans.s+midx.s)%MOD;ans.MIN=min(ans.MIN,midx.MIN);ans.MAX=max(ans.MAX,midx.MAX);}return ans;
}
long long sig(long long n){return ((n*(n+1)%MOD*500000004%MOD)%MOD)*((n*(n+1)%MOD*500000004%MOD)%MOD)%MOD;
}
bool isright(int L,int R){ansNode p=query(L,R,1,n,1);return (((sig(p.MAX)-sig(p.MIN-1))%MOD+MOD)%MOD==p.s);
}
int main(){scanf("%d %d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,n,1);for(int i=1;i<=m;i++){int opt,x,y;scanf("%d %d %d",&opt,&x,&y);if(opt==1)set(1,n,1,x,y);elseprintf("%s\n",(isright(x,y))?"damushen":"yuanxing");}return 0;
}