题解 P3792 【由乃与大母神原型和偶像崇拜】

· · 题解

这题，主要是维护平方和来判断区间是否连续，但这里任然有两个问题：

1.值域为1e9，极限下，long long是一定会爆炸的

2.正如讨论区的，平方和可以被hack

那么该如何解决这个问题呢？

我的想法是——离散化！

离散化后，值域的极限就在1e6，假设这5e5个数，每个都是1e6，平方和也才5e17，long long是不会爆炸的。

离散化后，虽说hack的几率就减小了，但是，为了准确性，我们可以同时再维护个和(我觉得，这样应该很难被hack了吧。。。)

所以我们完成这题，可以先将原数，以及opt==1时的数字离散化一波，再进行操作！

具体的操作跟其他题解差不多，没什么好讲的了~(由于本人比较菜，是自己模拟的离散化，勿喷...QwQ)

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+1,M=1e3;
struct node{//线段树维护:和，平方和，区间极值 
    long long s,w,ming,maxe;
}t[N<<2];
struct thing{//离散化数组 
    int w,num;
}p[N<<1];
int a[N],opt[N],L[N],R[N];
long long mi,mx,S;
inline void build(int now,int l,int r){//建树 
    if(l==r){
        t[now].s=a[l];
        t[now].w=1LL*a[l]*a[l];
        t[now].maxe=t[now].ming=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(now<<1,l,mid),build(now<<1|1,mid+1,r);
    t[now].s=t[now<<1].s+t[now<<1|1].s;
    t[now].w=t[now<<1].w+t[now<<1|1].w;
    t[now].maxe=max(t[now<<1].maxe,t[now<<1|1].maxe);
    t[now].ming=min(t[now<<1].ming,t[now<<1|1].ming);
}
inline void change(int now,int l,int r,int k,int x){//单点修改 
    if(l==r){
        t[now].s=x;
        t[now].w=1LL*x*x;
        t[now].ming=t[now].maxe=x;
        return;
    }
    int mid=(l+r)>>1;
    if(k<=mid){
        change(now<<1,l,mid,k,x);
    }
    else{
        change(now<<1|1,mid+1,r,k,x);
    }
    t[now].s=t[now<<1].s+t[now<<1|1].s;
    t[now].w=t[now<<1].w+t[now<<1|1].w;
    t[now].maxe=max(t[now<<1].maxe,t[now<<1|1].maxe);
    t[now].ming=min(t[now<<1].ming,t[now<<1|1].ming);
}
inline long long find(int now,int l,int r,int lc,int rc){//区间查询 
    if(lc<=l&&r<=rc){
        S+=t[now].s;
        mx=max(mx,t[now].maxe);
        mi=min(mi,t[now].ming);
        return t[now].w;
    }
    int mid=(l+r)>>1;
    long long sum=0;
    if(lc<=mid){
        sum+=find(now<<1,l,mid,lc,rc);
    }
    if(rc>mid){
        sum+=find(now<<1|1,mid+1,r,lc,rc);
    }
    return sum;
}
inline long long suan(long long x){//返回1^2+...+x^2 
    long long sut=(x*(x+1)/2)*(2*x+1)/3;
    return sut;
}
inline bool kkk(thing x,thing y){
    return x.w<y.w;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        p[i].w=a[i],p[i].num=i;//离散化储存 
    }
    int e=n;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&opt[i],&L[i],&R[i]);
        if(opt[i]==1){//离散化储存 
            p[++e].w=R[i];
            p[e].num=i+n;
            continue;
        }
    }
    sort(p+1,p+e+1,kkk);
    int ran=1;
    if(p[1].num<=n){//离散化 
        a[p[1].num]=1;
    }
    else{
        R[p[1].num-n]=1;
    }
    for(int i=2;i<=e;++i){//离散化 
        if(p[i].w!=p[i-1].w){
            ran++;
        }
        if(p[i].num<=n){
            a[p[i].num]=ran;
            continue;
        }
        R[p[i].num-n]=ran;
    }
    build(1,1,n);
    for(int i=1;i<=m;++i){
        if(opt[i]==1){
            change(1,1,n,L[i],R[i]);//单点修改 
            continue;
        }
        S=0,mi=2e9,mx=-2e9;//初始化 
        long long sum=find(1,1,n,L[i],R[i]);//这样写可以只find一次，当然也可以直接返回四元组。。。 
        if(mx-mi!=R[i]-L[i]){//如果极值之差不等于区间左右端点，则必不连续 
            puts("yuanxing");
            continue;
        }
        long long sut=suan(mx)-suan(mi-1);//获得平方和 
        if(S!=(mx+mi)*(mx-mi+1)/2||sut!=sum){//比较，若不等，则必不为连续区间 
            puts("yuanxing");
            continue;
        }
        puts("damushen");
    }
    return 0;
}