题解洛谷 P3710 【方方方的数据结构】

因为有撤销操作，所以修改操作可能会只会存在一段时间，因此把时间看作一维，被修改的序列看作一维。

可以把操作都离线下来，对于每个修改操作，就是在二维平面上对一个矩形进行修改，询问操作，就是查询单点权值。

具体实现时，可以对所有询问操作查询的单点建\(K-D\ Tree\)，然后在\(K-D\ Tree\)上矩形修改即可。

\(code:\)

#include<bits/stdc++.h>

#define maxn 600010

#define p 998244353

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int n,m,root,tot,type,cnt;

ll ans;

struct node

{

    int opt,u,d,pos;

    ll v;

}q[maxn];

struct KD_tree

{

    int d[2],mi[2],ma[2],ls,rs;

    ll val,add,mul;

}t[maxn],dat[maxn];

bool cmp(const KD_tree &a,const KD_tree &b)

{

    return a.d[type]<b.d[type];

}

void pushup(int cur)

{

    int ls=t[cur].ls,rs=t[cur].rs;

    for(int i=0;i<=1;++i)

    {

        t[cur].ma[i]=t[cur].mi[i]=t[cur].d[i];

        if(ls)

        {

            t[cur].ma[i]=max(t[cur].ma[i],t[ls].ma[i]);

            t[cur].mi[i]=min(t[cur].mi[i],t[ls].mi[i]);

        }

        if(rs)

        {

            t[cur].ma[i]=max(t[cur].ma[i],t[rs].ma[i]);

            t[cur].mi[i]=min(t[cur].mi[i],t[rs].mi[i]);

        }

    }

}

void pushadd(int cur,ll v)

{

    t[cur].val=(t[cur].val+v)%p,t[cur].add=(t[cur].add+v)%p;

}

void pushmul(int cur,ll v)

{

    t[cur].val=t[cur].val*v%p,t[cur].add=t[cur].add*v%p,t[cur].mul=t[cur].mul*v%p;

}

void pushdown(int cur)

{

    int ls=t[cur].ls,rs=t[cur].rs;

    if(t[cur].mul!=1) pushmul(ls,t[cur].mul),pushmul(rs,t[cur].mul),t[cur].mul=1;

    if(t[cur].add) pushadd(ls,t[cur].add),pushadd(rs,t[cur].add),t[cur].add=0;

}

void build(int l,int r,int k,int &cur)

{

    cur=++tot,type=k;

    int mid=(l+r)>>1;

    nth_element(dat+l+1,dat+mid+1,dat+r+1,cmp);

    t[cur]=dat[mid],t[cur].mul=1;

    if(l<mid) build(l,mid-1,k^1,t[cur].ls);

    if(r>mid) build(mid+1,r,k^1,t[cur].rs);

    pushup(cur);

}

bool out(int cur,int u,int d,int l,int r)

{

    return u>t[cur].ma[0]||d<t[cur].mi[0]||l>t[cur].ma[1]||r<t[cur].mi[1];

}

bool in(int cur,int u,int d,int l,int r)

{

    return u<=t[cur].mi[0]&&d>=t[cur].ma[0]&&l<=t[cur].mi[1]&&r>=t[cur].ma[1];

}

bool check(int cur,int u,int d,int l,int r)

{

    return u<=t[cur].d[0]&&d>=t[cur].d[0]&&l<=t[cur].d[1]&&r>=t[cur].d[1];

}

void modify_add(int cur,int u,int d,int l,int r,ll v)

{

    if(out(cur,u,d,l,r)) return;

    if(in(cur,u,d,l,r))

    {

        pushadd(cur,v);

        return;

    }

    if(check(cur,u,d,l,r)) t[cur].val=(t[cur].val+v)%p;

    int ls=t[cur].ls,rs=t[cur].rs;

    pushdown(cur);

    if(ls) modify_add(ls,u,d,l,r,v);

    if(rs) modify_add(rs,u,d,l,r,v);

}

void modify_mul(int cur,int u,int d,int l,int r,ll v)

{

    if(out(cur,u,d,l,r)) return;

    if(in(cur,u,d,l,r))

    {

        pushmul(cur,v);

        return;

    }

    if(check(cur,u,d,l,r)) t[cur].val=t[cur].val*v%p;

    int ls=t[cur].ls,rs=t[cur].rs;

    pushdown(cur);

    if(ls) modify_mul(ls,u,d,l,r,v);

    if(rs) modify_mul(rs,u,d,l,r,v);

}

void query(int cur,int x,int y)

{

    if(x>t[cur].ma[0]||x<t[cur].mi[0]||y>t[cur].ma[1]||y<t[cur].mi[1]) return;

    if(x==t[cur].d[0]&&y==t[cur].d[1])

    {

        ans=t[cur].val;

        return;

    }

    int ls=t[cur].ls,rs=t[cur].rs;

    pushdown(cur);

    if(ls) query(ls,x,y);

    if(rs) query(rs,x,y);

}

int main()

{

    read(n),read(m);

    for(int i=1;i<=m;++i)

    {

        read(q[i].opt);

        if(q[i].opt<=2) read(q[i].u),read(q[i].d),read(q[i].v);

        if(q[i].opt==3) read(q[i].pos),dat[++cnt].d[0]=q[i].pos,dat[cnt].d[1]=i;

        if(q[i].opt==4) read(q[i].pos),q[q[i].pos].pos=i;

    }

    for(int i=1;i<=m;++i)

        if(q[i].opt<=2&&!q[i].pos)

            q[i].pos=m;

    build(1,cnt,0,root);

    for(int i=1;i<=m;++i)

    {

        if(q[i].opt==1) modify_add(root,q[i].u,q[i].d,i,q[i].pos,q[i].v);

        if(q[i].opt==2) modify_mul(root,q[i].u,q[i].d,i,q[i].pos,q[i].v);

        if(q[i].opt==3) query(root,q[i].pos,i),printf("%lld\n",ans);

    }

    return 0;

}

巴特西

题解洛谷 P3710 【方方方的数据结构】

最新文章

热门文章

巴特西

题解 洛谷 P3710 【方方方的数据结构】

最新文章

热门文章

题解洛谷 P3710 【方方方的数据结构】