题解 P6812 【「MCOI-02」Ancestor 先辈】

· · 题解

定义&本质：

屑其实是什么意思呢？

就是把两个序列头对齐放在一起，只要下面的数全部大于等于上面的数，上面的就比下面的屑。

例如1 3 4 6 7和8 8 8 8

1 3 4 6 7

8 8 8 8

此时，8大于1，8大于3，8大于4，8大于6，所以上面的序列比下面的屑。

那相信先辈是什么意思大家也懂了。

但要什么时候一个序列才是先辈呢？

既然要一个序列的后缀把原序列屑掉，那么这个后缀对齐原序列的头之后，肯定所有的数都大于等于上面的原序列的数，换句话说，也就是需要这个序列是一个不下降序列。

于是这道题就很简单了。

思路：

可以用万能的线段树来做。

我们合并的时候怎么才能判断这个合并出来的区间是不是先辈呢？

我们只需要判断，左边和右边的是不是先辈，然后判断左末和右头满不满足不下降即可。

于是这道题就没有难点了，剩下的都是线段树基本操作。

注意在query里面要用新的merge函数更新即可。

代码：

/*
  Author: EnderDeer
  Online Judge: Luogu
*/

#include<bits/stdc++.h>

#define int long long

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

struct node{
    int l;
    int r;
    int lw;
    int rw;
    bool flag;
}e[10000010];

int n,m;
int a[10000010];
int lazy[10000010];

void merge(int i){
    e[i].lw = e[i * 2].lw;
    e[i].rw = e[i * 2 + 1].rw;
    if(e[i * 2].rw <= e[i * 2 + 1].lw && e[i * 2].flag && e[i * 2 + 1].flag)e[i].flag = true;
    else e[i].flag = false;
}

void renewans(node &x,node &y,node &z){
    x.lw = y.lw;
    x.rw = z.rw;
    if(y.flag && z.flag && y.rw <= z.lw)x.flag = true;
    else x.flag = false;
}

void pushup(int i,int w){
    e[i].lw += w;
    e[i].rw += w;
    lazy[i] += w;
}

void pushdown(int i){
    if(e[i].l == e[i].r)return ;
    pushup(i * 2,lazy[i]);
    pushup(i * 2 + 1,lazy[i]);
    lazy[i] = 0;
}

void build(int i,int l,int r){
    e[i].l = l;
    e[i].r = r;
    if(l == r){
        e[i].lw = e[i].rw = a[l];
        e[i].flag = true;
        return ;
    }
    int mid = (l + r) / 2;
    build(i * 2,l,mid);
    build(i * 2 + 1,mid + 1,r);
    merge(i);
}

void update(int i,int l,int r,int w){
    if(e[i].l >= l && e[i].r <= r){
        pushup(i,w);
        return ; 
    }
    pushdown(i);
    int mid = (e[i].l + e[i].r) / 2;
    if(mid >= l)update(i * 2,l,r,w);
    if(mid < r)update(i * 2 + 1,l,r,w);
    merge(i);
}

node query(int i,int l,int r){
    if(e[i].l >= l && e[i].r <= r)return e[i];
    pushdown(i);
    int mid = (e[i].l + e[i].r) / 2;
    node ans;
    node ans1;
    node ans2;
    if(mid >= r)return query(i * 2,l,r);
    else if(mid < l)return query(i * 2 + 1,l,r);
    else {
        ans1 = query(i * 2,l,mid);
        ans2 = query(i * 2 + 1,mid + 1,r);
        renewans(ans,ans1,ans2);
    }
    return ans;
}

signed main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i ++)a[i] = read();
    build(1,1,n);
    while(m --){
        int op;
        int l,r,w;
        op = read();
        if(op == 1){
            l = read(),r = read(),w = read();
            update(1,l,r,w);
        }
        else {
            l = read(),r = read();
            node ans = query(1,l,r);
            if(ans.flag == true)puts("Yes");
            else puts("No");
        }
    }
    return 0;
}