Untitled

杂项

优化指令

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")

8e9的暴力, CF上跑了733ms...

适用于常数小的多重循环暴力, 建议热身赛的时候测试下能不能用

重载运算符

struct cmp{
	bool operator ()(const Node & a,const Node & b)const{
		return (a.v == b.v?a.l < b.l:a.v < b.v);
	}
};
set<Node,cmp>odt2;

快读

struct Precision{
    int x;Precision(int a){
    x=a;}};struct SW{
    int x;SW(int a){
    x=a;}};struct SF{
    int x;SF(int a){
    x=a;}};
#define Set(x,y,z) SW(x)<<SF(y)<<z<<SW(0)
struct IO{
     
    #define Tp template<typename T>
    #define _D isdigit(c=gc())
    #define _A f|=eb;if(f)_R
    #define _R return *this
    #define _G p1==p2&&(p2=(p1=B)+fread(B,1,S,stdin),p1==p2)?EOF:*p1
    #define _T(x) while(st[++st[0]]=x%10+'0',x/=10)
    #define _O operator
    static const int S=1<<21;char B[S],*p1,*p2,sf,t;int st[105],H,bs,sw;bool eb,f;char nex(){
    return _G;}IO(){
    bs=6;sf=eb=sw=0;}
    IO& _O >> (char&c){
    _A;while(T(c=gc())){
    _A;}_R;}char gc(){
    t=(_G++);t=='\r'&&nex()=='\n'&&(gc());t==EOF&&(eb=1);return t;}
    IO& _O >> (string&s){
    _A;s="";char c;while(T(c=gc())){
    _A;}while(s+=c,!T(c=gc()));_R;}IO& _O << (Precision x){
    bs=x.x;_R;}
    IO& _O >> (char*c){
    _A;while(T(*c=gc())){
    _A;}while(!T(*++c=gc()));*c=0;_R;}int P(char c){
    return c=='\n'||c=='\r'||c==EOF;}
    IO& _O >> (double&x){
    _A;x=0;bool F=0;char c;while(!_D){
    F^=(c=='-');_A;}while(x=x*10+(c^48),_D&&(P(c),1));if(c^'.')_R;c=gc();
    double k=1;while(x+=(c^48)*(k*=0.1),_D);F&&(x=-x);_R;}void pu(int x){
    while(x-->0)pc(sf);}IO& _O << (SW x){
    sw=x.x;_R;}
    Tp IO& _O >> (T&x){
    _A;x=0;bool F=0;char c;while(!_D){
    F^=(c=='-');_A;}while(x=(x<<3)+(x<<1)+(c^48),_D);F&&(x=-x);_R;}
    IO& _O << (const string &s){
    int l=s.length();pu(sw-l);for(int i=0;i<l;i++)pc(s[i]);_R;}IO& _O << (const char c){
    pc(c);_R;}
    IO& _O << (char*c){
    int l=strlen(c);pu(sw-l);for(int i=0;i<l;i++)pc(c[i]);_R;}void CL(){
    fwrite(B,1,H,stdout);H=0;}
    IO& _O << (const char*c){
    int l=strlen(c);pu(sw-l);for(int i=0;i<l;i++)pc(c[i]);_R;}IO& _O << (SF x){
    sf=x.x;_R;}
    IO& _O << (double x){
    x<0&&(st[++st[0]]='-',x=-x);double t=0.5;for(int i=1;i<=bs;i++)t*=0.1;x+=t;ll y=x;_T(y);pu(sw-st[0]-
        bool(bs)-bs);while(st[0])pc(st[st[0]--]);x-=ll(x);if(bs)pc('.');for(int i=1;i<=bs;i++)pc(int(x*=10)+'0'),x-=int(x);_R;}
    Tp IO& _O << (T x){
    x<0&&(pc('-'),x=-x);_T(x);pu(max(sw-st[0],0));while(st[0])pc(st[st[0]--]);_R;}_O bool()const{
    return !f;}
    IO& getline(string&s){
    _A;s="";char c=gc();if(!P(c))while(s+=c,!P(c=gc()));_R;}void pc(const char c){
    H==S&&(CL(),0);B[H++]=c;}
    IO& getline(char*c){
    _A;*c=gc();if(!P(*c))while(!P(*++c=gc()));*c=0;_R;}int T(char c){
    return c==' '||P(c);}~IO(){
    CL();}
}fin,fout;

Bitset

常用方法

_Find_first() 返回第一个1的位置

_Find_next(x) 返回\(x\)后第一个1的位置

set(x) 将第\(x\)位设为1. 不加参数则全部置1

reset(x) 将第\(x\)为设为0. 不加参数则全部置0.

filp(x) 将第\(x\)位翻转. 不加参数则全部翻转.

RMQ问题

ST表

struct STable{
	int ST[50005][20];
	bool ismax;
	void ST_init(){
		for(int i = 1;i <= n;i++)ST[i][0] = inital[i];
		for(int j = 1;(1<<j) <= n;j++)
			for(int i = 1;i +(1<<j) - 1<= n;i++){
				if(ismax)ST[i][j] = max(ST[i][j - 1],ST[i + (1<<(j - 1))][j - 1]);
				else ST[i][j] = min(ST[i][j - 1],ST[i + (1<<(j - 1))][j - 1]);
		}
	}
	int query(int l, int r){
		int k = log2(r-l+1);
		if(ismax)return max(ST[l][k],ST[r - (1<<k) + 1][k]);
		else return min(ST[l][k],ST[r - (1<<k) + 1][k]);
	}
};

Fenwick树

int BIT[5000005],n,m;
inline int lowbit(int x){
	return x&-x;
}
int sum(int index){
	int tmp = 0;
	while(index > 0){
		tmp += BIT[index];
		index -= lowbit(index);
	}
	return tmp;
}
void add(int index,int x){
	while(index <= n){
		BIT[index] += x;
		index += lowbit(index); 
	}
}

求k小值:

int kth(int k){
	int tans = 0,tcnt = 0;
	for(int i = log2(n);i >= 0;i--){
		tans += (1<<i);
		if(tans >= n or tcnt + BIT[tans] >= k)tans -= (1<<i);
		else tcnt += BIT[tans];
	}
	return tans+1;
}

区间修改单点查询见P3368(懒到爆炸

珂朵莉树

珂朵莉树在存在区间赋值操作和数据随机的情况下可以维护复杂的区间询问. 复杂度一般为\(O(n\log n)\).

注意如果数据不随机, 但区间赋值操作很多(或者是全部区间赋值没有查询)也可用珂朵莉树维护.

struct Node{
    //节点,表示区间[l,r]的值为v
	ll l,r;
	mutable ll v;//必须加mutable, 否则无法修改v
	Node(ll l,ll r,ll v):l(l),r(r),v(v){}
	bool operator < (const Node & x) const {
		return l < x.l;
	}
};
set<Node>odt;
auto split(int idx){
    //将区间[l,r] (其中l <= idx <= r)分裂为[l,idx-1]和[idx,r]两个区间并返回[idx,r]区间的迭代器
	auto it = odt.lower_bound(Node(idx,0,0));
	if(it != odt.end() and it->l == idx)return it;
	it--;
	int l = it->l,r = it->r,v = it->v;
	odt.erase(it);
	odt.insert(Node(l,idx-1,v));
	return odt.insert(Node(idx,r,v)).first;
}
void assign(int l,int r,int v){
    //将[l,r]赋值为v
	auto end = split(r+1),begin = split(l);//必须先r后l,否则会RE
	odt.erase(begin,end);
	odt.insert(Node(l,r,v));
}

维护各个区间的查询均可暴力. 以区间\(k\)小值和区间\(n\)次方和为例

区间\(k\)小值:

int kth(int l,int r,int k){
	auto end = split(r+1),begin = split(l);
	vector<Node>tmp;
	for(auto it = begin;it != end;it++)tmp.push_back(*it);
	sort(tmp.begin(),tmp.end(),cmp);
	for(auto it:tmp){
		k -= (it.r - it.l + 1);
		if(k <= 0)return it.v;
	}
	return -1;
}

求\(\sum_{i = l}^ra[i]^x \mod p\)

int PowSum(int l,int r,int x,int p){
	ll ans = 0;
	auto end = split(r+1),begin = split(l);
	for(auto it = begin;it != end;it++){
		ans = (ans + Pow(it->v,x,p)%p*(it->r - it->l + 1)%p)%p;
	}
	return ans;
}

线段树

因为我比较懒，所以这里有一堆弱智线段树方便复制= =

单点修改,区间查询,线性建树

调用init(n)初始化.传入一个数组建树.

树根标号为0.

下标从0开始

查询操作区间为[L,R).

struct segtree{
	//root idx:0
	//[L,R)
	int size = 1;
	vector<ll>sumv;
	void init(int n){
		while(size < n)size *= 2;
		sumv.assign(size*2,0);
	}
	inline int ls(int x){return (x<<1)|1;}
	inline int rs(int x){return (x<<1)+2;}
	void build(vector<ll> & in,int x,int lx,int rx){
		if(rx - lx == 1){
			if(lx < (int)in.size())sumv[x] = in[lx];
			return;
		}
		int m = (lx+rx)/2;
		build(in,ls(x),lx,m);
		build(in,rs(x),m,rx);
		sumv[x] = sumv[ls(x)] + sumv[rs(x)];
	}
	void build(vector<ll> & in){
		build(in,0,0,size);
	}
	void set(int idx,int v,int x,int lx,int rx){
		if(rx - lx == 1){
			sumv[x] = v;
			return;
		}
		int m = (lx+rx)/2;
		if(idx < m)set(idx,v,ls(x),lx,m);
		else set(idx,v,rs(x),m,rx);
		sumv[x] = sumv[ls(x)] + sumv[rs(x)];
	}
	void set(int idx,int v){
		set(idx,v,0,0,size);
	}
	ll sum(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		if(lx >= l and rx <= r)return sumv[x];
		int m = (lx+rx)/2;
		ll s1 = sum(l,r,ls(x),lx,m);
		ll s2 = sum(l,r,rs(x),m,rx);
		return s1+s2;
	}
	ll sum(int l,int r){
		return sum(l,r,0,0,size);
	}
};

区间内第一个大于等于x的值的下标

\(least(L,v)\)返回\([L,n)\)里第一个大于等于x的值的下标.如果题目求\([L,R]\)的话特判一下下标和R的关系就行.

小于等于与之类似

再次提醒,这种写法的线段树下标从0开始

int least(int l,int v,int x,int lx,int rx){
	if(rx <= l or maxv[x] < v)return INF;
	if(rx - lx == 1){
		if(maxv[x] >= v)return lx;
		else return INF;
	}
	int m = (lx + rx)/2;
	int a1 = least(l,v,ls(x),lx,m),a2 = INF;
	if(a1 == INF)a2 = least(l,v,rs(x),m,rx);
	return min(a1,a2);
}
int least(int l,int v){
	return least(l,v,0,0,size);
}

第k个1

给出一个0-1数组,求第k个1的下标.

int kth(int x){
	//return the idx of kth-one
	int u = 0;
	int k = x,l = 0,r = size;
	while(k){
		if(r - l == 1)return l;
		int lw = sumv[ls(u)],rw = sumv[rs(u)];
		int m = (l+r)/2;
		if(lw >= k){
			u = ls(u);
			r = m;
		}
		else{
			k -= lw;
			u = rs(u);
			l = m;
		} 
	}
	return l;
}

区间合并操作

例:求最大连续子段和.

记\(seg_x\)为区间\(x\)的最大连续子段和.\(pre_x\)为最大前缀和,\(suf_x\)为最大后缀和,\(sum_x\)为区间之和.

记\(ls\)为\(x\)的左儿子,\(rs\)为\(x\)的右儿子.

对于一个区间\(x\),它的\(seg\)有三种可能:左子区间的\(seg\),右子区间的\(seg\),两个子区间的公共部分.因此我们有: \[ seg_x = \max(seg_{ls},seg_{rs},suf_{ls}+pre_{rs}) \] 对于\(pre\)和\(suf\)我们有: \[ pre_x = max(pre_{ls},sum_{ls}+pre_{rs})\\ suf_x = max(suf_{rs},sum_{rs}+suf_{ls}) \] 其他区间信息的合并与此基本相同.(本题答案为\(seg[0]\))

struct segtree{
	//root idx:0
	//[L,R)
	int size = 1;
	vector<ll>sumv,pre,suf,seg;
	void init(int n){
		while(size < n)size *= 2;
		sumv.assign(size*2,0);
		pre.assign(size*2,0);
		suf.assign(size*2,0);
		seg.assign(size*2,0);
	}
	inline int ls(int x){return (x<<1)|1;}
	inline int rs(int x){return (x<<1)+2;}
	void set(int idx,int v,int x,int lx,int rx){
		if(rx - lx == 1){
			sumv[x] =  suf[x] = pre[x] = seg[x] = v;
			return;
		}
		int m = (lx+rx)/2;
		if(idx < m)set(idx,v,ls(x),lx,m);
		else set(idx,v,rs(x),m,rx);
		sumv[x] = sumv[ls(x)] + sumv[rs(x)];
		pre[x] = max(pre[ls(x)],sumv[ls(x)]+pre[rs(x)]);
		suf[x] = max(suf[rs(x)],sumv[rs(x)]+suf[ls(x)]);
		seg[x] = max({seg[ls(x)],seg[rs(x)],suf[ls(x)]+pre[rs(x)]});
	}
	void set(int idx,int v){
		set(idx,v,0,0,size);
	}
};

区间加 单点查询

差分

//P-3-E 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6+10; 
struct Fenwick{
	int size = 1;
	ll BIT[maxn];
	void init(int n){
		size = n+1;
//		BIT.assign(n+1,0);
	}
	inline int lowbit(int x){
		return x & -x;
	}
	ll sum(int d){
		ll tans = 0;
		while(d){
			tans += BIT[d];
			d -= lowbit(d); 
		}
		return tans;
	}
	void add(int d,ll v){
		while(d <= size){
//			cout << d << endl;
			BIT[d] += v;
			d += lowbit(d);
		}
	}
	void add(int l,int r,int v){
		add(l,v);
		add(r+1,-v);
	}
}; 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	Fenwick fen;
	int n,m;
	cin >> n >> m;
	fen.init(n);
	while(m--){
		int opt,l,r,v;
		cin >> opt;
		if(opt == 1){
			cin >> l >> r >> v;
			l++;
//			r--;
			fen.add(l,r,v);
		}
		else{
			cin >> v;
			v++;
			cout << fen.sum(v)<< endl;
		}
	}
	return 0;
}

懒标记

struct segtree{//lazy tag,sum
	int size = 1;
	vector<ll>addv;
	void init(int n){
		while(size < n)size *= 2;
//		sumv.assign(size*2,0);
		addv.assign(size*2,0);
	}
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2;
	} 
	void build(vector<int> & in,int x,int lx,int rx){
		if(rx - lx == 1){
			addv[x] = in[lx];
			return;
		}
		int m = (lx+rx)/2;
		build(in,ls(x),lx,m);
		build(in,rs(x),rx,m);
	}
	void build(vector<int> & in){
		build(in,0,0,size);
	}
	void add(int l,int r,int v,int x,int lx,int rx){
		if(lx >= r or l >= rx)return;
		if(l <= lx and rx <= r){
			addv[x] += v;
			return;
		}
		int m = (lx+rx)/2;
		add(l,r,v,ls(x),lx,m);
		add(l,r,v,rs(x),m,rx);
	}
	void add(int l,int r,int v){
		add(l,r,v,0,0,size);
	}
	ll sum(int idx,int x,int lx,int rx){
		if(rx - lx == 1)return addv[x];
		int m = (lx+rx)/2;
		if(idx < m)return addv[x] + sum(idx,ls(x),lx,m);
		else return addv[x] + sum(idx,rs(x),m,rx);
	}
	ll sum(int idx){
		return sum(idx,0,0,size);
	}
};

区间修改,区间查询

维护如下操作:

\(A \space l \space r \space v\)：对区间\([L,R]\)进行操作\(A(l,r,v)\)

\(B \space l \space r\): 查询\(B(l,r)\)的值

\(A,B\)两种操作需要满足结合律;\(A\)需要满足交换律(如果不满足则需要懒标记).\(A\)与\(B\)需满足分配律

形式化地,设\(\otimes\)为操作\(A\),\(\odot\)为操作\(B\),线段树维护的操作需要满足:

1. \[ A \otimes B\otimes C = A \otimes (B \otimes C)\\ A \odot B \odot C = A \odot (B \odot C) \] { }

2. \[ A \otimes B = B \otimes A \]

3. \[ (A \otimes C) \odot (B \otimes C) = (A \odot B) \otimes C \]

区间加,区间最小值

struct Segtree{
	int siz = 1;
	vector<ll>addv,minv;
	const ll INF = 1e18;
	void init(int n){
		while(siz < n)siz *= 2;
		minv.assign(siz*2,0ll);
		addv.assign(siz*2,0ll);
	}
	inline int ls(int x){return (x<<1)+1;}
	inline int rs(int x){return (x<<1)+2;}
	void pushup(int x){
		minv[x] = min(minv[ls(x)],minv[rs(x)]);
	}
	void pushdown(int x,int lx,int rx){
		if(rx - lx == 1)return;
		ll & v = addv[x];
		if(v){
			addv[ls(x)] += v;addv[rs(x)] += v;
			minv[ls(x)] += v;
			minv[rs(x)] += v;
			v = 0;
		}
	}
	void add(int l,int r,int v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		if(rx - lx > 1)pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			minv[x] += v;
			addv[x] += v;
			return;
		}
		int m = (lx+rx)/2;
		add(l,r,v,ls(x),lx,m);
		add(l,r,v,rs(x),m,rx);
		pushup(x);
		return;
	}
	void add(int l,int r,int v){
		add(l,r,v,0,0,siz);
	}
	ll Min(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return INF;
		if(rx - lx > 1)pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			return minv[x];
		}
		int m = (lx+rx)/2;
		ll m1 = Min(l,r,ls(x),lx,m);
		ll m2 = Min(l,r,rs(x),m,rx);
		pushup(x);
		return min(m1,m2);
	}
	ll Min(int l,int r){
		return Min(l,r,0,0,siz);
	}
}seg;

区间乘,区间求和

初始数组均为1.

struct segtree{
	int n,size = 1;
	vector<ll>sumv,mulv;
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2;
	}
	void build(int x,int lx,int rx){
		sumv[x] = rx - lx;
		if(rx - lx == 1)return;
		int m = (lx+rx)/2;
		build(ls(x),lx,m);
		build(rs(x),m,rx);
	}
	void build(){
		build(0,0,size);
	}
	void init(int n){
		while(size < n){
			size *= 2;
		}
		sumv.assign(size*2,0ll);
		mulv.assign(size*2,1ll);
		build();
	}
	void apply(int x,ll v){
		mulv[x] = mulv[x]*v%mod;
		sumv[x] = sumv[x]*v%mod;
	}
	void pushup(int x){
		sumv[x] = (sumv[ls(x)] + sumv[rs(x)])%mod*mulv[x]%mod;
	}
	void mul(int l,int r,ll v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		if(l <= lx and rx <= r){
			apply(x,v);
			return;
		}
		int m = (lx+rx)/2;
		mul(l,r,v,ls(x),lx,m);
		mul(l,r,v,rs(x),m,rx);
		pushup(x);
	}
	void mul(int l,int r,int v){
		mul(l,r,v,0,0,size);
	}
	ll sum(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		if(l <= lx and rx <= r){
			return sumv[x];
		}
		int m = (lx+rx)/2;
		ll s1 = sum(l,r,ls(x),lx,m);
		ll s2 = sum(l,r,rs(x),m,rx);
		return (s1+s2)%mod*mulv[x]%mod;
	}
	ll sum(int l,int r){
		return sum(l,r,0,0,size);
	}
};

区间加,区间求和

struct segtree{
	int size = 1;
	vector<ll>sumv,addv;
	inline int ls(int x){return x*2 + 1;}
	inline int rs(int x){return x*2 + 2;}
	void init(int n){
		while(size < n)size *= 2;
		sumv.assign(size * 2,0ll);
		addv.assign(size * 2,0ll);
	}
	void pushup(int x){
		sumv[x] = sumv[ls(x)] + sumv[rs(x)];
	}
	void pushdown(int x,int lx,int rx){
		ll & v = addv[x];
		if(v){
			int len = (rx - lx) / 2;
			sumv[ls(x)] += v * len;
			sumv[rs(x)] += v * len;
			addv[ls(x)] += v;
			addv[rs(x)] += v;
			v = 0;
		}
	}
	void add(int l,int r,int v,int x,int lx,int rx){
		if(lx >= r or l >= rx)return;
		if(rx - lx > 1)pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			sumv[x] += (rx - lx) * v;
			addv[x] += v;
			return;
		}
		int m = (lx + rx) / 2;
		add(l,r,v,ls(x),lx,m);
		add(l,r,v,rs(x),m,rx);
		pushup(x);
	}
	void add(int l,int r,int v){
		add(l,r,v,0,0,size);
	}
	ll sum(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		if(rx - lx > 1)pushdown(x,lx,rx);
		if(l <= lx and rx <= r)return sumv[x];
		int m = (lx + rx) / 2;
		ll s1 = sum(l,r,ls(x),lx,m);
		ll s2 = sum(l,r,rs(x),m,rx);
		pushup(x);
		return s1 + s2;
	}
	ll sum(int l,int r){
		return sum(l,r,0,0,size);
	}
}seg;

维护等差数列(区间加等差数列,单点查询)

​ 由于\(A_n = A_{n-1} + d\)， 维护一个差分数列即可.

• \(1 \space l \space r \space a \space d\)： 将\([L,R]\)加上首项\(a\)公差\(d\)的等差数列
• \(2\space x\): 查询位置\(x\)的值

此处的add操作是闭区间

while(m--){
    int opt,l,r,a,d;
    cin >> opt >> l;
    if(opt == 1){
        cin >> r >> a >> d;
        seg.add(l,l,a);
        seg.add(r+1,r+1,-a);
        seg.add(l+1,r,d);
        seg.add(r+1,r+1,-(r-l)*d);
    }
    else cout << seg.sum(1,l) << endl;
}

区间加, 区间平方和

维护squv[]代表平方和, 显然有 \[ squv[x] = v \cdot v \cdot len + 2 \cdot v \cdot sumv[x] \]

void pushup(int x){
	sumv[x] = (sumv[ls(x)] + sumv[rs(x)]) % p;
	squv[x] = (squv[ls(x)] + squv[rs(x)]) % p;
}
void pushdown(int x,int lx,int rx){
	ll & v = addv[x];
	if(v){
		if(v < 0)v = (v + p) % p;
		int len = (rx - lx) / 2;
		squv[ls(x)] = (squv[ls(x)] + v * v % p * len % p + 2 * sumv[ls(x)] * v % p) % p;
		squv[rs(x)] = (squv[rs(x)] + v * v % p * len % p + 2 * sumv[rs(x)] * v % p) % p;
		sumv[ls(x)] = (sumv[ls(x)] + v * len % p) % p;
		sumv[rs(x)] = (sumv[rs(x)] + v * len % p) % p;
		addv[ls(x)] = (addv[ls(x)] + v) % p;
		addv[rs(x)] = (addv[rs(x)] + v) % p;
		v = 0;
	}
}
void add(int l,int r,int v,int x,int lx,int rx){
	if(lx >= r or l >= rx)return;
	if(rx - lx > 1)pushdown(x,lx,rx);
	if(l <= lx and rx <= r){
		squv[x] = (squv[x] + (rx - lx) * v % p * v % p + 2 * sumv[x] * v % p) % p;
		sumv[x] = (sumv[x] + (rx - lx) * v % p) % p;
		addv[x] = (addv[x] + v) % p;
		return;
	}
	int m = (lx + rx) / 2;
	add(l,r,v,ls(x),lx,m);
	add(l,r,v,rs(x),m,rx);
	pushup(x);
}

区间加,区间大于x的第一个值

在线段树上二分即可

struct segtree{
	int size = 1;
	vector<ll>addv,maxv;
	void init(int n){
		while(size < n)size *= 2;
		addv.assign(size*2,0);
		maxv.assign(size*2,0);
	}
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2;
	}
	void pushup(int x){
		maxv[x] = max(maxv[ls(x)],maxv[rs(x)]) + addv[x];
	}
	void add(int l,int r,ll v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		if(l <= lx and rx <= r){
			addv[x] += v;
			maxv[x] += v;
			return;
		} 
		int m = (lx+rx)/2;
		add(l,r,v,ls(x),lx,m);
		add(l,r,v,rs(x),m,rx);
		pushup(x);
	}
	void add(int l,int r,ll v){
		add(l,r,v,0,0,size);
	}
	int least(int l,int v,int x,int lx,int rx,ll add){
		if(rx <= l or maxv[x] + add < v)return INF;
		if(rx - lx == 1){
			if(maxv[x] + add >= v)return lx;
			else return INF;
		}
		add += addv[x];
		int m = (lx + rx)/2;
		int a1 = least(l,v,ls(x),lx,m,add),a2 = INF;
		if(a1 == INF)a2 = least(l,v,rs(x),m,rx,add);
		return min(a1,a2);
	}
	int least(int l,int v){
		return least(l,v,0,0,size,addv[0]);
	}
};

区间懒标记

本节的区间懒标记均表示当前节点已经更新, 但当前节点的儿子节点未更新

区间赋值 区间最小值

const ll INF = 1e10+1;
struct segtree{
	int size = 1;
	const int NO_OPT = 1E9+10;
	vector<ll>setv,minv;
	void init(int n){
		while(size < n)size *= 2;
		setv.assign(size*2,0);
		minv.assign(size*2,0); 
	}
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2; 
	}
	void apply(ll & a,ll b){
		a = (b == NO_OPT?a:b);	
	}
	void pushdown(int x){
        if(setv[x] == NO_OPT)return;
		apply(setv[ls(x)],setv[x]);
		apply(minv[ls(x)],setv[x]);
		apply(setv[rs(x)],setv[x]);
		apply(minv[rs(x)],setv[x]);
		setv[x] = NO_OPT; 
	}
	void pushup(int x){
		minv[x] = min(minv[ls(x)],minv[rs(x)]);
	}
	void Set(int l,int r,ll v,int x,int lx,int rx){
		if(rx - lx > 1)pushdown(x);
		if(l >= rx or lx >= r)return;
		if(l <= lx and rx <= r){
			apply(setv[x],v);
			apply(minv[x],v);
			return;
		}
		int m = (lx+rx)/2;
		Set(l,r,v,ls(x),lx,m);
		Set(l,r,v,rs(x),m,rx);
		pushup(x);
	}
	void Set(int l,int r,ll v){
		Set(l,r,v,0,0,size);
	}
	ll Min(int l,int r,int x,int lx,int rx){
		if(rx - lx > 1)pushdown(x);
		if(l >= rx or lx >= r)return INF;
		if(l <= lx and rx <= r)return minv[x];
		int m = (lx+rx)/2;
		ll m1 = Min(l,r,ls(x),lx,m);
		ll m2 = Min(l,r,rs(x),m,rx);
		return min(m1,m2);
	}
	ll Min(int l,int r){
		return Min(l,r,0,0,size);
	}
}; 

区间赋值 区间加

struct segtree{
	int size = 1;
	vector<ll>sumv,setv;
	const int NO_OPT = INF+1;
	void init(int n){
		while(size < n)size *= 2;
		sumv.assign(size*2,0);
		setv.assign(size*2,NO_OPT);
	}
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2;
	}
	inline void apply(ll & a,ll b){
		a = (b == NO_OPT?a:b);
	}
	void pushdown(int x,int lx,int rx){
		int len = rx - lx;
		if(len == 1 or setv[x] == NO_OPT)return;
		len /= 2;
		apply(setv[ls(x)],setv[x]);
		apply(sumv[ls(x)],setv[x]*len);
		apply(setv[rs(x)],setv[x]);
		apply(sumv[rs(x)],setv[x]*len);
		setv[x] = NO_OPT;
	}
	void pushup(int x){
		sumv[x] = sumv[ls(x)] + sumv[rs(x)];
	}
	void Set(int l,int r,ll v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			setv[x] = v;
			sumv[x] = v*(rx - lx);
			return;
		}
		int m = (lx+rx)/2;
		Set(l,r,v,ls(x),lx,m);
		Set(l,r,v,rs(x),m,rx);
		pushup(x);
	}
	void Set(int l,int r,ll v){
		Set(l,r,v,0,0,size);
	}
	ll sum(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			return sumv[x];
		}
		int m = (lx+rx)/2;
		ll s1 = sum(l,r,ls(x),lx,m);
		ll s2 = sum(l,r,rs(x),m,rx);
		return s1+s2;
	}
	ll sum(int l,int r){
		return sum(l,r,0,0,size);
	}
};

区间赋值 最大连续子段和(区间合并)

struct segtree{
	int size = 1;
	vector<ll>sumv,setv;
	vector<ll>prev,sufv,segv;
	const int NO_OPT = INF+1;
	void init(int n){
		while(size < n)size *= 2;
		sumv.assign(size*2,0);
		setv.assign(size*2,NO_OPT);
		prev.assign(size*2,0);
		sufv.assign(size*2,0);
		segv.assign(size*2,0);
	}
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2;
	}
	inline void apply(ll & a,ll b){
		a = (b == NO_OPT?a:b);
	}
	void pushdown(int x,int lx,int rx){
		int len = rx - lx;
		if(len == 1 or setv[x] == NO_OPT)return;
		len /= 2;
		apply(setv[ls(x)],setv[x]);
		apply(sumv[ls(x)],setv[x]*len);
		apply(setv[rs(x)],setv[x]);
		apply(sumv[rs(x)],setv[x]*len);
		if(setv[x] != NO_OPT){
			prev[ls(x)] = prev[rs(x)] = setv[x]*len;
			sufv[ls(x)] = sufv[rs(x)] = setv[x]*len;
			segv[ls(x)] = segv[rs(x)] = setv[x]*len;
		}
		setv[x] = NO_OPT;
	}
	void pushup(int x){
		sumv[x] = sumv[ls(x)] + sumv[rs(x)];
		sufv[x] = max(sufv[rs(x)],sufv[ls(x)] + sumv[rs(x)]);
		prev[x] = max(prev[ls(x)],prev[rs(x)] + sumv[ls(x)]);
		segv[x] = max({segv[ls(x)],segv[rs(x)],prev[rs(x)] + sufv[ls(x)]}); 
	}
	void Set(int l,int r,ll v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			setv[x] = v;
			sumv[x] = v*(rx - lx);
			if(v > 0){
				segv[x] = prev[x] = sufv[x] = v*(rx - lx);
			}
			else{
				segv[x] = prev[x] = sufv[x] = 0;
			}
			return;
		}
		int m = (lx+rx)/2;
		Set(l,r,v,ls(x),lx,m);
		Set(l,r,v,rs(x),m,rx);
		pushup(x);
	}
	void Set(int l,int r,ll v){
		Set(l,r,v,0,0,size);
	}
	ll sum(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			return sumv[x];
		}
		int m = (lx+rx)/2;
		ll s1 = sum(l,r,ls(x),lx,m);
		ll s2 = sum(l,r,rs(x),m,rx);
		return s1+s2;
	}
	ll sum(int l,int r){
		return sum(l,r,0,0,size);
	}
};

区间取反 第k个值

用sum来维护区间取反,每取反一次有\(sum_x = len_x - sum_x\)

struct segtree{
	int size = 1;
	vector<ll>sumv;
	vector<bool>inv,tag;
	void init(int n){
		while(size < n)size *= 2;
		sumv.assign(size*2,0);
		inv.assign(size*2,0);
	}
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2;
	}
	void pushdown(int x,int lx,int rx){
		if(rx - lx == 1 or !inv[x])return;
		int len = (rx - lx)/2;
		sumv[ls(x)] = len - sumv[ls(x)];
		sumv[rs(x)] = len - sumv[rs(x)];
		inv[ls(x)] = !inv[ls(x)];
		inv[rs(x)] = !inv[rs(x)];
		inv[x] = !inv[x];
	}
	void pushup(int x){
		sumv[x] = sumv[ls(x)] + sumv[rs(x)];
	}
	void Inv(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			inv[x] = !inv[x];
			sumv[x] = (rx - lx) - sumv[x];
			return;
		}
		int m = (lx+rx)/2;
		Inv(l,r,ls(x),lx,m);
		Inv(l,r,rs(x),m,rx);
		pushup(x);
	}
	void Inv(int l,int r){
		Inv(l,r,0,0,size);
	}
	int kth(int l,int v,int x,int lx,int rx){
		pushdown(x,lx,rx);
		if(l >= rx)return INF;
		if(rx - lx == 1){
			if(sumv[x] >= v)return lx;
			else return INF;
		}
		int m = (lx+rx)/2;
		if(sumv[ls(x)] > v)return kth(l,v,ls(x),lx,m);
		else return kth(l,v - sumv[ls(x)],rs(x),m,rx); 
	}
	int kth(int l,int v){
		return kth(l,v,0,0,size);
	}
};

多个懒标记的顺序问题

待补充.

区间加, 区间乘

设\(addv[]\)为加法懒标记, \(mulv[]\)为乘法懒标记. 我们人为规定乘法懒标记优先级大于加法. 即当\(sumv[x]\)和\(mulv[x]\)同时存在时, 认为\(sumv[x] = mulv[x]*sumv[x] + addv[x]\).

则更新标记时, 加法直接\(addv[x] += v\), 乘法需要同时影响\(addv\)和\(mulv\), 将二者同时乘\(v\).

struct Segtree{
	int siz = 1;
	vector<ll>mulv,addv,sumv;
	void init(int n){
		while(siz < n)siz *= 2;
		mulv.assign(siz*2,1ll);
		addv.assign(siz*2,0ll);
		sumv.assign(siz*2,0ll);
	}
	inline int ls(int x){return (x<<1)|1;}
	inline int rs(int x){return (x<<1)+2;}
	void pushdown(int x,int lx,int rx){
		ll len = (rx - lx)/2;
		ll & av = addv[x],& mv = mulv[x];
		sumv[ls(x)] = (sumv[ls(x)]*mv % p + av*len%p)%p; 
		sumv[rs(x)] = (sumv[rs(x)]*mv % p + av*len%p)%p; 
		mulv[ls(x)] = (mulv[ls(x)]*mv)%p;
		mulv[rs(x)] = (mulv[rs(x)]*mv)%p;
		addv[ls(x)] = (addv[ls(x)]*mv%p + av)%p;//规定乘法优先级大于加法
		addv[rs(x)] = (addv[rs(x)]*mv%p + av)%p;		
		av = 0,mv = 1;
	}
	void pushup(int x){
		sumv[x] = sumv[ls(x)] + sumv[rs(x)];
		sumv[x] %= p;
	}
	void add(int l,int r,int v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		if(rx - lx > 1)pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			sumv[x] = (sumv[x] + v*(rx - lx)%p)%p;
			addv[x] += v;
			addv[x] %= p;
			return;
		}
		int m = (lx+rx)/2;
		add(l,r,v,ls(x),lx,m);
		add(l,r,v,rs(x),m,rx);
		pushup(x);
	}
	void add(int l,int r,int v){
		r++;
		add(l,r,v,0,0,siz);
	}
	void mul(int l,int r,int v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		if(rx - lx > 1)pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			sumv[x] = sumv[x]*v%p;
			mulv[x] = (mulv[x]*v)%p;
			addv[x] = (addv[x]*v)%p;//规定乘法优先级大于加法
			return;
		}
		int m = (lx+rx)/2;
		mul(l,r,v,ls(x),lx,m);
		mul(l,r,v,rs(x),m,rx);
		pushup(x);
	}
	void mul(int l,int r,int v){
		r++;
		mul(l,r,v,0,0,siz);
	}
	ll sum(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		if(rx - lx > 1)pushdown(x,lx,rx);
		if(l <= lx and rx <= r)return sumv[x]%p;
		int m = (lx+rx)/2;
		ll s1 = sum(l,r,ls(x),lx,m);
		ll s2 = sum(l,r,rs(x),m,rx);
		return (s1+s2)%p;
	}
	ll sum(int l,int r){
		r++;
		return sum(l,r,0,0,siz);
	}
	void build(vector<int> & in,int x,int lx,int rx){
		if(rx - lx == 1){
			if(lx < (int)in.size())sumv[x] = in[lx]%p;
			return;
		}
		int m = (lx+rx)/2;
		build(in,ls(x),lx,m);
		build(in,rs(x),m,rx);
		pushup(x);
	}
	void build(vector<int> & in){
		build(in,0,0,siz);
	}
}seg;

区间加 区间赋值 区间求和

规定\(setv\)的优先级大于\(addv\), 即\(sumv[x] = setv[x] + addv[x]\). 在add时直接加即可, 但set要先覆盖掉之前的add操作.

struct segtree{
	int size = 1;
	vector<ll>setv,sumv,addv;
	const ll NO_OPT = LLONG_MAX; 
	void init(int n){
		while(size <= n)size *= 2;
		setv.assign(size*2,NO_OPT);
		sumv.assign(size*2,0);
		addv.assign(size*2,0);
	}
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2;
	}
	void pushdown(int x,int lx,int rx){
		if(rx - lx == 1)return;
		int len = (rx - lx)/2;
		if(setv[x] != NO_OPT){
			addv[ls(x)] = addv[rs(x)] = 0;
			setv[ls(x)] = setv[rs(x)] = setv[x];
			sumv[ls(x)] = sumv[rs(x)] = setv[x]*len;
			setv[x] = NO_OPT; 
		}
		if(addv[x]){
			addv[ls(x)] += addv[x];
			addv[rs(x)] += addv[x];
			sumv[ls(x)] += addv[x]*len;
			sumv[rs(x)] += addv[x]*len;
			addv[x] = 0;
		}
	}
	void pushup(int x,int len){
		sumv[x] = sumv[ls(x)] + sumv[rs(x)] + addv[x]*len;
	}
	void Set(int l,int r,ll v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			setv[x] = v;
			addv[x] = 0;
			sumv[x] = v*(rx - lx);
			return;
		}
		int m = (lx+rx)/2;
		Set(l,r,v,ls(x),lx,m);
		Set(l,r,v,rs(x),m,rx);
		pushup(x,rx - lx);
	}
	void Set(int l,int r,ll v){
		Set(l,r,v,0,0,size);
	}
	void add(int l,int r,ll v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			addv[x] += v;
			sumv[x] += v*(rx - lx);
			return;
		}
		int m = (lx+rx)/2;
		add(l,r,v,ls(x),lx,m);
		add(l,r,v,rs(x),m,rx);
		pushup(x,rx - lx);
	}
	void add(int l,int r,ll v){
		add(l,r,v,0,0,size);
	}
	ll sum(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			return sumv[x];
		}
		int m = (lx+rx)/2;
		ll s1 = sum(l,r,ls(x),lx,m);
		ll s2 = sum(l,r,rs(x),m,rx);
		return s1+s2;
	}
	ll sum(int l,int r){
		return sum(l,r,0,0,size);
	}
}; 

杂项

在01数组里寻找最长的一串连续0/1

strip(x = 起始位置,v = 0或1)

返回连续的0/1串终点的下一个位置.

int strip(int l,int prel,int pre,bool v,int x,int lx,int rx){
		if(rx - lx == 1){
			return lx;
		}
		pushdown(x,lx,rx);
		int m = (lx + rx) / 2;
		bool ok = 0;//1-goto [m,rx) 0-goto [lx,m)
		if(v and pre + sumv[ls(x)] - prel >= m - l)ok = 1;
		if(!v and (m - pre - sumv[ls(x)]) - (l - prel) >= m - l)ok = 1;
		if(ok)return strip(l,prel,pre + sumv[ls(x)],v,rs(x),m,rx);
		else return strip(l,prel,pre,v,ls(x),lx,m);
	}
	int strip(int x,bool v){
		//find longest continuous 0 or 1, return the next position.
		//00001111001 (index start from 1)
		//strip(5,1) will return 9
		int pre = sum(0,x-1);
		return strip(x,pre,0,v,0,0,siz);
	}

在01数组里寻找最高位的1

int high(int pre,int tot,int x,int lx,int rx){
	if(rx - lx == 1)return lx;
	pushdown(x,lx,rx);
	int m = (lx + rx) / 2;
	if(sumv[ls(x)] + pre < tot)return high(pre + sumv[ls(x)],tot,rs(x),m,rx);
	else return high(pre,tot,ls(x),lx,m);
}
int high(){
	// find highest 1
	int tot = sum(1,siz - 1);
	return high(0,tot,0,0,siz);
}

动态开点

新增一个结构体Node, 存每个节点的左右儿子下标ls rs, 其余与普通线段树一致. 开空间时可以开得尽可能大. 设有\(m\)个询问, 区间长度最大值为\(n\), 空间复杂度为\(O(m\log n)\)

struct Node{
	int ls,rs;
	Node(){ls = rs = 0;}
};

int cnt = 0
void init(int n){
	while(size < n)size *= 2;//此处的n代表了区间的最大范围
	setv.assign(maxc,NO_OPT);//注意此处是maxc不是size*2. maxc可以开得尽可能大
	minv.assign(maxc,0);
	node.assign(maxc,Node());
}
inline int ls(int x){
	int & v = node[x].ls;
	return v?v:v = ++cnt;
}
inline int rs(int x){
	int & v = node[x].rs;
	return v?v:v = ++cnt;
}

可持久化线段树

可持久化数组

\(ncnt\)为当前版本下标，添加新版本必须修改这个值

set(idx = 下标,v = 值,hisver = 要修改的历史版本,curver = 当前历史版本)

具体来说, \(hisv\)代表了要修改的历史版本号. 修改过后的数组会保存在\(curv\)中.

get(idx = 下标,Ver = 要查询的历史版本)

时空复杂度均为\(O(q\log n)\)

int Ls[maxc],Rs[maxc],sumv[maxc];
int hisn[maxn],ncnt = 0;
struct seg{
	int size = 1;
	void init(int n){
		while(size < n)size *= 2;
	}
	inline int ls(int x){return Ls[x]?Ls[x]:Ls[x] = ++ncnt;}
	inline int rs(int x){return Rs[x]?Rs[x]:Rs[x] = ++ncnt;}
	void set(int idx,int v,int r,int x,int lx,int rx){
		if(rx - lx == 1){
			sumv[x] = v;
			return;
		}
		int m = (lx + rx)/2;
		if(idx < m){
			Rs[x] = Rs[r]; 
			set(idx,v,ls(r),ls(x),lx,m);
		}
		else{
			Ls[x] = Ls[r];
			set(idx,v,rs(r),rs(x),m,rx);
		}
	}
	void set(int idx,int v,int hisv,int curv){
		set(idx,v,hisn[hisv],hisn[curv],0,size);
	}
	int get(int idx,int x,int lx,int rx){
		if(rx - lx == 1){
			return sumv[x];
		}
		int m = (lx+rx)/2;
		if(idx < m){
			return get(idx,ls(x),lx,m);
		}
		else return get(idx,rs(x),m,rx);
	}
	int get(int idx,int ver){
		return get(idx,hisn[ver],0,size);
	}
}seg;

主席树

查询静态区间k小值.

int Ls[maxc],Rs[maxc],sumv[maxc],hisn[maxc];//hisn[版本号] = 对应根节点
int oriv[maxn];//离散化前的值
int univ[maxn];//离散化后的值
int raw[maxn];
int ncnt;
struct segtree{//可持久化权值线段树
	int size = 1;
	void init(int n){while(size < n)size *= 2;}
	inline int ls(int x){return Ls[x]?Ls[x]:Ls[x] = ++ncnt;}
	inline int rs(int x){return Rs[x]?Rs[x]:Rs[x] = ++ncnt;}
	void pushup(int x){
		sumv[x] = sumv[ls(x)] + sumv[rs(x)];
	}
	void add(int idx,int v,int r,int x,int lx,int rx){
		if(rx - lx == 1){
			sumv[x] = sumv[r] + v; 
			return;
		}
		int m = (lx+rx)/2;
		if(idx < m){
			Rs[x] = Rs[r];
			add(idx,v,ls(r),ls(x),lx,m);
		}
		else{
			Ls[x] = Ls[r];
			add(idx,v,rs(r),rs(x),m,rx);
		}
		pushup(x);
	}
	void add(int idx,int v,int hisv,int curv){
		add(idx,v,hisn[hisv],hisn[curv],0,size);
	}
	int kth(int k,int r,int x,int lx,int rx){
		if(rx - lx == 1){
			return oriv[lx];
		}
		int m = (lx+rx)/2;
		int csum = sumv[ls(x)] - sumv[ls(r)];
		if(k <= csum)return kth(k,ls(r),ls(x),lx,m);
		else return kth(k - csum,rs(r),rs(x),m,rx);
	}
	int kth(int l,int r,int k){
		return kth(k,hisn[l-1],hisn[r],0,size);
	}
}seg;

离散化部分:

map<int,int>hsh;
int tmp = 0;
for(int i = 1;i <= n;i++){
	cin >> oriv[i];
	raw[i] = oriv[i];
	hsh[oriv[i]] = 1;
}
for(auto & it:hsh){it.second = ++tmp;}
for(int i = 1;i <= n;i++){
	univ[i] = hsh[oriv[i]];
	hisn[i] = ++ncnt;
	seg.add(univ[i],1,i-1,i);
}
for(int i = 1;i <= n;i++)oriv[univ[i]] = raw[i];
for(int i = 1;i <= m;i++){
	int l,r,k;
	cin >> l >> r >> k;
	cout << seg.kth(l,r,k) << endl;
}

求区间mex

const int maxc = 6e7 + 10;
int Ls[maxc],Rs[maxc],minv[maxc];
int hisn[maxn],ncnt = 0;
struct seg{
	int size = 1;
	void init(int n){
		while(size < n)size *= 2;
	}
	void pushup(int x){
		minv[x] = min(minv[ls(x)],minv[rs(x)]);
	}
	inline int ls(int x){return Ls[x]?Ls[x]:Ls[x] = ++ncnt;}
	inline int rs(int x){return Rs[x]?Rs[x]:Rs[x] = ++ncnt;}
	void set(int idx,int v,int r,int x,int lx,int rx){
		if(rx - lx == 1){
			minv[x] = v;
			return;
		}
		int m = (lx + rx)/2;
		if(idx < m){
			Rs[x] = Rs[r]; 
			set(idx,v,ls(r),ls(x),lx,m);
		}
		else{
			Ls[x] = Ls[r];
			set(idx,v,rs(r),rs(x),m,rx);
		}
		pushup(x);
	}
	void set(int idx,int v,int hisv,int curv){
		set(idx,v,hisn[hisv],hisn[curv],0,size);
	}
	int mex(int L,int R){
		//return mex in [L,R]
		return mex(L,hisn[R],0,size);
	}
	int mex(int L,int x,int lx,int rx){
		if(rx - lx == 1)return lx;
		int m = (lx + rx) / 2;
		if(minv[ls(x)] < L)return mex(L,ls(x),lx,m);
		else return mex(L,rs(x),m,rx);
	}
}seg;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.setf(ios::fixed,ios::floatfield);
	cout.precision(12);	 
	int n,q;
	cin >> n >> q;
	seg.init(n + 10);
	for(int i = 1;i <= n;i++){
		cin >> raw[i];
		if(raw[i] > n + 1)raw[i] = n + 1;//mex must <= n
		hisn[i] = ++ncnt;
		seg.set(raw[i],i,i-1,i);
	}
	while(q--){
		int l,r;
		cin >> l >> r;
		cout << seg.mex(l,r) << endl;
	}
	return 0;
}

势能线段树(Segment Tree Beats)

Part1: 区间最值&暴力修改

https://ac.nowcoder.com/acm/problem/226598

https://codeforces.com/blog/entry/57319

势能线段树则总时间复杂度为O(M×∣0势能时线段树操作时间复杂度∣+N×∣节点势能上限降低至0势能时间复杂度∣+M×∣线段树单次操作影响到的节点数目∣×∣操作额外提供的势能∣)

核心思想: 在能跳出的部分尽量跳出(如区间取min时, maxv[x] <= v即可跳出)

区间取min

给出\(n\)个初始值和\(m\)个操作:

0 l r v 对于$ i $, \(A_i = min(A_i,v)\)

1 l r查询区间\([L,R]\)最大值

2 l r查询区间\([L,R]\)的和

令\(maxv[]\)维护最大值, \(secv[]\)维护严格次大值, \(cntv[]\)维护最大值的个数. 每次区间取\(min\)分三种情况:

1. \(maxv[x] \leq v\), 直接忽略
2. \(secv[x] < v < maxv[x]\), 将最大值改为\(v\)即可.
3. \(v \leq secv[x]\), 无法判断如何修改, 暴力修改其子区间.

通过势能分析可得其复杂度为\(O(m \log n)\)

struct sgbt{
    int siz = 1;
    vector<int>maxv,cntv,secv,mintag;//cntv-区间最大值的数量
    vector<ll>sumv;
    void init(int n){
        while(siz < n)siz *= 2;
        maxv.assign(siz*2,0);
        cntv.assign(siz*2,0);
        secv.assign(siz*2,-1);
        sumv.assign(siz*2,0ll);
        mintag.assign(siz*2,-1);
    }
    inline int ls(int x){return (x<<1)|1;}
    inline int rs(int x){return (x<<1)+2;}
    void pushup(int x){
        sumv[x] = sumv[ls(x)] + sumv[rs(x)];
        if(maxv[ls(x)] == maxv[rs(x)]){
            maxv[x] = maxv[ls(x)];
            secv[x] = max(secv[ls(x)],secv[rs(x)]);
            cntv[x] = cntv[ls(x)] + cntv[rs(x)];
        }
        else if(maxv[ls(x)] > maxv[rs(x)]){
            maxv[x] = maxv[ls(x)],cntv[x] = cntv[ls(x)];
            secv[x] = max(maxv[rs(x)],secv[ls(x)]);
        }
        else{
            maxv[x] = maxv[rs(x)],cntv[x] = cntv[rs(x)];
            secv[x] = max(maxv[ls(x)],secv[rs(x)]);
        }
    }
    void pushdown(int x){
        int & v = mintag[x];
        if(v == -1)return;
        if(maxv[ls(x)] > v){
            sumv[ls(x)] += 1ll*cntv[ls(x)]*(v - maxv[ls(x)]);
            maxv[ls(x)] = v;
            mintag[ls(x)] = v;
        }
        if(maxv[rs(x)] > v){
            sumv[rs(x)] += 1ll*cntv[rs(x)]*(v - maxv[rs(x)]);
            maxv[rs(x)] = v;
            mintag[rs(x)] = v;
        }
        v = -1;
        return;
    }
    void smin(int l,int r,int v,int x,int lx,int rx){
        if(l >= rx or lx >= r)return;
        if(rx - lx > 1)pushdown(x);
        if(maxv[x] <= v)return;
        if(l <= lx and rx <= r){
            if(secv[x] < v){
                sumv[x] += 1ll*cntv[x]*(v - maxv[x]);
                maxv[x] = v;
                mintag[x] = v;
                return;
            }
        }
        int m = (lx+rx)/2;
        smin(l,r,v,ls(x),lx,m);
        smin(l,r,v,rs(x),m,rx);
        pushup(x);
    }
    void smin(int l,int r,int v){
        r++;
        smin(l,r,v,0,0,siz);
    }
    int Max(int l,int r,int x,int lx,int rx){
        if(l >= rx or lx >= r)return -1;
        if(rx - lx > 1)pushdown(x);
        if(l <= lx and rx <= r)return maxv[x];
        int m = (lx+rx)/2;
        int m1 = Max(l,r,ls(x),lx,m);
        int m2 = Max(l,r,rs(x),m,rx);
        pushup(x);
        return max(m1,m2);
    }
    int Max(int l,int r){
        r++;
        return Max(l,r,0,0,siz);
    }
    ll sum(int l,int r,int x,int lx,int rx){
        if(l >= rx or lx >= r)return 0;
        if(rx - lx > 1)pushdown(x);
        if(l <= lx and rx <= r)return sumv[x];
        int m = (lx+rx)/2;
        ll s1 = sum(l,r,ls(x),lx,m);
        ll s2 = sum(l,r,rs(x),m,rx);
        pushup(x);
        return s1+s2;
    }
    ll sum(int l,int r){
        r++;
        return sum(l,r,0,0,siz);
    }
    void build(vector<int> & in,int x,int lx,int rx){
        if(rx - lx == 1){
            if(lx < (int)in.size()){
                sumv[x] = maxv[x] = in[lx];
                cntv[x] = 1;
            }
            return;
        }
        int m = (lx+rx)/2;
        build(in,ls(x),lx,m);
        build(in,rs(x),m,rx);
        pushup(x);
    }
    void build(vector<int> & in){
        build(in,0,0,siz);
    }
};

暴力修改维护区间操作+单点修改

例题: CF438D - The Child and Sequence

区间取模, 区间求和, 单点赋值.

我们定义每个数被取模的最大次数和为线段树的总势能. 容易发现一个数\(a\)的势能为\(\log a\), 线段树的总势能为\(n \log a\). 故我们暴力修改最多只需暴力修改\(n\log a\)次. 对区间开根号. 总复杂度\(O(n \log^2 n)\)

struct Segtree{
	int siz = 1;
	const int NO_OPT = INT_MAX;
	vector<ll>sumv,maxv,modv;
	void init(int n){
		while(siz < n)siz *= 2;
		sumv.assign(siz*2,0);
		maxv.assign(siz*2,0);
		// modv.assign(siz*2,NO_OPT);
	}
	inline int ls(int x){return (x<<1)|1;}
	inline int rs(int x){return (x<<1)+2;}
	// void pushdown(int x,int lx,int rx){

	// }
	void build(vector<int> & in,int x,int lx,int rx){
		if(rx - lx == 1){
			if(lx < (int)in.size()){
				sumv[x] = in[lx];
				maxv[x] = in[lx];
			}
			return;
		}
		int m = (lx+rx)/2;
		build(in,ls(x),lx,m);
		build(in,rs(x),m,rx);
		pushup(x);
	}
	void build(vector<int> & in){
		build(in,0,0,siz);
	}
	void pushup(int x){
		sumv[x] = (sumv[ls(x)] + sumv[rs(x)]);
		maxv[x] = max(maxv[ls(x)],maxv[rs(x)]);
	}
	void set(int idx,int v,int x,int lx,int rx){
		if(idx >= rx or lx > idx)return;
		if(rx - lx == 1 and lx == idx){
			maxv[x] = v;
			sumv[x] = v;
			return;
		}
		int m = (lx+rx)/2;
		set(idx,v,ls(x),lx,m);
		set(idx,v,rs(x),m,rx);
		pushup(x);
	}
	void set(int idx,int v){
		set(idx,v,0,0,siz);
	}
	void mod(int l,int r,int p,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		if(maxv[x] < p)return;
		if(l <= lx and rx <= r and rx - lx == 1){
			sumv[x] %= p;
			maxv[x] = sumv[x];
			return;
 		}
 		int m = (lx+rx)/2;
 		mod(l,r,p,ls(x),lx,m);
 		mod(l,r,p,rs(x),m,rx);
 		pushup(x);
	}
	void mod(int l,int r,int p){
		r++;
		mod(l,r,p,0,0,siz);
	}
	ll sum(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		if(l <= lx and rx <= r)return sumv[x];
		int m = (lx+rx)/2;
		ll s1 = sum(l,r,ls(x),lx,m);
		ll s2 = sum(l,r,rs(x),m,rx);
		return s1+s2;
	}
	ll sum(int l,int r){
		r++;
		return sum(l,r,0,0,siz);
	}
}seg;

暴力修改维护区间操作+区间修改

区间开根, 区间加, 区间求和.

定义势能为\(C = maxv[x] - minv[x]\). 当势能为0时说明该段区间所有数均相同, 可将区间开根(或其他类似操作)改为区间赋值.

时间复杂度仍为\(O(n\log^2n)\)

struct Segtree{
	int siz = 1;
	const ll NO_OPT = LLONG_MAX;
	vector<ll>maxv,minv,sumv,addv,setv;
	void init(int n){
		while(siz < n)siz *= 2;
		maxv.assign(siz*2,0ll);
		minv.assign(siz*2,0ll);
		sumv.assign(siz*2,0ll);
		addv.assign(siz*2,0ll);
		setv.assign(siz*2,NO_OPT);
	}
	inline int ls(int x){return (x<<1)+1;}
	inline int rs(int x){return (x<<1)+2;}
	void pushup(int x){
		sumv[x] = sumv[ls(x)] + sumv[rs(x)];
		maxv[x] = max(maxv[ls(x)],maxv[rs(x)]);
		minv[x] = min(minv[ls(x)],minv[rs(x)]);
	}
	void pushdown(int x,int lx,int rx){
		if(rx - lx == 1)return;
		ll len = (rx - lx)/2;
		if(setv[x] != NO_OPT){
			ll & v = setv[x];
			sumv[ls(x)] = sumv[rs(x)] = v*len;
			setv[ls(x)] = setv[rs(x)] = v;
			maxv[ls(x)] = minv[ls(x)] = maxv[rs(x)] = minv[rs(x)] = v;
			addv[ls(x)] = addv[rs(x)] = 0;
			v = NO_OPT;
		}
		if(addv[x]){
			ll & v = addv[x];
			addv[ls(x)] += v;addv[rs(x)] += v;
			sumv[ls(x)] += v*len;sumv[rs(x)] += v*len;
			maxv[ls(x)] += v;maxv[rs(x)] += v;
			minv[ls(x)] += v;minv[rs(x)] += v;
			v = 0;
		}
	}
	void add(int l,int r,ll v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		if(rx - lx > 1)pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			addv[x] += v;
			minv[x] += v;maxv[x] += v;
			sumv[x] += v*(rx-lx);
			return;
		}
		int m = (lx+rx)/2;
		add(l,r,v,ls(x),lx,m);
		add(l,r,v,rs(x),m,rx);
		pushup(x);
		return;
	}
	void add(int l,int r,ll v){
		r++;
		add(l,r,v,0,0,siz);
	}
	void sqr(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		if(rx - lx > 1)pushdown(x,lx,rx);
		if(l <= lx and rx <= r and maxv[x] == minv[x]){
			setv[x] = sqrt(maxv[x]);
			addv[x] = 0;
			maxv[x] = minv[x] = setv[x];
			sumv[x] = setv[x]*(rx - lx);
			return;
		}
		int m = (lx+rx)/2;
		sqr(l,r,ls(x),lx,m);
		sqr(l,r,rs(x),m,rx);
		pushup(x);
	}
	void sqr(int l,int r){
		r++;
		sqr(l,r,0,0,siz);
	}
	ll sum(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		if(rx - lx > 1)pushdown(x,lx,rx);
		if(l <= lx and rx <= r)return sumv[x];
		int m = (lx+rx)/2;
		ll s1 = sum(l,r,ls(x),lx,m);
		ll s2 = sum(l,r,rs(x),m,rx);
		pushup(x);
		return s1+s2;
	}
	ll sum(int l,int r){
		r++;
		return sum(l,r,0,0,siz);
	}
	void build(vector<int> & in,int x,int lx,int rx){
		if(rx - lx == 1){
			if(lx < (int)in.size()){
				minv[x] = maxv[x] = sumv[x] = in[lx];
			}
			return;
		}
		int m = (lx+rx)/2;
		build(in,ls(x),lx,m);
		build(in,rs(x),m,rx);
		pushup(x);
	}
	void build(vector<int> & in){
		build(in,0,0,siz);
	}
}seg;

Part2: 区间历史最值维护

一些例题

A

区间赋值为0或1,求区间内1的子段个数

比如0 1 0 1 1 0 0 1 1 1答案为3

解法:

维护三个数组，\(num[x]\)表示\(x\)的线段个数

\(left[x]\)表示\(x\)的左端点是否为1,\(right[]\)同理.

小细节:pushup时当right[ls(x)] == 1 and left[rs(x)] == 1时,num[x]--

struct segtree{
	int size = 1;
	vector<ll>sumv,setv,left,right,num;
	const int NO_OPT = INT_MAX;
	void init(int n){
		while(size < n)size *= 2;
		sumv.assign(size*2,0);
		setv.assign(size*2,NO_OPT);
		left.assign(size*2,0);
		right.assign(size*2,0);
		num.assign(size*2,0);
	}
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2;
	}
	inline void apply(ll & a,ll b){
		a = (b == NO_OPT?a:b);
	}
	void pushdown(int x,int lx,int rx){
		int len = rx - lx;
		if(len == 1 or setv[x] == NO_OPT)return;
		len /= 2;
		apply(setv[ls(x)],setv[x]);
		apply(sumv[ls(x)],setv[x]*len);
		apply(setv[rs(x)],setv[x]);
		apply(sumv[rs(x)],setv[x]*len);
		if(setv[x]){
			num[ls(x)] = num[rs(x)] = 1;
			left[ls(x)] = left[rs(x)] = right[ls(x)] = right[rs(x)] = 1;
		}
		else{
			num[ls(x)] = num[rs(x)] = 0;
			left[ls(x)] = left[rs(x)] = right[ls(x)] = right[rs(x)] = 0;
		}
		setv[x] = NO_OPT;
	}
	void pushup(int x){
		sumv[x] = sumv[ls(x)] + sumv[rs(x)];
		left[x] = left[ls(x)];
		right[x] = right[rs(x)];
		num[x] = num[ls(x)] + num[rs(x)] - ((right[ls(x)] and left[rs(x)])?1:0);
	}
	void Set(int l,int r,ll v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			setv[x] = v;
			sumv[x] = v*(rx - lx);
			if(v){
				num[x] = 1;
				left[x] = right[x] = 1;
			}
			else{
				num[x] = 0;
				left[x] = right[x] = 0;
			}
			return;
		}
		int m = (lx+rx)/2;
		Set(l,r,v,ls(x),lx,m);
		Set(l,r,v,rs(x),m,rx);
		pushup(x);
	}
	void Set(int l,int r,ll v){
		Set(l,r,v,0,0,size);
	}
	ll sum(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			return sumv[x];
		}
		int m = (lx+rx)/2;
		ll s1 = sum(l,r,ls(x),lx,m);
		ll s2 = sum(l,r,rs(x),m,rx);
		return s1+s2;
	}
	ll sum(int l,int r){
		return sum(l,r,0,0,size);
	}
};

B

IOI2014-Walls

长度为\(n\)的序列初始为空,维护两种操作:

1. Add(L,R,v): 将\([L,R]\)中小于\(v\)的值改变为\(v\)
2. Remove(L,R,v):将\([L,R]\)中大于\(v\)的值改变为\(v\)

给出\(m\)个操作,输出操作全部完成后的序列.

\(1 \leq n \leq 2\cdot10^6,1 \leq m \leq 5\cdot10^5\)

对每个节点维护\(upv[]\)和\(lowv[]\),表示该节点值的上限和下限.查询时对每个点做一次单点查询,答案为\(lowv[x]\).

struct segtree{
	int size = 1;
	vector<int>upv,lowv;
	void init(int n){
		while(size < n)size *= 2;
		upv.assign(size*2,NO_OPT);
		lowv.assign(size*2,NO_OPT);
	}
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2;
	}
	void pushdown(int x,int lx,int rx){
		if(rx - lx == 1)return;
		if(upv[x] != NO_OPT){
			upv[ls(x)] = min(upv[x],upv[ls(x)]);
			upv[rs(x)] = min(upv[x],upv[rs(x)]);
			if(lowv[ls(x)] != NO_OPT and lowv[ls(x)] > upv[x])lowv[ls(x)] = upv[x];
			if(lowv[rs(x)] != NO_OPT and lowv[rs(x)] > upv[x])lowv[rs(x)] = upv[x];
			upv[x] = NO_OPT;
		}
		if(lowv[x] != NO_OPT){
			if(lowv[ls(x)] != NO_OPT)lowv[ls(x)] = max(lowv[ls(x)],lowv[x]);
			else lowv[ls(x)] = lowv[x];
			if(lowv[rs(x)] != NO_OPT)lowv[rs(x)] = max(lowv[rs(x)],lowv[x]);
			else lowv[rs(x)] = lowv[x];
			if(upv[ls(x)] != NO_OPT and upv[ls(x)] < lowv[x])upv[ls(x)] = lowv[x];
			if(upv[rs(x)] != NO_OPT and upv[rs(x)] < lowv[x])upv[rs(x)] = lowv[x];
			lowv[x] = NO_OPT;
		}
	}
	void up(int l,int r,int v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			upv[x] = min(upv[x],v);
			if(lowv[x] != NO_OPT and lowv[x] > v)lowv[x] = v;
			return;
		}
		int m = (lx+rx)/2;
		up(l,r,v,ls(x),lx,m);
		up(l,r,v,rs(x),m,rx);
		return;
	}
	void up(int l,int r,int v){
		up(l,r,v,0,0,size);
	}
	void low(int l,int r,int v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			if(lowv[x] == NO_OPT or lowv[x] < v)lowv[x] = v;
			if(upv[x] != NO_OPT and upv[x] > v)upv[x] = v;
			return;
		} 
		int m = (lx+rx)/2;
		low(l,r,v,ls(x),lx,m);
		low(l,r,v,rs(x),m,rx);
		return;
	}
	void low(int l,int r,int v){
		low(l,r,v,0,0,size);
	}
	int get(int idx,int x,int lx,int rx){
		if(idx >= rx)return NO_OPT;
		pushdown(x,lx,rx);
		if(rx - lx == 1)return lowv[x];
		int m = (lx+rx)/2;
		if(idx < m)return get(idx,ls(x),lx,m);
		else return get(idx,rs(x),m,rx);
	}
	int get(int idx){
		return get(idx,0,0,size);
	}
};
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	segtree seg;
	seg.init(n+1);
	while(m--){
		int opt,l,r,v;
		r++;
		cin >> opt >> l >> r >> v;
		r++;
		if(opt == 1)seg.low(l,r,v);
		else seg.up(l,r,v);
	}
	for(int i = 0;i < n;i++){
		int ans = seg.get(i);
		cout << (ans == NO_OPT?0:ans) << '\n';
	}
	return 0;
}

Rope

#include <ext/rope>
using namespace __gnu_cxx;

可持久化数组:

//
#include <bits/stdc++.h>
#include <ext/rope>
using namespace __gnu_cxx;
using namespace std;
const int maxn = 2e6 + 10;
#define endl '\n';
rope<int> rp[maxn];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	rp[0].push_back(0);
	for(int i = 1;i <= n;i++){
		int x;
		cin >> x;
		rp[0].push_back(x);
	}
	for(int i = 1;i <= m;i++){
		int ver,opt,idx,v;
		cin >> ver >> opt >> idx;
		rp[i] = rp[ver];
		if(opt == 1){
			cin >> v;
			rp[i].replace(idx,1,v);
		}
		else{
			int ans = rp[i][idx];
			cout << ans << endl;
		}
	}
	return 0;
}

• push_back(): This function is used to input a character at the end of the rope. Time Complexity: O(log N).
• pop_back(): Introduced from C++11(for strings), this function is used to delete the last character from the rope. Time Complexity: O(log N).
• insert(int x, crope r1): Inserts the contents of r1 before the xth element. Time Complexity: For Best Case: O(log N) and For Worst Case: O(N).
• erase(int x, int l): Erases l elements, starting with the xth element. Time Complexity: O(log N).
• substr(int x, int l): Returns a new rope whose elements are the l characters starting at the position x. Time Complexity: O(log N).
• replace(int x, int l, crope r1): Replaces the l elements beginning with the xth element with the elements in r1. Time Complexity: O(log N).
• concatenate(+): concatenate two ropes using the ‘+’ symbol. Time Complexity: O(1).

平衡树

Treap

---

平衡树1-Treap

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10;
struct Node{
	int cnt,size,v,r;
	Node * ch[2];
	int cmp(int x) const{
		if(x == v)return -1;
		return x<v?0:1;
	}
	Node(){//null,plz use newnode(x);
		ch[0] = ch[1] = NULL;
		cnt = size = v = r = 0;
	}
	void maintain(){
		size = ch[0]->size +ch[1]->size + cnt;
	} 
};
Node * null = new Node();
Node * newnode(int x){
	Node * tmp = new Node();
	tmp->ch[0] = tmp->ch[1] = null;
	tmp->v = x;
	tmp->r = rand();
	tmp->size = tmp->cnt = 1;
	return tmp;
}
Node * find(Node * o,int x){
	while(o != null){
		int d = o->cmp(x);
		if(d == -1)return o;
		else o = o->ch[d];
	}
	return null;
}
void rotate(Node *& o,int d){
	Node * k = o->ch[d^1];
	o->ch[d^1] = k->ch[d];
	k->ch[d] = o;
	o->maintain();k->maintain();
	o = k;
}
void insert(Node *& o,int x,int c){
	if(o == null)o = newnode(x);
	else{
		int d = o->cmp(x);
		if(d == -1)o->cnt+=c;
		else{
			insert(o->ch[d],x,c);
			if(o->ch[d]->r > o->r)rotate(o,d^1);
		}
	}
	o->maintain();
}
void remove(Node *& o,int x){
	if(find(o,x) == null)return;
	int d = o->cmp(x);
	if(d == -1){
		Node * u = o;
		if(o->cnt > 1){
			o->cnt--;
			o->size--;
		}
		else if(o->ch[0] != null and o->ch[1] != null){
			int d2 = o->ch[0]->r > o->ch[1]->r ?1:0;
			rotate(o,d2);
			remove(o->ch[d2],x);
		}
		else{
			if(o->ch[0] == null)o = o->ch[1];else o = o->ch[0];
			delete u;
		}
	}
	else remove(o->ch[d],x);
	if(o != null)o->maintain();
}
int kth(Node * o,int k){
	//min
	int k1 = k;
	while(o != null){
		int s = o->ch[0]->size;
		if(k1 > s and k1 <= s + o->cnt)return o->v;
		else if(k1 <= s) o = o->ch[0];
		else{
			k1 = k1 - s - o->cnt;
			o = o->ch[1];
		}
	}
	return 0;
}
int Rank(Node * o,int x){
    //比x小的数字个数。若不存在x则返回0
	int ans_ = 0;
	if(find(o,x) == null)return 0;
	while(o != null){
		if(o->v == x){
			ans_ += 1 + o->ch[0]->size;
			break;
		}
		else if(o->v > x)o = o->ch[0];
		else{
			ans_ += o->ch[0]->size + o->cnt;
			o = o->ch[1];
		}
	}
	return ans_;
}
int lower_bound(Node * o,int x){
	int ans_ = -INF;
	while(o != null){
		if(ans_ <= o->v and o->v < x){
			ans_ = o->v;
			o = o->ch[1];
		}
		else o = o->ch[0];
	}
	return ans_;
}
int upper_bound(Node * o,int x){
	int ans_ = INF;
	while(o != null){
		if(x < o->v and o->v < ans_){
			ans_ = o->v;
			o = o->ch[0];
		}
		else o = o->ch[1];
	}
	return ans_;
}
void deltree(Node *& o){
	if(o->ch[0] != null)deltree(o->ch[0]);
	if(o->ch[1] != null)deltree(o->ch[1]);
	delete o;
	o = null;
}
void merge(Node *& src,Node *& dest){
	if(src->ch[0] != null)merge(src->ch[0],dest);
	if(src->ch[1] != null)merge(src->ch[1],dest);
	insert(dest,src->v,src->cnt);
	delete src;
	src = null;
} 

字符串

读入

读入一行

getline

string s;
getline(cin,s);

sstream

string s;
stringstream ss;
int a, b, c;
getline(cin, s);
ss.clear();
ss.str(s);
ss >> a >> b >> c;

KMP

\(Next[i]\)表示自\(i\)结束(不包括\(i\))的子串中前后缀相同的长度

最小循环节长度: \(i - Next[i]\)

例如：

i	0	1	2	3	4	5	6	7	8	9	10	11
\(s[i]\)	A	B	R	A	C	A	D	A	B	R	A	\
\(Next[i]\)	0	0	0	0	1	0	1	0	1	2	3	4

可以看出\([i - Next[i],i - 1]\)这一段的前后缀是相同的

int Next[1000010];
void getFail(string P){
	int p_size = P.size();
	Next[0] = Next[1] = 0;
	for(int i = 1;i < p_size;i++){
		int j = Next[i];
		while(j and P[i] != P[j])j = Next[j];
		Next[i+1] = (P[j] == P[i]?j+1:0);
	}
}
void KMP(string T,string P){
	int t_size = T.size(),p_size = P.size();
	getFail(P);
	int j = 0;
	for(int i = 0;i < t_size;i++){
		while(j and P[j] != T[i])j = Next[j];
		if(P[j] == T[i])j++;
		if(j == p_size){
			printf("%d\n",i - p_size + 2);
			j = Next[j];
		}
	}
}

Manacher

最长连续回文子串

\(len[i] - 1\)表示以i为中心的最长回文串一半的长度(不包括中心)

返回最长连续回文子串的长度

struct Manacher{
	int len[maxn];
	string raw = "~";
	int ic = 0,im = 0,ir = 0,ans = 0;
	void init(string s = ""){
		for(int i = 0;i < s.size();i++){
			raw += '|';
			raw += s[i];
		}
		raw += "|!";
//		cout << raw << endl;
	}
	int run(){
		int l = raw.size();
		for(int i = 0;i < l;i++){
			len[i] = 0;
			if(i < ir){
				im = 2*ic-i;
				len[i] = min(ir-i,len[im]);
			}
			while(raw[i-len[i]] == raw[i+len[i]])len[i]++;
			if(i + len[i] > ir)ic = i,ir = i + len[i];
			if(len[i] > len[ic])ic = i;
			ans = max(len[i],ans);
		}
		for(char x:raw)cout << x << " ";
		return ans-1;
	}
}yay;

字符串hash (滚动hash)

​ \(H[x]\)为hash值,\(xp[d]\)为\(x^d\),\(x\)为底数(随便取一个就行),\(s\)为字符串.用ull自然溢出来-1s

​ 递推式:\(H[i] = H[i-1] \cdot x + (s[i] - 'a')\)

​ 查询以\(i\)开始长度为\(L\)的字符串的hash:$Hash(i,L) = H[i + L - 1] - (H[i-1] xp[L]) $

模板里的get和CompString默认下标从0开始

比较大小和求LCP的复杂度是\(O(log|s|)\)的，但一般比后缀数组快.

const int p1 = 998244353;
const int p2 = 1e9+9;
const int x1 = 123,x2 = 233;
struct Hash{
    vector<ll>xp1,xp2,H1,H2;
    string s;//非必须
    int n = 0;
	void init(string tar){
		s = tar;
		n = s.size();
		xp1.assign(n + 1,0);
		xp2.assign(n + 1,0);
		H1.assign(n + 1,0);
		H2.assign(n + 1,0);
		xp1[0] = xp2[0] = 1;
		for(int i = 1;i <= n;i++){
			xp1[i] = xp1[i-1] * x1 % p1;
			xp2[i] = xp2[i-1] * x2 % p2;
			H1[i] = (H1[i-1]*x1 % p1 + s[i-1] - 'a' + 1) % p1;
			H2[i] = (H2[i-1]*x2 % p2 + s[i-1] - 'a' + 1) % p2;
		}
	}
	Hash(){}
    Hash(string & tar){
		init(tar);
	}
	//Hash(i,L)
	pair<int,int> get(int x,int L){
		x++;
		if(x + L > n + 1){
			return {-1,-1};//不要用Rand(), 有效率问题. 记得特判-1
		}
		return {
			(H1[x+L-1] - H1[x-1]*xp1[L] % p1 + p1) % p1,
			(H2[x+L-1] - H2[x-1]*xp2[L] % p2 + p2) % p2
		};
	}
	int LCP(int s1,int s2){//求s[s1...]和s[s2...]的最长公共前缀
		int L = 1,R = n,M;
		while(L < R){
			M = (L+R)/2;
			auto it1 = get(s1,M);
			auto it2 = get(s2,M);
			if(it1.first != -1 and it1 == it2)L = M+1;
			else R = M;
		}
		return L - 1;
	}
	int CompString(int s1,int len1,int s2,int len2){
		//比较s[s1..],长度为len1和s[s2..],长度为len2的子串大小.
		//前者大于后者:1 相等:0 小于: -1
		int tlcp = (s1 == s2?min(len1,len2):LCP(s1,s2));
		if(tlcp >= min(len1,len2)){
			return len1 < len2?-1:(len1 == len2?0:1);
		}
		else return s[s1 + tlcp] < s[s2 + tlcp]?-1:(s[s1 + tlcp] == s[s2 + tlcp]?0:1);
	}
}hsh;

hash判断回文

hsh为原串的hash, hshr为反串的hash.

判断\(s[l...r]\)是否为回文. \(n = |s|\)

bool pali(int l,int r,int n){
	int len = (r - l + 1);
	if(len <= 1)return 1;
	auto it1 = hsh.get(l,len / 2);
	auto it2 = hshr.get(n - l - len,len / 2);
	return (it1.fit1 == it2);
}

后缀数组

一晚上速成的垃圾内容 需要细致的重构

注意字符串下标均从0开始

\(sa\)为后缀数组, sa[i]表示将所有后缀排序后第\(i\)小的后缀的编号

sa[]的示意图:(p为sa, 下标从0开始)

lcp[]的下标从1开始

\(lcp[i]\)为\(s[sa[i]...]\)和\(s[sa[i-1]...]\)的最长公共前缀长度(等同于lrj蓝书上的\(height\)

\(c\)为等价类,迭代结束后\(c\)等同于\(rank\),\(c[i]\)代表第\(i\)个后缀在\(sa\)中的下标

调用时通过\(SA(string)\)初始化,\(cal()\)计算sa,\(getlcp\)计算lcp.

\(LCP(i,j)\)返回后缀i和j的LCP.

注意LCP和ST用的是数组而不是vector

struct Node{
	int a,b;
	Node(int a = 0,int b = 0):a(a),b(b){}
	bool operator < (const Node & x){
		return a == x.a?b < x.b:a < x.a;
	}
}; 
struct SA{
	string s;
	int n;
	vector<int>sa,c;
	int lcp[maxn],ST[maxn][20];
	SA(string s = ""):s(s){
		s += '$';
		n = s.size();
		sa.assign(n,0);
		c.assign(n,0); 
	}
	void count_sort(vector<int> & sa,vector<int> & c){
		vector<int>pos(n),cnt(n),sa_new(n);
		for(int x:c)cnt[x]++;
		for(int i = 1;i < n;i++)pos[i] = pos[i-1] + cnt[i-1];
		for(int x:sa){
			int d = c[x];
			sa_new[pos[d]] = x;
			pos[d]++;
		}
		sa = sa_new;
	}
	void cal(){
		//init
		{
			vector<Node>A(n);
			for(int i = 0;i < n;i++)A[i] = Node(s[i],i);
			sort(A.begin(),A.end());
			for(int i = 0;i < n;i++)sa[i] = A[i].b;
			c[sa[0]] = 0;
			for(int i = 1;i < n;i++){
				c[sa[i]] = c[sa[i-1]] + (A[i].a != A[i-1].a);
			}
		}
		int k = 0;
		while((1<<k) < n){
			for(int i = 0;i < n;i++)sa[i] = (sa[i] - (1<<k) + n)%n;
			count_sort(sa,c);
			vector<int>c_new(n);
			c_new[sa[0]] = 0;
			for(int i = 1;i < n;i++){
				pair<int,int>now = {c[sa[i]],c[(sa[i] + (1<<k)) % n]};
				pair<int,int>prev = {c[sa[i-1]],c[(sa[i-1] + (1<<k)) % n]};
				c_new[sa[i]] = c_new[sa[i-1]] + (now != prev);
			}
			k++;
			c = c_new;
		}
	}
	void ST_init(){
		for(int i = 1;i <= n;i++)ST[i][0] = lcp[i];
		for(int j = 1;(1<<j) <= n;j++)
			for(int i = 1;i + (1<<j) -1 <= n;i++)
				ST[i][j] = min(ST[i][j - 1],ST[i + (1<<(j - 1))][j - 1]);
	}
	int LCP(int L,int R){
		L = c[L],R = c[R];
		if(L > R)swap(L,R);
		L++;
		int k = log2(R - L + 1);
		return min(ST[L][k],ST[R - (1<<k) + 1][k]);
	}
	void getlcp(){
		int k = 0;
		for(int i = 0;i < n-1;i++){
			int j = sa[c[i] - 1];
			while(s[i+k] == s[j+k])k++;
			lcp[c[i]] = k;
			if(k)k--;
		}
		ST_init();
	}
	void output(){
		for(int i = 0;i < n;i++)printf("%d ",sa[i]);
		printf("\n");
		for(int i = 1;i < n;i++)printf("%d ",lcp[i]);
	}
	int lower_bound(string x){
		int k = x.size();
		int L = 0,R = n,M;
		while(L < R){
			M = (L+R)/2;
			string u = s.substr(sa[M],k);
			if(u >= x)R = M;
			else L = M+1;
		}
		return L;
	}
	int upper_bound(string x){
		int k = x.size();
		int L = 0,R = n,M;
		while(L < R){
			M = (L+R)/2;
			string u = s.substr(sa[M],k);
			if(u <= x)L = M+1;
			else R = M;
		}
		return L;
	}
	int count(string x){
		return upper_bound(x) - lower_bound(x);
	}
};

附上个不用vector的,留着给POJ这种0202年还不兹磁C++11的OJ用(注意下标依旧从0开始)

如果T了的话把pair改成自己写的结构体.pair排序很慢

int sa[maxn],pos[maxn],cnt[maxn],sa_new[maxn],c[maxn],c_new[maxn];
pair<char,int>A[maxn];
void SA(){
	//init
	{
		for(int i = 0;i < n;i++)A[i] = {s[i],i};
		sort(A,A+n);
		for(int i = 0;i < n;i++)sa[i] = A[i].second;
		c[sa[0]] = 0;
		for(int i = 1;i < n;i++){
			c[sa[i]] = c[sa[i-1]] + (A[i].first != A[i-1].first);
		}
	}
	int k = 0;
	while((1<<k) < n){
		for(int i = 0;i < n;i++)sa[i] = (sa[i] - (1<<k) + n)%n;
		for(int i = 0;i <= n;i++)cnt[i] = pos[i] = 0;
		for(int i = 0;i < n;i++)cnt[c[i]]++;
		for(int i = 1;i < n;i++)pos[i] = pos[i-1] + cnt[i-1];
		for(int i = 0;i < n;i++)sa_new[pos[c[sa[i]]]++] = sa[i];
		for(int i = 0;i < n;i++)sa[i] = sa_new[i];
		c_new[sa[0]] = 0;
		for(int i = 1;i < n;i++){
			c_new[sa[i]] = c_new[sa[i-1]] + (c[sa[i]] != c[sa[i-1]] or c[(sa[i] + (1<<k)) % n] != c[(sa[i-1] + (1<<k)) % n]);
		}
		k++;
		for(int i = 0;i < n;i++)c[i] = c_new[i];
	}
}

应用

循环拼接

对字符串\(s\)的每个循环节进行排序

例如 s = "abacba"

即为对"abacba","bacbaa","acbaab","cbaaba","baabac","aabacb"进行排序

解法:将字符串本身拼接在其后面, 求\(s+s\)的后缀数组即可.

在线模式匹配

每个字符串均为某些字符串的后缀的前缀. 假设模式串为\(t\), 长度为\(|t|\), 那么我们只需根据后缀数组在文本串\(s\)中找到长度为\(|k|\)的后缀的前缀, 二分即可

每次查找复杂度:\(O(|t|logn)\)

文本串为\(s\), 模式串为\(t\).调用check(t)即可.

int check(string x){
    int k = x.size();
    int L = 0,R = n,M;
    while(L <= R){
        M = (L+R)/2;
        string u = s.substr(sa[M],k);
        if(u == x)return sa[M];
        else if(u < x)L = M+1;
        else R = M-1;
    }
    return -1;
}

统计字符串t在s中出现次数(可重叠)

思想同上.二分出上下界即可

代码见模板部分的count()

从字符串首尾取字符, 使新串字典序最小

当首尾字符不等时,显然取最小的最优.

当首尾字符相等时,需要判断由\(L\)开始的子串和由\(R\)开始的反子串的字典序大小,并取其中小的那个.

暴力求最坏需要\(O(n)\), 而后缀数组可以做到\(O(1)\)判断. 我们在\(s\)后加上一个\(s\)中未出现的字符,再将\(s\)反转之后的\(s'\)拼在其后.对新的\(s|s'\)求后缀数组.

由\(L\)开始的子串排名为\(rank[L]\), 由\(R\)开始的反子串排名为\(rank[N - 2 - R]\). (\(N\)为\(s|s'\)的长度. -2是因为我们在两个串中间拼接了一个特殊字符)

例题:[USACO07DEC]Best Cow Line G

输入一个整数\(n\),接下来\(n\)行每行一个字符.

输出从字符串首尾取字符, 能得到的最小字典序的新串.

//P2870
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6+10;
char s[maxn];
struct SA{
	int n;
	vector<int>sa,c;
	void count_sort(vector<int> & sa,vector<int> & c){
		vector<int>pos(n),cnt(n),sa_new(n);
		for(int x:c)cnt[x]++;
		for(int i = 1;i < n;i++)pos[i] = pos[i-1] + cnt[i-1];
		for(int x:sa){
			int d = c[x];
			sa_new[pos[d]] = x;
			pos[d]++;
		}
		sa = sa_new;
	}
	void cal(){
		for(int i = 0;i < n;i++)sa.push_back(0),c.push_back(0);
		//init
		{
			vector<pair<char,int> >A(n);
			for(int i = 0;i < n;i++)A[i] = {s[i],i};
			sort(A.begin(),A.end());
			for(int i = 0;i < n;i++)sa[i] = A[i].second;
			c[sa[0]] = 0;
			for(int i = 1;i < n;i++){
				c[sa[i]] = c[sa[i-1]] + (A[i].first != A[i-1].first);
			}
		}
		int k = 0;
		while((1<<k) < n){
			for(int i = 0;i < n;i++)sa[i] = (sa[i] - (1<<k) + n)%n;
			count_sort(sa,c);
			vector<int>c_new(n);
			c_new[sa[0]] = 0;
			for(int i = 1;i < n;i++){
				pair<int,int>now = {c[sa[i]],c[(sa[i] + (1<<k)) % n]};
				pair<int,int>prev = {c[sa[i-1]],c[(sa[i-1] + (1<<k)) % n]};
				c_new[sa[i]] = c_new[sa[i-1]] + (now != prev);
			}
			k++;
			c = c_new;
		}
	}
	void output(){
		for(int i = 0;i < n;i++)printf("%d ",sa[i]);
		printf("\n");
	}
};
int main(){
	int n,N;
	cin >> n;
	for(int i = 0;i < n;i++)cin >> s[i];
	s[n] = '|';
	int idx = n+1;
	for(int i = n-1;i >= 0;i--)s[idx++] = s[i];
	N = 2*(n+1);
	SA yay;
	yay.n = N;
	yay.cal();
	int L = 0,R = n-1,cnt = 0;
	while(L <= R){
		if(yay.c[L] < yay.c[N - 2 - R])cout << s[L++];
		else cout << s[R--];
		cnt++;
		if(cnt%80 == 0)cout << endl;
	}
	return 0;
}

LCP的应用

最长公共子串

给出两个字符串\(s,t\), 求它们的最长公共连续子串.

我们在\(s\)和\(t\)之间拼接一个未出现的特殊字符, 然后求LCP.将后缀分为两类:从\(s\)开始的后缀和从\(t\)开始的.显然答案为\(\max\{LCP[i]\},i与i-1为不同类\)

代码:

//P-5-B 
//SA
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
int a,b;
struct SA{
	string s;
	int n;
	vector<int>sa,c;
	int lcp[maxn],ST[maxn][20];
	SA(string s = ""):s(s){
		s += '$';
		n = s.size();
		for(int i = 0;i < n;i++)sa.push_back(0),c.push_back(0);
	}
	void count_sort(vector<int> & sa,vector<int> & c){
		vector<int>pos(n),cnt(n),sa_new(n);
		for(int x:c)cnt[x]++;
		for(int i = 1;i < n;i++)pos[i] = pos[i-1] + cnt[i-1];
		for(int x:sa){
			int d = c[x];
			sa_new[pos[d]] = x;
			pos[d]++;
		}
		sa = sa_new;
	}
	void cal(){
		//init
		{
			vector<pair<char,int> >A(n);
			for(int i = 0;i < n;i++)A[i] = {s[i],i};
			sort(A.begin(),A.end());
			for(int i = 0;i < n;i++)sa[i] = A[i].second;
			c[sa[0]] = 0;
			for(int i = 1;i < n;i++){
				c[sa[i]] = c[sa[i-1]] + (A[i].first != A[i-1].first);
			}
		}
		int k = 0;
		while((1<<k) < n){
			for(int i = 0;i < n;i++)sa[i] = (sa[i] - (1<<k) + n)%n;
			count_sort(sa,c);
			vector<int>c_new(n);
			c_new[sa[0]] = 0;
			for(int i = 1;i < n;i++){
				pair<int,int>now = {c[sa[i]],c[(sa[i] + (1<<k)) % n]};
				pair<int,int>prev = {c[sa[i-1]],c[(sa[i-1] + (1<<k)) % n]};
				c_new[sa[i]] = c_new[sa[i-1]] + (now != prev);
			}
			k++;
			c = c_new;
		}
	}
	void ST_init(){
		for(int i = 1;i <= n;i++)ST[i][0] = lcp[i];
		for(int j = 1;(1<<j) <= n;j++)
			for(int i = 1;i + (1<<j) -1 <= n;i++)
				ST[i][j] = min(ST[i][j - 1],ST[i + (1<<(j - 1))][j - 1]);
	}
	int LCP(int L,int R){
		L = c[L],R = c[R];
		if(L > R)swap(L,R);
		L++;
		int k = log2(R - L + 1);
		return min(ST[L][k],ST[R - (1<<k) + 1][k]);
	}
	void getlcp(){
		int k = 0;
		for(int i = 0;i < n-1;i++){
			int j = sa[c[i] - 1];
			while(s[i+k] == s[j+k])k++;
			lcp[c[i]] = k;
			if(k)k--;
		}
		ST_init();
	}
	void output(){
		int idx = 0,len = 0;
		for(int i = 1;i < n;i++){
			int now = n - 1 - sa[i],pre = n - 1 - sa[i-1];
			if((pre > b and now <= b) or (pre <= b and now > b)){
				if(len < lcp[i]){
					idx = sa[i];len = lcp[i];
				}
			}
		}
		cout << s.substr(idx,len);
	}
	int lower_bound(string x){
		int k = x.size();
		int L = 0,R = n,M;
		while(L < R){
			M = (L+R)/2;
			string u = s.substr(sa[M],k);
			if(u >= x)R = M;
			else L = M+1;
		}
		return L;
	}
	int upper_bound(string x){
		int k = x.size();
		int L = 0,R = n,M;
		while(L < R){
			M = (L+R)/2;
			string u = s.substr(sa[M],k);
			if(u <= x)L = M+1;
			else R = M;
		}
		return L;
	}
	int count(string x){
		return upper_bound(x) - lower_bound(x);
	}
};
int main(){
	string s,t;
	cin >> s >> t;
	a = s.size(),b = t.size();
	s = s+'#'+t;
	SA yay(s);
	yay.cal();
	yay.getlcp();
	yay.output();
	return 0;
}

两子串最长公共前缀

\[ LCP(sa[i],sa[j]) = min\{lcp[i+1],...,lcp[j]\} \]

于是就转化成了RMQ问题.

具体代码见模板中的LCP()

比较一个字符中两子串的关系

设需要比较\(A = s[a...b]\)和\(B = s[c...d]\)的关系.

若\(lcp(a,c) \ge \min(|A|,|B|)\),则\(A < B\)等价于\(|A| < |B|\)

否则, \(A < B\)等价于\(rank[a] < rank[c]\)

注意: 如果要将两个字符串\(A\), \(B\)拼接在一起, 且需统计\(A\)中小于等于\(B\)的子串个数时, 应该按\(B + A\)的方式拼接(前缀相同时更短的字符串rank更小)

int CompString(int s1,int len1,int s2,int len2){
		int tlcp = (s1 == s2?min(len1,len2):LCP(s1,s2));
		if(tlcp >= min(len1,len2)){
			return len1 < len2?-1:(len1 == len2?0:1);
		}
		else return c[s1] < c[s2]?-1:(c[s1] == c[s2]?0:1);
	}

注意: 可以只用\(lcp\)来比较字符串大小(这样就可以用hash等方法来求\(lcp\)而不用写SA). 只要把上面的第6行替换为

else return s[s1 + tlcp] < s[s2 + tlcp]?-1:(s[s1 + tlcp] == s[s2 + tlcp]?0:1);

即可.

不同子串的数目

\[ \frac{n(n+1)}{2} - \sum_{i = 1}^n lcp[i] \]

怎么推的忘了

ll ans = 0;
for(int i = 1;i < n;i++){
    ans += n - sa[i] - 1 - lcp[i];
}
cout << ans;

出现至少k次的子串的最大长度

首先\(lcp[i]\)表示\(sa[i]\)和\(sa[i-1]\)的最大公共长度

那么相邻的\(k-1\)个\(lcp\)的最小值就是该子串出现\(k\)次的最大公共长度.

所以我们求出相邻\(k-1\)个\(lcp\)的最小值, 再求这些最小值的最大值就是答案

可以用单调队列或者单调栈在\(O(n)\)时间内解决.

例题: [USACO06DEC]Milk Patterns G

输入第一行为\(n,k\) \(n\)为字符串长度,\(k\)为出现至少\(k\)次

下面的\(n\)行每行一个数字.

//P2852 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6+10;
int n,s[maxn];
int sa[maxn],pos[maxn],cnt[maxn],sa_new[maxn],c[maxn],c_new[maxn],lcp[maxn];
pair<int,int>A[maxn];
void SA(){
	for(int i = 0;i < n;i++)A[i] = {s[i],i};
	sort(A,A+n);
	for(int i = 0;i < n;i++)sa[i] = A[i].second;
	c[sa[0]] = 0;
	for(int i = 1;i < n;i++){
		c[sa[i]] = c[sa[i-1]] + (A[i].first != A[i-1].first);
	}
	int k = 0;
	while((1<<k) < n){
		for(int i = 0;i < n;i++)sa[i] = (sa[i] - (1<<k) + n)%n;
		for(int i = 0;i <= n;i++)cnt[i] = pos[i] = 0;
		for(int i = 0;i < n;i++)cnt[c[i]]++;
		for(int i = 1;i < n;i++)pos[i] = pos[i-1] + cnt[i-1];
		for(int i = 0;i < n;i++)sa_new[pos[c[sa[i]]]++] = sa[i];
		for(int i = 0;i < n;i++)sa[i] = sa_new[i];
		c_new[sa[0]] = 0;
		for(int i = 1;i < n;i++){
			c_new[sa[i]] = c_new[sa[i-1]] + (c[sa[i]] != c[sa[i-1]] or c[(sa[i] + (1<<k)) % n] != c[(sa[i-1] + (1<<k)) % n]);
		}
		k++;
		for(int i = 0;i < n;i++)c[i] = c_new[i];
	}
	k = 0;
	for(int i = 0;i < n-1;i++){
		int j = sa[c[i] - 1];
		while(s[i+k] == s[j+k])k++;
		lcp[c[i]] = k;
		if(k)k--;
	}
}
struct Node{
	int w,idx;
	Node(int w = 0,int idx = 0):w(w),idx(idx){}
};
deque<Node>qmin;
int main(){
	int K;
	scanf("%d%d",&n,&K);
	K--;
	for(int i = 0;i < n;i++)scanf("%d",&s[i]);
	s[n] = -1;
	n++;
	SA();
	int ans = 0;
	for(int i = 1;i < n;i++){
		Node u = Node(lcp[i],i);
		while(qmin.size() and qmin.back().w > u.w)qmin.pop_back();
		qmin.push_back(u);
		while(qmin.size() and qmin.front().idx < i - K + 1)qmin.pop_front();
		if(i >= K)ans = max(ans,qmin.front().w);
	}
	printf("%d",ans);
	return 0;
}

Trie

待补充.

struct Trie{
	int siz = 1;
	int nxt[maxn][30];
	int vis[maxn];
	void clear(){
		siz = 1;
		memset(nxt,0,sizeof(nxt));
		memset(vis,0,sizeof(vis));
	}
	void insert(string s){
		int u = 0;
		for(int x:s){
			int c = x - '0';
			if(!nxt[u][c]){
				nxt[u][c] = siz++;
			}
			u = nxt[u][c];
		}
	}
	void search(string s){
		int u = 0;
		for(int x:s){
			int c = x - '0';
			if(!nxt[u][c]){
				cout << "WRONG\n";
				return;
			}
			u = nxt[u][c];
		}
		if(vis[u])cout << "REPEAT\n";
		else{
			cout << "OK\n";
			vis[u] = 1;
		}
	}	
}trie;

暴力

分块

因为分块细节很多,这里只放几道例题.

区间加法,单点查询

//LOJ6277 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4+10;
const int SIZ = 256;
vector<ll>block[maxn];
int bnt[maxn];
ll add[maxn],raw[maxn];
void update(int L,int R,int w){
	if(bnt[L] == bnt[R]){
		for(int i = L;i <= R;i++)raw[i] += w;
	}
	else{
		for(int i = L;i <= bnt[L]*SIZ;i++)raw[i] += w;
		for(int i = (bnt[R]-1)*SIZ+1;i <= R;i++)raw[i] += w;
		for(int i = bnt[L]+1;i < bnt[R];i++)add[i] += w;
	}
}
ll query(int x){
	return raw[x] + add[(x-1)/SIZ+1];
}
int main(){
	ios::sync_with_stdio(0);
	for(int i = 1;i < maxn;i++)bnt[i] = (i-1)/SIZ+1;
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)cin >> raw[i];
	for(int i = 1;i <= n;i++){
		int o,l,r,w;
		cin >> o >> l >> r >> w;
		if(o)cout << query(r) << endl;
		else update(l,r,w);
	}
	return 0;
}

动态逆序对

现在给出 1到n 的一个排列，按照某种顺序依次删除 m 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

//P3157 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
const int SIZ = 1024;
int bnt[maxn],raw[maxn],A[maxn];
int BIT[maxn],n,m,maxb;
vector<int>Block[maxn];
ll ans = 0;
inline int lowbit(int b){
	return b&-b;
}
void add(int index,int d){
	while(index <= n){
		BIT[index] += d;
		index += lowbit(index);
	}
}
int sum(int index){
	int t_ans = 0;
	while(index){
		t_ans += BIT[index];
		index -= lowbit(index);
	}
	return t_ans;
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++){
		scanf("%d",&raw[i]);
		bnt[i] = (i-1)/SIZ+1;
		A[raw[i]] = i;
		Block[bnt[i]].push_back(raw[i]);
		ans += (i-1-sum(raw[i]));
		add(raw[i],1);
	}
	maxb = (n-1)/SIZ+1;
	for(int i = 1;i <= maxb;i++)sort(Block[i].begin(),Block[i].end());
}
int query(int x){
	int b = (A[x]-1)/SIZ+1,k = 0;
	for(int i = 1;i < b;i++)k += (Block[i].size() - (lower_bound(Block[i].begin(),Block[i].end(),x) - Block[i].begin()));
	for(int i = b+1;i <= maxb;i++)k += lower_bound(Block[i].begin(),Block[i].end(),x) - Block[i].begin();
	for(int i = (b-1)*SIZ+1;i < A[x];i++)if(raw[i] and raw[i] > x)k++;
	for(int i = A[x];i <= b*SIZ;i++)if(raw[i] and raw[i] < x)k++;
	return k;
}
void del(int x){
	int b = (A[x]-1)/SIZ+1;
	raw[A[x]] = 0;
	A[x] = 0; 
	for(auto it = Block[b].begin();it != Block[b].end();it++){
		if(*it == x){
			Block[b].erase(it);
			return;
		}
	}
}
int main(){
	init();
	while(m--){
		int x;
		scanf("%d",&x);
		printf("%lld\n",ans);
		ans -= query(x);
		del(x);
	}
	return 0;
}

莫队

基础莫队(小B的询问,Luogu P2709)

求\(\sum_{i = 1}^kc_{i}^2\)

\(c_i\)为\(i\)在\([L,R]\)的出现次数

块大小取\(\sqrt{n}\)

//P2709
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
const int SIZ = 512;
ll cnt[maxn],res[maxn],raw[maxn],ans;
int n,m,k;
struct Node{
	int L,R,idx;
	Node(int L = 0,int R = 0,int idx = 0):L(L),R(R),idx(idx){}
	bool operator < (const Node & x)const{
		if((L-1)/SIZ != (x.L-1)/SIZ)return (L-1) < (x.L-1);
		else return R < x.R;	
	}
}query[maxn];
void update(int pos,int x){
	int v = raw[pos];
	if(x == 1)ans += cnt[v]*2 + 1;
	else ans += 1 - cnt[v]*2;
	cnt[v] += x;
}
int main(){
	cin >> n >> m >> k;
	for(int i = 1;i <= n;i++)cin >> raw[i];
	for(int i = 1;i <= m;i++){
		int L,R;
		cin >> L >> R;
		query[i] = Node(L,R,i);
	}
	sort(query+1,query+m+1);
	int l = 1,r = 0;
	for(int i = 1;i <= m;i++){
		while(l > query[i].L)update(--l,1);
		while(r < query[i].R)update(++r,1);
		while(l < query[i].L)update(l++,-1);
		while(r > query[i].R)update(r--,-1);
		res[query[i].idx] = ans;
	}
	for(int i = 1;i <= m;i++)cout << res[i] << endl;
	return 0;
}

奇偶排序优化:

bool operator < (const Node & x)const{
	if((l-1)/SIZ != (x.l-1)/SIZ)return l < x.l;
	else{
		if(((l-1)/SIZ+1)%2)return r < x.r;
		else return r > x.r; 
	}
}

带修莫队

分块大小取\(n^{\frac{2}{3}}\)

询问存当前区间(\(l,r\))和修改的时间(\(t\)), 排序分别以\(l,r,t\)为关键字.

修改时如果当前时间比询问时间小就暴力修改，否则暴力回退

注意: 只有修改的位置在当前区间内才更新答案，但无论如何都要进行修改

例题:P1903 [国家集训队]数颜色 / 维护队列

1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。

2、 R P Col 把第P支画笔替换为颜色Col。

//P1903-Mo 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int SIZ = 2607;
const int maxn = 4e6+10;
int raw[maxn],cnt[maxn];
struct Query{
	int l,r,idx,t,ans;
	int v;
	bool operator < (const Query & x) const{
		if((l-1)/SIZ != (x.l-1)/SIZ)return l < x.l;
		else if((r-1)/SIZ != (x.r-1)/SIZ){
			if(((l-1)/SIZ)%2)return r < x.r;
			else return r > x.r;
		}
		else return t < x.t;	
	}
	Query(int l,int r,int idx,int t):l(l),r(r),idx(idx),t(t){}
	Query(int idx = 0,int v = 0):idx(idx),v(v){}
}query[maxn],op[maxn];
int ans = 0;
inline void add(int x){
	if(!cnt[x])ans++;
	cnt[x]++;
}
inline void del(int x){
	if(1 == cnt[x])ans--;
	cnt[x]--;
}
void change(int tim,int qidx){
	//opt :1,re 0,add
	int l = query[qidx].l,r = query[qidx].r,x = op[tim].idx;
	if(l <= x and x <= r){
		del(raw[x]);
		add(op[tim].v);
	}
	swap(raw[x],op[tim].v);
}
signed main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++)scanf("%d",&raw[i]);
	int ocnt = 0,qcnt = 0;
	for(int i= 1;i <= m;i++){
		string opt;
		int l,r;
		cin >> opt;
		scanf("%d%d",&l,&r);
		if(opt == "Q"){
			qcnt++;
			query[qcnt] = Query(l,r,qcnt,ocnt);
		}
		else op[++ocnt] = Query(l,r);
	}
	sort(query+1,query+qcnt+1);
	int l = 1,r = 0,now = 0;
	for(int i = 1;i <= qcnt;i++){
		while(l < query[i].l)del(raw[l++]);
		while(l > query[i].l)add(raw[--l]);
		while(r > query[i].r)del(raw[r--]);
		while(r < query[i].r)add(raw[++r]);
		while(now < query[i].t)change(++now,i);
		while(now > query[i].t)change(now--,i);
		query[i].ans = ans;
	}
	auto cmp = [](Query a,Query b) -> bool{
		return a.idx < b.idx;
	};
	sort(query+1,query+qcnt+1,cmp);
	for(int i = 1;i <= qcnt;i++)printf("%d\n",query[i].ans);
	return 0;
}

树上莫队

分块方式

将树分为大小在\([B,3B)\)之间的块, 其中\(pa[i]\)表示第\(i\)个点所属的块编号, \(pivot[i]\)表示\(i\)号块对应的关键点. 关键点是满足该块内任意一点到关键点的简单路径上的所有点都在块内的点

stack<int>s;
int B;
int pa[maxn],pivot[maxn],acnt;
void dfs(int u,int fa){
	int siz = s.size();
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(v == fa)continue;
		dfs(v,u);
		if((int)s.size() - siz >= B){
			pivot[++acnt] = u;
			while((int)s.size() > siz){
				pa[s.top()] = acnt;
				s.pop();
			}
		}
	}
	s.push(u);
}

使用时:

dfs(1,-1);
while(s.size()){
    pa[s.top()] = acnt;
    s.pop();
}

其他

并查集

路径压缩,无按秩合并

int father[maxn];
void init(){
	for(int i = 1;i <= n;i++)father[i] = i;
}
int findset(int e){
	return father[e] == e?e:father[e] = findset(father[e]);
}
inline void un(int x,int y){
	father[findset(x)] = findset(y);
}

路径压缩, 按秩合并

int fa[maxn],siz[maxn];
int findset(int e){
	return fa[e] == e?e:fa[e] = findset(fa[e]); 
}
void un(int a,int b){
	a = findset(a),b = findset(b);
	if(siz[a] > siz[b])swap(a,b);
	siz[b] += siz[a];
	// fa[a] = fa[b];
	fa[a] = b;
}
bool check(int a,int b){
	return findset(a) == findset(b);
}

带权并查集

int fa[maxn],siz[maxn],maxv[maxn],minv[maxn];
int findset(int e){
	return fa[e] == e?e:fa[e] = findset(fa[e]);
}
bool check(int a,int b){
	return findset(a) == findset(b);
} 
void un(int a,int b){
	if(check(a,b))return;
	int & v = fa[findset(a)],u = findset(b);
	siz[u] += siz[v];
	maxv[u] = max(maxv[u],maxv[v]);
	minv[u] = min(minv[u],minv[v]);
	v = u;
}
 

二分

int lower_bound(int & A,int x){
	int L = 0,R = n,M;
	while(L < R){
		M = (L+R)/2;
		if(A[M] >= x)R = M;
		else L = M+1;
	}
	return L;
}
int upper_bound(int & A,int x){
	int L = 0,R = n,M;
	while(L < R){
		M = (L+R)/2;
		if(A[M] <= x)L = M+1;//区别在此
		else R = M;
	}
	return L;
}

单调队列

保证双端队列里的值单调即可.

for(int i = 1;i <= n;i++){
	Node u = Node(raw[i],i);
	while(qmin.size() and qmin.back().w > u.w)qmin.pop_back();
	qmin.push_back(u);
	while(qmin.size() and qmin.front().idx < i - k + 1)qmin.pop_front();
	if(i >= k)cout << qmin.front().w << " ";
}