luoguP5105 不强制在线的动态快速排序

emm

可重集合没用用。直接变成不可重复集合

有若干个区间

每个区间形如[L,R]

[L,R]计算的话，就是若干个连续奇数的和。拆位统计1的个数

平衡树维护

加入一个[L,R]，把相交的区间合并。之后相邻不相交的部分O(1)计算贡献到答案里。

O(nlogn+30n)

不强制在线的动态快速排序

写起来并不太好写

set就可以

删除一些区间，合并成大区间

要分类讨论

至于calc(l,r)

有O(1)公式，可以不用按位：

第一个第二个发现了，后面就是多余位置处理即可。

代码：

1.注意插入区间被包含的情况，删掉前驱，R还要取一个max

2.按位的话，最高的是1e9+1e9=2e9，是1<<30，不是29.。。

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

int q;

struct po{

    ll l,r;

    po(){}

    po(int x,int y){

        l=x;r=y;

    }

    bool friend operator <(po a,po b){

        if(a.l!=b.l) return a.l<b.l;

        return a.r<b.r;

    }

};

set<po>s;

set<po>::iterator it,le,ri;

ll ans;

ll pre(int x,ll p){

    if(p==) return x%;

    if(p==) {

        if(x%==) return ;

        if(x%==) return ;

        if(x%==) return ;

        if(x%==) return ;

    }

    x=x%(<<p);

    if(x==) return (<<(p-))%;

    return max(,x-(<<(p-)))%;

}

ll clac(int l,int r){

    ll ret=;

    l=(l+l+)/+;

    r=(r+r-)/+;

    if(l>r) return ;

    for(ll i=;i>=;--i){

        ret+=(pre(r,i)-pre(l-,i)+++)%*(<<i);

    }

    return ret;

}

void dele(int typ){

    if(typ==){//pre and bac and me

        ll tmp=clac((*it).l,(*it).r);

        ans^=tmp;

        ri=it;

        ++ri;

        if(ri!=s.end()){

            ans^=((*ri).l)*((*ri).l)-((*it).r)*((*it).r);

        }

        le=it;

        if(le!=s.begin()){

            --le;

            ans^=((*it).l)*((*it).l)-((*le).r)*((*le).r);

        }

        s.erase(it);

    }

    else if(typ==){//bac and me

        ll tmp=clac((*it).l,(*it).r);

        ans^=tmp;

        ri=it;

        ++ri;

        if(ri!=s.end()){

            ans^=((*ri).l)*((*ri).l)-((*it).r)*((*it).r);

        }

        s.erase(it);

    }else {//only bac

        ri=it;

        ++ri;

        if(ri!=s.end()){

            ans^=((*ri).l)*((*ri).l)-((*it).r)*((*it).r);

        }

    }

}

void ins(int l,int r){

    if(s.empty()){

        ans^=clac(l,r);

        s.insert(po(l,r));

    }else{

        it=s.lower_bound(po(l,r));

        ll L=l,R=r;

        //bool fl=false;

        if(it!=s.begin()){

            --it;

            if((*it).r>=l-){

                L=min(L,(*it).l);

                R=max(R,(*it).r);

                dele();

                //fl=true;

                it=s.lower_bound(po(l,r));

            }else{

                dele();

            }

        }

        while(){

            it=s.lower_bound(po(l,r));

            if(it==s.end()) break;

            if((*it).l>r) break;

            R=max(R,(*it).r);

            dele();

        }

        if(it!=s.end()){

            ans^=((*it).l)*((*it).l)-R*R;

        }

        if(it!=s.begin()){

            --it;

            ans^=L*L-((*it).r)*((*it).r);

        }

        ans^=clac(L,R);

        s.insert(po(L,R));

    }

}

int main(){

    rd(q);

    int op,l,r;

    while(q--){

        rd(op);

        if(op==){

            rd(l);rd(r);

            ins(l,r);

        }else{

            printf("%lld\n",ans);

        }

    }

    return ;

}

}

signed main(){

//    freopen("data.in","r",stdin);

//    freopen("my.out","w",stdout);

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/1/16 9:17:43

*/

巴特西

luoguP5105 不强制在线的动态快速排序

最新文章

热门文章