YAMAYA 题解

题目大意

$n$ 个小夫坐成一排，每个小夫有一个真实值 $v_i$。小夫们有 $m$ 场聚会，第 $i$ 次聚会会在编号为 $[l_i, r_i]$ 的小夫中举办。

聚会之后，这些小夫的真实值会变为他们之中的真实值的最大值。将会发生 $q$ 次事件，有两类事件。

第一类事件，第 $x$ 个小夫的真实值变成了 $y$。
第二类事件，小夫们向你提问，假如第 $L$ 次聚会到第 $R$ 次聚会按顺序举办，第 $x$ 个小夫的真实值会变成多少。

Solution

鲜花：

这道题纯恶心，不可爱。

也有可能只是我太菜了。:(

正解：

比较显然的一点是：$q$ 次询问中，记一次询问的 $x$ 为 $[x,x]$，而后从 $R$ 到 $L$ 枚举每个操作区间，如果区间 $[l_i,r_i]$ 有交，就取两区间的并，最后就将一个点 $[x,x]$ 扩展成了一个区间 $[l,r]$。$x$ 的真实值就是 $[l,r]$ 之间的最大值。

对于 $m$ 次操作，分别对 $l$ 和 $r$ 维护上一次受影响的操作编号。

以维护 $l$ 举例：当前枚举到第 $i$ 次的 $l_i$，去找一个最大的 $j\ (j\leq i-1)$ 使得 $l_i\in [l_j,r_j]$。我们用 $pre_i$ 来记录这个 $j$。（下文出现的 $nxt$ 同理维护 $r$）

现在你已经懂这个啦，但是我们不满足于知道 $i$ 的上一个，我们还想知道 $i$ 的上 $2^k$ 个。这个倍增很好搞，这里不提了。

在维护 $pre$ 与 $nxt$ 的同时，我们顺带记录 $q$ 次查询中每个 $x$ 的被影响的初值。具体的，当前枚举到第 $i$ 次操作，那么对于所有 $R_j=r_i\ (j\in [1,q])$ 的查询来说，操作已然做完了，我们就可以得到最后影响 $x_j$ 的是哪个 $k\ (k\leq i)$，我们令它为 $id_j$。这里可以用区修区查最大值线段树维护。

得到每个 $i\in [1,q]$ 的初值 $id_i$ 后（这里的 $i$ 只讨论 $op_i=2$，上下文都是），就可以拓展区间了。

怎么跑呢？倍增跑就好了~

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115


#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ls rt<<1
#define rs ls|1
#define mid ((l+r)>>1)

const int N=5e5+5;

int n,m,q;
struct node
{
    int op,l,r,x;
}a[N],b[N];
int v[N];
vector<int> Q[N];
int tr[N<<2],lz[N<<2],Id[N];
int pre[N][30],nxt[N][30];

void pushup(int rt) { tr[rt]=max(tr[ls],tr[rs]); }

void build(int rt,int l,int r)
{
    lz[rt]=0;
    if(l==r)
        return tr[rt]=v[l],void();
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(rt);
}

void pushdown(int rt)
{
    tr[ls]=max(tr[ls],lz[rt]);
    lz[ls]=max(lz[ls],lz[rt]);
    tr[rs]=max(tr[rs],lz[rt]);
    lz[rs]=max(lz[rs],lz[rt]);
}

void upd(int rt,int l,int r,int lf,int rg,int x)
{
    if(lf<=l&&r<=rg)
        return tr[rt]=lz[rt]=x,void();
    if(lf>r||l>rg)
        return;
    pushdown(rt);
    if(lf<=mid)
        upd(ls,l,mid,lf,rg,x);
    if(mid<rg)
        upd(rs,mid+1,r,lf,rg,x);
    pushup(rt);
}

int qry(int rt,int l,int r,int lf,int rg)
{
    if(lf<=l&&r<=rg)
        return tr[rt];
    if(lf>r||l>rg)
        return 0;
    int res=0;
    pushdown(rt);
    if(lf<=mid)
        res=qry(ls,l,mid,lf,rg);
    if(mid<rg)
        res=max(res,qry(rs,mid+1,r,lf,rg));
    return res;
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&v[i]);
    for(int i=1;i<=m;i++)
        scanf("%lld%lld",&b[i].l,&b[i].r);
    scanf("%lld",&q);
    for(int i=1;i<=q;i++){
        scanf("%lld%lld%lld",&a[i].op,&a[i].l,&a[i].r);
        if(a[i].op==2)
            scanf("%lld",&a[i].x),Q[a[i].r].emplace_back(i);
    }
    for(int i=1;i<=m;i++){
        pre[i][0]=qry(1,1,n,b[i].l,b[i].l);
        nxt[i][0]=qry(1,1,n,b[i].r,b[i].r);
        upd(1,1,n,b[i].l,b[i].r,i);
        for(int j:Q[i])
            Id[j]=qry(1,1,n,a[j].x,a[j].x);
    }
    for(int j=1;j<=21;j++)
        for(int i=1;i<=m;i++){
            pre[i][j]=pre[pre[i][j-1]][j-1];
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
        }
    build(1,1,n);
    for(int i=1;i<=q;i++){
        if(a[i].op==1){
            upd(1,1,n,a[i].l,a[i].l,a[i].r);
            v[a[i].l]=a[i].r;
            continue;
        }
        if(Id[i]<a[i].l){
            printf("%lld\n",v[a[i].x]);
            continue;
        }
        int l=Id[i],r=Id[i];
        for(int j=21;~j;j--){
            if(pre[l][j]>=a[i].l)
                l=pre[l][j];
            if(nxt[r][j]>=a[i].l)
                r=nxt[r][j];
        }
        printf("%lld\n",qry(1,1,n,b[l].l,b[r].r));
    }
    return 0;
}