Templates for XCPC - 数据结构（一）

二维差分

void insert(int x1,int y1,int x2,int y2,int c){
    d[x1][y1]+=c;
    d[x2+1][y1]-=c;
    d[x1][y2+1]-=c;
    d[x2+1][y2+1]+=c;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
    d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1];

ST 表

lg[1]=0;lg[2]=1;for(int i=3;i<=n;i++)lg[i]=lg[i/2]+1;
for(int i=1;i<=n;i++)f[i][0]=a[i];
for(int k=1;k<=20;k++){
	for(int i=1;i+(1<<k)-1<=n;i++){
		f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
	}
}
while(m--){
	int l,r;l=read();r=read();
	int s=lg[r-l+1];
	cout<<max(f[l][s],f[r-(1<<s)+1][s])<<'\n';
}

树状数组

#define lowbit(x) ((x)&(-(x)))
void add(int x,int v){
	for(int i=x;i<=n;i+=lowbit(i))tree[i]+=v;
}
int query(int x){
	int ret=0;
	for(int i=x;i;i-=lowbit(i))ret+=tree[i];
	return ret;
}

笛卡尔树

for(int i=1;i<=n;i++){
    int k=top;
    while(k&&a[stk[k]]<a[i])k--;//max
    if(k)rs[stk[k]]=i;
    if(k<top)ls[i]=stk[k+1];
    stk[++k]=i;
    top=k;
}

珂朵莉树

struct Node {
    int l,r;
    mutable int v;
    Node(const int& il,const int& ir,const int& iv):l(il),r(ir),v(iv){};
    bool operator<(const Node &t)const{return l<t.l;}
};
set<Node> odt;
auto split(int x){
    auto it=odt.lower_bound(Node(x,0,0));
    if(it!=odt.end()&&it->l==x)return it;--it;
    int l=it->l,r=it->r,v=it->v;
    odt.erase(it);
    odt.insert(Node(l,x-1,v));
    return odt.insert(Node(x,r,v)).first;
}
void assign(int l,int r,int v){ //区间赋值
    auto itr=split(r+1),itl=split(l);
    odt.erase(itl,itr);
    odt.insert(Node(l,r,v));
}
void perform(int l,int r){ //遍历区间进行操作
    auto itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl){
        int l=itl->l,r=itl->r,v=itl->v;
        // ...
    }
}