Chtholly_tree

神仙数据结构 Chtholly_tree（ODT）

我永远喜欢珂朵莉

Chtholly_tree简介

这是一种很暴力的数据结构（只是暴力，但不黄），基于\(\texttt{STLset}\)
主要用于骗分，可以很好地适应随机数据。
有时可以碾压分块和线段树。

代码集合

#include<set>
#include<vector>
#include<cstdio>
#include<utility>
#include<algorithm>

#define ODT Chtholly_tree

#define LL long long

using namespace std;

struct Chtholly_tree {
    int ll,rr;
    mutable LL val;
    Chtholly_tree(int L,int R=-1,LL V=0): ll(L), rr(R), val(V) {}
    bool operator < (const Chtholly_tree& tt)const {
        return ll<tt.ll;
    }
};

set<ODT> odt;
set<ODT>::iterator split(int pos) {
    set<ODT>::iterator it=odt.lower_bound(ODT(pos));
    if (it!=odt.end()&&it->ll==pos) return it;
    --it;
    ODT tmp=*it;
    odt.erase(it);
    odt.insert(ODT(tmp.ll,pos-1,tmp.val));
    return odt.insert(ODT(pos, tmp.rr, tmp.val)).first;
}
void assign(int l,int r,LL val) {
    set<ODT>::iterator itr=split(r+1), itl=split(l);
    odt.erase(itl,itr);
    odt.insert(ODT(l,r,val));
}
void add(int l,int r,LL val) {
    set<ODT>::iterator itr=split(r+1),itl=split(l);
    for(set<ODT>::iterator it=itl; it!=itr; it++) it->val+=val;
}
LL sum(int l, int r) {
    set<ODT>::iterator itr=split(r + 1),itl=split(l);
    LL res=0;
    for(set<ODT>::iterator it=itl; it!=itr;it++) res+=(it->rr-it->ll+1)*it->val;
    return res;
}
LL rank(int l, int r, int k){
    vector<pair<LL, int> >vec(0);
    set<ODT>::iterator itr=split(r+1),itl=split(l);
    for(set<ODT>::iterator it=itl;it!=itr;it++)vec.push_back(make_pair(it->val,it->rr-it->ll+1));
    sort(vec.begin(),vec.end());
    for (vector<pair<LL,int> >::iterator it=vec.begin();it!=vec.end();it++) if((k-=it->second)<=0) return it->first;
    return -1; //note:if there are negative numbers, return another impossible number.
}
int main() {
}

例题：

CF896C Willem, Chtholly and Seniorious
CF915E Physical Education Lessons
P2787 语文1（chin1）- 理理思维

标程：

CF915E

//by     G_M_H      2019 11 12
//优化常数，将sum加到assign中，组成assign_new
#include<set>
#include<vector>
#include<cstdio>
#include<utility>
#include<algorithm>

#define ODT Chtholly_tree

#define LL long long

using namespace std;

struct Chtholly_tree {
    int ll,rr;
    mutable LL val;
    Chtholly_tree(int L,int R=-1,LL V=0): ll(L), rr(R), val(V) {}
    bool operator < (const Chtholly_tree& tt)const {
        return ll<tt.ll;
    }
};

set<ODT> odt;
LL ans=0;
set<ODT>::iterator split(int pos) {
    set<ODT>::iterator it=odt.lower_bound(ODT(pos));
    if (it!=odt.end()&&it->ll==pos) return it;
    --it;
    ODT tmp=*it;
    odt.erase(it);
    odt.insert(ODT(tmp.ll,pos-1,tmp.val));
    return odt.insert(ODT(pos, tmp.rr, tmp.val)).first;
}
void assign(int l,int r,LL val) {
    set<ODT>::iterator itr=split(r+1), itl=split(l);
    odt.erase(itl,itr);
    odt.insert(ODT(l,r,val));
}
void assign_new(int l,int r,LL val) {
    set<ODT>::iterator itr=split(r+1), itl=split(l);
    for(set<ODT>::iterator it=itl;it!=itr;it++) ans-=it->val*(it->rr-it->ll+1);
    odt.erase(itl,itr);
    odt.insert(ODT(l,r,val));
    ans+=val*(r-l+1);
}
void add(int l,int r,LL val) {
    set<ODT>::iterator itr=split(r+1),itl=split(l);
    for(set<ODT>::iterator it=itl; it!=itr; it++) it->val+=val;
}
LL sum(int l,int r) {
    set<ODT>::iterator itr=split(r+1),itl=split(l);
    LL res=0;
    for(set<ODT>::iterator it=itl; it!=itr;it++) res+=(it->rr-it->ll+1)*it->val;
    return res;
}
LL rank(int l, int r, int k){
    vector<pair<LL, int> >vec(0);
    set<ODT>::iterator itr=split(r+1),itl=split(l);
    for(set<ODT>::iterator it=itl;it!=itr;it++)vec.push_back(make_pair(it->val,it->rr-it->ll+1));
    sort(vec.begin(),vec.end());
    for (vector<pair<LL,int> >::iterator it=vec.begin();it!=vec.end();it++) if((k-=it->second)<=0) return it->first;
    return -1; //note:if there are negative numbers, return another impossible number.
}
int n,m,l,r,op;
int main() {
    scanf("%d%d",&n,&m);
    odt.insert(ODT(1,n,1));
    ans=n;
    while(m--) {
        scanf("%d%d%d",&l,&r,&op);
        if(op==1) assign_new(l,r,0);
        else assign_new(l,r,1);
        printf("%d\n",ans);
    }
    return 0;
}

Chtholly_tree

原文：https://www.cnblogs.com/STOGMH/p/11844736.html