给你一个序列a
每次两个操作：
1.修改x位置的值为y
2.查询区间l，r是否可以重排为值域上连续的一段
输入格式：
第一行两个数n，m
第二行n个数表示a[i]
后面m行每行三个数opt x y，或者opt l r，代表操作
输出格式：
如果可以，输出“damushen”
否则输出“yuanxing”
5 5 1 2 3 4 5 2 1 5 2 2 3 2 3 3 1 3 6 2 3 5
damushen damushen damushen damushen
对于30%的数据，n,m<=500
对于60%的数据，n,m<=100000
对于100%的数据，n,m<=500000
值域1e9
2s
这道题主要是要知道一个用平方和来体现哈希的思想。
那就是在区间中最小值到最大值的平方之和是唯一的（立方和一样）。
于是我们就可以用线段树保存区间最大值，最小值和平方和，来进行操作。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define il inline
#define db double
#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a<b)?(a):(b))
using namespace std;
il int gi()
{
int x=0,y=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘)
{
if(ch==‘-‘)
y=-1;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘)
{
x=x*10+ch-‘0‘;
ch=getchar();
}
return x*y;
}
int a[500005],tmax[2000005],tmin[2000005],tsum[2000005];
il void build(int rt,int l,int r)
{
if(l==r)
{
tmax[rt]=tmin[rt]=a[l];
tsum[rt]=a[l]*a[l];
return;
}
int m=(l+r)>>1;
build(rt<<1,l,m);
build(rt<<1|1,m+1,r);
tmax[rt]=max(tmax[rt<<1],tmax[rt<<1|1]);
tmin[rt]=min(tmin[rt<<1],tmin[rt<<1|1]);
tsum[rt]=tsum[rt<<1]+tsum[rt<<1|1];
}
il int querymax(int rt,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
return tmax[rt];
int m=(l+r)>>1,r1=-1e9,r2=-1e9;
if(L<=m)
r1=querymax(rt<<1,l,m,L,R);
if(m<R)
r2=querymax(rt<<1|1,m+1,r,L,R);
return max(r1,r2);
}
il int querymin(int rt,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
return tmin[rt];
int m=(l+r)>>1,r1=1e9,r2=1e9;
if(m>=L)
r1=querymin(rt<<1,l,m,L,R);
if(m<R)
r2=querymin(rt<<1|1,m+1,r,L,R);
return min(r1,r2);
}
il int querysum(int rt,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
return tsum[rt];
int m=(l+r)>>1,s=0;
if(m>=L)
s+=querysum(rt<<1,l,m,L,R);
if(m<R)
s+=querysum(rt<<1|1,m+1,r,L,R);
return s;
}
il void update(int rt,int l,int r,int pos,int v)
{
if(l==r)
{
tmax[rt]=v;
tmin[rt]=v;
tsum[rt]=v*v;
return;
}
int m=(r+l)>>1;
if(pos<=m)
update(rt<<1,l,m,pos,v);
else
update(rt<<1|1,m+1,r,pos,v);
tmax[rt]=max(tmax[rt<<1],tmax[rt<<1|1]);
tmin[rt]=min(tmin[rt<<1],tmin[rt<<1|1]);
tsum[rt]=tsum[rt<<1]+tsum[rt<<1|1];
}
il int he(int x,int y)
{
int s=0;
for(int i=x;i<=y;i++)
s+=i*i;
return s;
}
int main()
{
memset(tmin,127/3,sizeof(tmin));
int n=gi(),m=gi(),l,r,minx,maxn,sum,vis;
for(int i=1;i<=n;i++)
a[i]=gi();
build(1,1,n);
for(int i=1;i<=m;i++)
{
vis=gi(),l=gi(),r=gi();
if(vis==2)
{
minx=querymin(1,1,n,l,r);
maxn=querymax(1,1,n,l,r);
sum=querysum(1,1,n,l,r);
if(maxn-minx!=r-l)
{
printf("yuanxing\n");
continue;
}
if(he(minx,maxn)==sum)
printf("damushen\n");
else
printf("yuanxing\n");
}
else
update(1,1,n,l,r);
}
return 0;
}
原文：https://www.cnblogs.com/gshdyjz/p/9775487.html