小A盗墓

时间限制: 5 Sec 内存限制: 128 MB

题目描述

小A终于通过了保安的考验，来到了古墓门前，古墓门前有n根柱子，第i根柱子的高度是整数。古墓的门上会弹出一些暗号，机智小A猜到这个暗号表示询问第l到第r根柱子的高度在升序排序后是否构成一段连续且上升的序列。并且这些柱子的高度还可能在弹出暗号的过程中出现变化。

现在小A需要回答出每个暗号的答案

输入

第一行两个整数，表示柱子的个数n以及操作的个数m。

第二行n个整数，第i个整数表示第i根柱子的高度。

接下来m行，每行三个整数opt, x, y。当opt=1时，表示把第x根柱子的高度改为y；当opt=2时，表示询问第x到第y根柱子的高度在升序排序后是否构成一段连续且上升的序列。若是，则输出Yes，否则输出No。

输出

对于每个询问输出一行Yes或No。

样例输入

样例输出

Yes
Yes
Yes
Yes

提示

Solution：

一开始想到的是最朴素的做法，用线段树维护区间和及最值，然后主席树维护区间内数的个数，但显然空间不够。

再仔细想了想看看能不能从区间和入手，使得不同的数产生的区间和唯一，这就是费马大定理了：

当整数时，关于的方程没有正整数解。

#pragma GCC optimite(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 500010;
int a[N];
struct Seg
{
    int l,r,lx,rx;
    ull sum;
}t[N<<2];
inline void pushup(int p)
{
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
    t[p].lx=min(t[p<<1].lx,t[p<<1|1].lx);
    t[p].rx=max(t[p<<1].rx,t[p<<1|1].rx);
}
void update(int p,int x,int val)
{
    if(t[p].l==t[p].r)
    {
        t[p].lx=t[p].rx=val;
        t[p].sum=(ull)val*val*val;
        return;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid) update(p<<1,x,val);
    else update(p<<1|1,x,val);
    pushup(p);
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r)
    {
        t[p].lx=t[p].rx=a[l];
        t[p].sum=(ull)a[l]*a[l]*a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
ull query(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].sum;
    int mid=(t[p].l+t[p].r)/2;
    ull val=0;
    if(l<=mid) val+=query(p*2,l,r);
    if(r>mid) val+=query(p*2+1,l,r);
    return val;
}
int ask1(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].rx;
    int mid=(t[p].l+t[p].r)/2;
    int ans=-1;
    if(l<=mid) ans=max(ans,ask1(p<<1,l,r));
    if(r>mid) ans=max(ans,ask1(p<<1|1,l,r));
    return ans;
}
int ask2(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].lx;
    int mid=(t[p].l+t[p].r)/2;
    int ans=1e9+7;
    if(l<=mid) ans=min(ans,ask2(p<<1,l,r));
    if(r>mid) ans=min(ans,ask2(p<<1|1,l,r));
    return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,op,x,y;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        cin>>op>>x>>y;
        if(op==1) update(1,x,y);
        else
        {
            ull l=ask2(1,x,y),r=ask1(1,x,y);
            ull tmp=(ull)(r*(r+1)/2+l*(l-1)/2)*(r*(r+1)/2-l*(l-1)/2);
            if(query(1,x,y)==tmp) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

View Code