[ABC256Ex] I like Query Problem 题解

· · 题解

题目概述：

让你写个数据结构，支持区间推平，区间整除，查询区间和。

题目分析：

珂朵莉树套线段树，这道题充斥了我对珂朵莉树的所有理解。

看到区间推平，我相信学过珂朵莉树的人已经按捺不住内心想直接写个珂朵莉树胡上去，我也是，但是这是 Ex 题，过不去。

分析原因，很简单，因为块数太散了，每次查询和整除操作的复杂度太傻，一步思考，我们可以通过定期重构的方式，每相隔 \sqrt q 的时间，就用线性的复杂度将 set 中权值连续的部分变成极大块，来优化查询和整除操作，但是，还是过不去。

我们每次优化的就是两个要进行块间遍历的操作，所以定期重构可以理解为用近似 O(n \sqrt q) 的复杂度去均摊两个暴力操作的的复杂度。

有啥数据结构也可以降低查询的复杂度呢？线段树。

我们发现线段树很容易支持区间推平和区间和操作，稳定 O( \log n)，难在区间整除（其实你如果会，这就是个势能线段树的板子），但珂朵莉树却可以很简单的进行区间整除，结合我们上面的均摊思想，一个新方法诞生了。

每次整除操作和区间推平时，都重构一遍 split 出来的左右端点中间的块，归并成权值相同的极大块，再用线段树进行区间推平，相当于把定期重构换成了遇上修改操作就重构一遍修改操作中间的所有块，再用线段树推平维护一遍，查询就可以直接 O(\log n) 的做。

这玩意是对的，比纯暴力珂朵莉树快 6s 多，下面口胡一下复杂度。

因为每次操作都保证了相同权值极大块，所以每次整除至少是 \log 的，又因为我们外面又套了棵线段树，所以整体近似 O(n \log^2 n) 的，不严格在整除操作，加上 STL 和线段树并用的巨大常数，所以跑的还是比较慢的。

Code.

#include<bits/stdc++.h>
#define int long long
inline char gc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read()
{
    int x=0; char c=gc(); bool f=0;
    for(;c<'0'||c>'9';c=gc()) f|=(c=='-');
    for(;c>='0'&&c<='9';c=gc()) x=(x<<1)+(x<<3)+(c^48);
    return x=f ? -x : x;
}
using namespace std;
const int N=5e5+10;
int n,q,a[N],tt; struct Seg {int l,r,sum,tag;} tr[N<<2];
inline void pushup(int u) {tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;}
inline void pushdown(int u)
{
    if(tr[u].tag != -1)
    {
        tr[u<<1].sum=tr[u].tag*(tr[u<<1].r - tr[u<<1].l + 1);
        tr[u<<1|1].sum=tr[u].tag*(tr[u<<1|1].r - tr[u<<1|1].l + 1);
        tr[u<<1].tag=tr[u<<1|1].tag=tr[u].tag;
    }
    tr[u].tag=-1;
}
inline void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r,tr[u].tag=-1;
    if(l == r) return tr[u].sum=a[l],void();
    int mid = (l + r) >> 1ll;
    build(u<<1,l,mid); build(u<<1|1,mid+1,r);
    pushup(u);
}
inline int query(int u,int l,int r)
{
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1ll,res=0;
    if(l <= mid) res=query(u<<1,l,r); if(mid < r) res+=query(u<<1|1,l,r);
    return res;
}
inline void modify(int u,int l,int r,int k)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].sum=k*(tr[u].r - tr[u].l + 1);
        tr[u].tag=k; return ;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1ll;
    if(l <= mid) modify(u<<1,l,r,k); if(mid < r) modify(u<<1|1,l,r,k);
    pushup(u);
}
struct node
{
    int l,r; mutable int v;
    bool operator < (const node &o) const {
        return l < o.l;
    }
} t[N]; set<node> s;
inline set<node> :: iterator split(int pos)
{
    auto it=s.lower_bound(node{pos,-1,0});
    if(it->l == pos && it != s.end()) return it;
    it -- ; int l=it->l,r=it->r,v=it->v;
    s.erase(it); s.insert(node{l,pos-1,v});
    return s.insert(node{pos,r,v}).first;
}
inline void assign(int l,int r,int v)
{
    auto itr=split(r+1),itl=split(l);
    s.erase(itl,itr); s.insert(node{l,r,v});
    modify(1,l,r,v);
}
inline void qr(int l,int r,int x)
{
    auto itr=split(r+1),itl=split(l); int pl=0,yl=1;
    for(auto it=itl;it!=itr;it++) it->v/=x,t[++pl]=*it;
    s.erase(itl,itr);
    for(int i=2;i<=pl;i++)
    {
        if(t[i].v == t[yl].v) t[yl].r=t[i].r;
        else t[++yl]=t[i];
    }
    for(int i=1;i<=yl;i++)
    {
        s.insert(node{t[i].l,t[i].r,t[i].v});
        modify(1,t[i].l,t[i].r,t[i].v);
    }
}
signed main()
{
    n=read(); q=read();
    for(int i=1,l=1;i<=n;i++)
    {
        a[i]=read(); if(i == 1) tt=a[i];
        else if(a[i] != tt || i == n)
        {
            s.insert(node{l,i-1,tt});
            l=i,tt=a[i];
        }
    }
    s.insert(node{n,n,a[n]}); build(1,1,n);
    while(q -- )
    {
        int op=read(),l=read(),r=read();
        if(op == 1) qr(l,r,read()); 
        else if(op == 2) assign(l,r,read());
        else printf("%lld\n",query(1,l,r));
    }
    return 0;
}

这个玩意我把它作为有区间推平操作的势能线段树的下位替代品，可以说是用珂朵莉树来简化修改，或者说是用线段树来优化查询了，优点可能是少去了原本在线段树上分析势能的操作，比较无脑且好写，适合暴力。