P9912 [COCI 2023/2024 #2] Zatopljenje 题解

JimmyLee · 2024-03-10 17:12:10 · 题解

解法

一组询问

先考虑一个简化版的情况，如果只有一组询问怎么处理。

那不直接打暴力

可以考虑一个常见的技巧：每个位置赋一个颜色 c_i，满足：

这样我们就把原来的序列变成了一个 01 串。

问题就变成了 01 串上给定区间 [l, r] 中连续的 1 的区间的个数。

多组询问

有个显然的结论：如果 x_i 单调下降，则生成的 01 串中只会有 0 变成 1。

在这种情况下问题就变成了单点修改，区间查询连续的 1 的区间的个数。

直接线段树。解决。

所以做法就是先将询问离线，按 x_i 从大到小排序。

每次先加入当前高度下新加入的节点， 然后查询 [l_i, r_i] 间的连续的 1 的区间的个数。

每次新加入的节点可以用桶预先统计好。

Code

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

struct SegT
{
    struct node
    {
        int l=0, r=0, ans=0;
        node operator+(node b) {return {l, b.r, ans+b.ans-(r&&r==b.l)};}
        void operator=(int b) {l=r=ans=b;}
    }tr[maxn<<2];

    #define lc   (x<<1)
    #define rc   (x<<1|1)
    #define mid  ((l+r)>>1)
    #define lson lc, l, mid
    #define rson rc, mid+1, r
    #define rt   1, 1, n

    void push_up(int x) {tr[x]=tr[lc]+tr[rc];}

    void modify(int x, int l, int r, int p)
    {
        if(l==r) return tr[x]=1;
        if(p<=mid) modify(lson, p);
        if(p>mid)  modify(rson, p);
        push_up(x);
    }

    node query(int x, int l, int r, int L, int R)
    {
        if(L<=l&&r<=R) return tr[x];
        if(R<=mid) return query(lson, L, R);
        if(L>mid)  return query(rson, L, R);
        return query(lson, L, R)+query(rson, L, R);
    }
}tr; // 线段树部分

vector<tuple<int, int, int, int>> qrs; // 储存离线询问
vector<int> adds[maxn] /*存储每次新加入的节点*/, hgt;
int lis[maxn], ans[maxn];

int main()
{
    int n, q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>lis[i];
    for(int i=1, l, r, x;i<=q;i++)
        cin>>l>>r>>x, 
        qrs.emplace_back(x, l, r, i), 
        hgt.emplace_back(x);
    sort(qrs.begin(), qrs.end(), greater());
    sort(hgt.begin(), hgt.end(), greater());
    for(int i=1;i<=n;i++) 
        adds[upper_bound(hgt.begin(), hgt.end(), lis[i], greater())-hgt.begin()+1].emplace_back(i); // 向桶内添加节点
    int cnt=1;
    for(auto [h, l, r, i]:qrs)
    {
        for(auto v:adds[cnt++]) tr.modify(rt, v); 
        ans[i]=tr.query(rt, l, r).ans; // 先改再查
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
}