[Avito Code Challenge 2018 G] Magic multisets（线段树）

题目链接：http://codeforces.com/contest/981/problem/G

题目大意：

有n个初始为空的‘魔法’可重集，向一个‘可重集’加入元素时，若该元素未出现过，则将其加入；否则该可重集中所有元素的个数都会翻倍。

例如将$2$加入${1,3}$会得到${1,2,3}$，将$2$加入${1,2,3,3}$会得到${1,1,2,2,3,3,3,3}$.

$q$次操作，每次操作要么向一个区间内的所有可重集加入某个元素，要么询问一个区间内可重集的大小之和。

$n,q ≤ 2×10^5$

题解：

发现对于出现过该元素的区间就是区间乘，没有出现过的就是区间加

操作1我们先把$[l,r]$全部乘上2，再把之前已经出现过当前元素的区间乘上2的逆元再+1，最后合并一下左右区间就好了。合并大概就是保证这个操作时间复杂度的关键了，只是我也不知道怎么算

发现这样我们要维护每个元素出现的区间，同时支持方便的合并，我们开n个set就好了

正是做完这题我发现我竟然不会写区间乘法线段树

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

#include<set>

#define pa pair<int,int>

#define mid ((l+r)>>1)

using namespace std;

typedef long long ll;

const int N=2e5+;

const int mod=;

ll n,q,inv;

ll sum[N<<],add[N<<],mul[N<<];

set <pa> st[N];

inline ll read()

{

    char ch=getchar();

    ll s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

ll qpow(ll a,ll b)

{

    ll re=;

    for (;b;b>>=,a=a*a%mod) if (b&) re=re*a%mod;

    return re;

}

void build(int o,int l,int r)

{

    mul[o]=;add[o]=sum[o]=;

    if (l==r) return;

    build(o<<,l,mid);

    build(o<<|,mid+,r);

}

void pushup(int o,int l,int r)

{

    //sum[o]=sum[o<<1]+sum[o<<1|1];

    sum[o]=(sum[o<<]*mul[o<<]+add[o<<]*(mid-l+))%mod;

    sum[o]=(sum[o]+sum[o<<|]*mul[o<<|]+add[o<<|]*(r-mid))%mod;

}

void pushdown(int o,int l,int r)

{

    if (mul[o]!=)

    {

        ll p=mul[o];

        mul[o]=;

        //(sum[o<<1]*=p)%=mod;

        //(sum[o<<1|1]*=p)%=mod;

        (add[o<<]*=p)%=mod;

        (add[o<<|]*=p)%=mod;

        (mul[o<<]*=p)%=mod;

        (mul[o<<|]*=p)%=mod;

    }

    if (add[o]!=)

    {

        ll p=add[o];

        add[o]=;

    //  (sum[o<<1]+=p*(mid-l+1))%=mod;

    //    (sum[o<<1|1]+=p*(r-mid))%=mod;

        (add[o<<]+=p)%=mod;

        (add[o<<|]+=p)%=mod;

    }

}

void update(int o,int l,int r,int x,int y,ll z,int flag)

{

    if (l>=x&&r<=y)

    {

        if (flag==)

        {

            (mul[o]*=z)%=mod;

            (add[o]*=z)%=mod;

        //    (sum[o]*=z)%=mod;

        }

        if (flag==)

        {

            (add[o]+=z)%=mod;

        //    (sum[o]+=(r-l+1)*z)%=mod;

        }

        return;

    }

    pushdown(o,l,r);

    if (x<=mid) update(o<<,l,mid,x,y,z,flag);

    if (y>mid) update(o<<|,mid+,r,x,y,z,flag);

    pushup(o,l,r);

}

void merge(int x,int L,int R)

{

    set<pa>::iterator it;

    it=st[x].lower_bound(pa(L,L));

    for (;it!=st[x].end();it++)

    {

        set<pa>::iterator lst=it;lst--;

        int l=(*lst).second+;

        int r=(*it).first-;

        int upl=max(L,l);

        int upr=min(R,r);

        if (upr>=upl)

        {

            update(,,n,upl,upr,inv,);

            update(,,n,upl,upr,,);

        }

        if ((*it).first>=R) break;

    }

    int mergeL=L,mergeR=R;

    it=st[x].upper_bound(pa(L,L));it--;

    if ((*it).second>=mergeL) mergeL=(*it).first;

    it=st[x].upper_bound(pa(R,R));it--;

    if ((*it).second>=mergeR) mergeR=(*it).second;

    vector <pa> er;

    it=st[x].lower_bound(pa(mergeL,mergeL));

    for (;it!=st[x].end();it++)

    {

        pa e=*it;

        if (e.first>=mergeL&&e.second<=mergeR) er.push_back(e);

        else break;

    }

    for (int i=;i<er.size();i++) st[x].erase(er[i]);

    st[x].insert(pa(mergeL,mergeR));

}

ll query(int o,int l,int r,int x,int y)

{

    if (l>=x&&r<=y) return (sum[o]*mul[o]+add[o]*(r-l+))%mod;

//    if (l>=x&&r<=y) return sum[o]%mod;

    pushdown(o,l,r);

    ll re=;

    if (x<=mid) (re+=query(o<<,l,mid,x,y))%=mod;

    if (y>mid) (re+=query(o<<|,mid+,r,x,y))%=mod;

    pushup(o,l,r);

    return re;

}

int main()

{

    inv=qpow(,mod-);

    //inv=(mod+1)/2;

    n=read();q=read();

    for (int i=;i<=n;i++)

    {

        st[i].insert(pa(,));

        st[i].insert(pa(n+,n+));

    }

    build(,,n);

    while (q--)

    {

        int opt=read();

        if (opt==)

        {

            int l=read(),r=read(),z=read();

            update(,,n,l,r,,);

            merge(z,l,r);

        }

        if (opt==)

        {

            int l=read(),r=read();

            printf("%lld\n",query(,,n,l,r));

        }

    }

    return ;

}

巴特西

[Avito Code Challenge 2018 G] Magic multisets（线段树）

题目链接：http://codeforces.com/contest/981/problem/G

题目大意：

题解：

最新文章

热门文章