并查集

struct DSU
{
    vector<int> fa, sz;
    DSU(int n) : fa(n+1), sz(n + 1, 1) { iota(fa.begin(), fa.end(), 0); }
    int find(int x){
        while (x != fa[x]) x = fa[x] = fa[fa[x]];
        return x;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y){
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (sz[x] > sz[y]) swap(x, y);
        sz[y] += sz[x];
        fa[x] = y;
        return true;
    }
    int size(int x) { return sz[find(x)]; }
};

树状数组

struct BIT {
    int n; vector<int> c;
    BIT(int sz) : n(sz), c(sz + 1) {};
    int lowbit(int x) { return x & -x; }
    void add(int x, int val) {
        while (x <= n) c[x] += val, x += lowbit(x);
    }
    int getsum(int x){
        int ans = 0;
        while (x) ans += c[x], x -= lowbit(x);
        return ans;
    }
    int query(int l, int r){ return getsum(r) - getsum(l - 1); }
    int kth(int k) {//大于等于k的最小位置
    	int res = 0, x = 0; 
    	for (int i = log2(n); i >= 0; --i) {
        	x += 1 << i;                 
        	if (x >= n || res + c[x] >= k) x -= 1 << i;
        	else res += c[x];
    	}
   		return x + 1;
	}
};

线段树

单点修改 区间和查询

struct SegTree {
	struct node {
		int l, r, sum;
	}tree[N << 2];//四倍大小
	void push_up(int p)
	{
		tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
	}
	void build(int l, int r, int p)
	{
		tree[p].l = l, tree[p].r = r;
		if (l == r)
		{
			tree[p].sum = a[l];
			return;
		}
		int mid = (l + r) / 2;
		build(l, mid, p << 1);
		build(mid + 1, r, p << 1 | 1);
		push_up(p);
	}
	void update(int pos, int val, int p)//单点修改，直接修改值
	{
		int  l = tree[p].l, r = tree[p].r;
		if (l == r)
		{
			tree[p].sum = val;
			return;
		}
		int mid = (l + r) / 2;
		if (pos <= mid)
			update(pos, val, p << 1);
		else
			update(pos, val, p << 1 | 1);
		push_up(p);
	}
	int query(int ql, int qr, int p)//查询区间和
	{
		int l = tree[p].l, r = tree[p].r;
		if (ql <= l && qr >= r)
		{
			return tree[p].sum;
		}
		int mid = (l + r) / 2;
		int ans = 0;
		if (ql <= mid)
			ans += query(ql, qr, p << 1);
		if (qr > mid)
			ans += query(ql, qr, p << 1 | 1);
		return ans;
	}
};

区间修改 区间查询 最大值

struct SegTree {
	struct node {
		int l, r, mx, lazy;
	}tree[N << 2];
	void build(int l, int r, int p)
	{
		tree[p].l = l, tree[p].r = r;
        tree[p].mx = tree[p].lazy = 0;
		if (l == r)
			return;
		int mid = (l + r) / 2;
		build(l, mid, p << 1);
		build(mid + 1, r, p << 1 | 1);
	}
	void push_up(int p)
	{
		tree[p].mx = max(tree[p << 1].mx, tree[p << 1 | 1].mx);
	}
	void push_down(int p)
	{
		if (!tree[p].lazy)
			return;
		tree[p << 1].mx += tree[p].lazy;
		tree[p << 1 | 1].mx += tree[p].lazy;
		tree[p << 1].lazy += tree[p].lazy;
		tree[p << 1 | 1].lazy += tree[p].lazy;
		tree[p].lazy = 0;
	}
	void update(int ul, int ur, int val, int p)
	{
		int l = tree[p].l, r = tree[p].r;
		if (ul <= l && ur >= r)
		{
			tree[p].mx += val;
			tree[p].lazy += val;
			return;
		}
		push_down(p);
		int mid = (l + r) / 2;
		if (ul <= mid)
			update(ul, ur, val, p << 1);
		if (ur > mid)
			update(ul, ur, val, p << 1 | 1);
		push_up(p);
	}
	int query(int ql, int qr, int p)
	{
		int l = tree[p].l, r = tree[p].r;
		if (ql <= l && qr >= r)
			return tree[p].mx;
		push_down(p);
		int mid = (l + r) / 2;
		int ans = 0;
		if (ql <= mid)
			ans = max(ans, query(ql, qr, p << 1));
		if (qr > mid)
			ans = max(ans, query(ql, qr, p << 1 | 1));
		return ans;
	}
}sg;

主席树（ 可持久化权值线段树 ）

int n, m, a[N], b[N];///求区间[l,r]中的第k大元素

struct node{
	int ls, rs, sum;//ls：左儿子编号 lr：右儿子编号 sum：元素个数
}tree[N<<5];//一般开32倍大小 
int rt[N], sz;//rt[i]：第i个根节点编号 sz ：节点数量

void update(int l, int r, int &x, int y, int p)
{
	x = ++sz;
	tree[x] = tree[y];//先将节点原点信息复制
	tree[x].sum++;//元素个数增加
	if(l == r) return;
	int mid = (l + r) / 2;
	if(p <= mid) update(l, mid, tree[x].ls, tree[y].ls, p);
	else update(mid + 1, r, tree[x].rs, tree[y].rs, p);
}

int query(int l, int r, int x, int y, int k)
{
	int temp = tree[tree[y].ls].sum - tree[tree[x].ls].sum;//左半边元素个数
	if(l == r) return l;
	int mid = (l + r) / 2;
	if(temp >= k) return query(l, mid, tree[x].ls, tree[y].ls, k);
	else return query(mid+1, r, tree[x].rs, tree[y].rs, k - temp);
}

void solve()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
	int len = unique(b + 1, b + 1 + n) - b - 1;//离散化数据
	
	for(int i = 1; i <= n; i++)
	{
		int p = lower_bound(b + 1, b + 1 + len, a[i]) - b;//寻找a[i]离散化后的数据
		update(1, len, rt[i], rt[i-1], p);
	}
	while(m--)
	{
		ll l, r, k;
		cin >> l >> r >> k;
		cout << b[query(1, len, rt[l-1], rt[r], k)] << '\n';
	}
}

字典树

字符串

int tot;//点数
struct node{
	int alp[26];//alp[i]若为正数，则有可通向对应字母的点
	int isend;//该点是否可以作为终点
}tree[N];//开模式串个数*长度的大小

void insert(string s)
{
	int p = 0;
	for(int i = 0; i < s.size(); i++)
	{
		int temp = s[i] - 'a';
		if(!tree[p].alp[temp])
			tree[p].alp[temp] = ++tot;
		p = tree[p].alp[temp];
	}
	tree[p].isend = 1;
}

bool search(string s)
{
	int p = 0;
	for(int i = 0; i < s.size(); i++)
	{
		int temp = s[i] - 'a';
		if(!tree[p].alp[temp])//没有对应的点
			return false;
		p = tree[p].alp[temp];
	}
	if(tree[p].isend)//判断该点是否可作为终点
		return true;
	return false;
}

void solve()
{
	cin>>n;
	string s;
	for(ll i = 1; i <= n; i++)
	{
		cin>>s;
		insert(s);
	}
    map<string, ll> mp;
	cin>>q;
	while(q--)
	{
		cin>>s;
		bool f = search(s);
		if(!f)
			cout<<"WRONG"<<'\n';
		else
		{
			mp[s]++;
			if(mp[s] == 2)
			{
				cout<<"REPEAT"<<'\n';
				mp[s] = 1;
			}
			else
				cout<<"OK"<<'\n';
		}
	}//洛谷P2580
} 

二进制

#include<bits/stdc++.h>//cf 817E
#define ll long long
using namespace std;

const int N = 1e5 + 5;

ll n;

struct node {
	ll bit[2];
	ll cnt;
}tree[N << 5];开模式串个数*长度的大小
ll sz;

void insert(ll num)
{
	ll p = 0;
	for (ll i = 31; i >= 0; i--)
	{
		if (!tree[p].bit[(num >> i) & 1])
			tree[p].bit[(num >> i) & 1] = ++sz;
		p = tree[p].bit[(num >> i) & 1];
		tree[p].cnt++;
	}
}

void del(ll num)
{
	ll p = 0;
	for (ll i = 31; i >= 0; i--)
	{
		if (!tree[p].bit[(num >> i) & 1])
			return;
		p = tree[p].bit[(num >> i) & 1];
		tree[p].cnt--;
	}
}

ll search(ll num1, ll num2)
{
	ll p = 0;
	ll ans = 0;
	for (ll i = 31; i >= 0; i--)
	{
		ll x = (num1 >> i) & 1;
		ll y = (num2 >> i) & 1;
		if (x == 1)
		{
			if (y == 1)
			{
				ans += tree[tree[p].bit[1]].cnt;
				p = tree[p].bit[0];
			}
			else if (y == 0)
				p = tree[p].bit[1];
		}
		else if (x == 0)
		{
			if (y == 1)
			{
				ans += tree[tree[p].bit[0]].cnt;
				p = tree[p].bit[1];
			}
			else if (y == 0)
				p = tree[p].bit[0];
		}
		if (!p)
			break;
	}
	return ans;
}

void solve()
{
	cin >> n;
	while (n--)
	{
		ll op;
		cin >> op;
		if (op == 1)
		{
			ll x;
			cin >> x;
			insert(x);
		}
		else if (op == 2)
		{
			ll x;
			cin >> x;
			del(x);
		}
		else
		{
			ll x, y;
			cin >> x >> y;
			cout << search(x, y) << '\n';
		}
	}
}

int main()
{
	solve();
	return 0;
}

ST表

一维ST表

最大/小值， gcd， 按位或

int mx[21][N], Log[N];
void init_ST()
{
	for (int j = 1; j <= 20; j++)
		for (int i = 1; i + (1 << j) - 1 <= n; i++)
			mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
	Log[1] = 0;
	for (int i = 2; i <= n; i++) Log[i] = Log[i / 2] + 1;
}
int query(int l, int r)
{
	int k = Log[r - l + 1];
	return max(mx[k][l], mx[k][r - (1 << k) + 1]);
}

二维ST表

int mi[N][N][21][21], Log[N];
void init_ST()
{
    for (int i = 0; i <= 20; i++){
        for (int j = 0; j <= 20; j++){
            if (i == 0 and j == 0) continue;
            for (int k = 1; k <= n - (1 << i) + 1; k++){
                for (int p = 1; p <= m - (1 << j) + 1; p++){
                    if (i == 0) mi[k][p][i][j] = min(mi[k][p][i][j - 1], mi[k][p + (1 << j - 1)][i][j - 1]);
                    else mi[k][p][i][j] = min(mi[k][p][i - 1][j], mi[k + (1 << i - 1)][p][i - 1][j]);
                }
            }
        }
    }
    Log[1] = 0;
	for (int i = 2; i <= n; i++) Log[i] = Log[i / 2] + 1;
}
int query(int r1, int c1, int r2, int c2)
{
    int k1 = Log[r2 - r1 + 1];
    int k2 = Log[c2 - c1 + 1];
    return min({mi[r1][c1][k1][k2], mi[r2 - (1 << k1) + 1][c1][k1][k2], mi[r1][c2 - (1 << k2) + 1][k1][k2], mi[r2 - (1 << k1) + 1][c2 - (1 << k2) + 1][k1][k2]});
}

莫队

莫队

//https://codeforces.com/contest/1484/problem/D
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const ll mod = 1e9 + 7;
const ll N = 5e4 + 5;

ll n, m, a[N], len, pos[N], res, num[N], ans[N], le[N];
struct node {
	ll l, r, id;
	bool operator < (const node& a) const
	{
		if (pos[l] != pos[a.l])
			return pos[l] < pos[a.l];
		if (pos[l] % 2)
			return r < a.r;
		return r > a.r;
	}
}q[N];

void add(ll x)
{
	res -= num[a[x]] * (num[a[x]] - 1) / 2;
	num[a[x]]++;
	res += num[a[x]] * (num[a[x]] - 1) / 2;
}

void del(ll x)
{
	res -= num[a[x]] * (num[a[x]] - 1) / 2;
	num[a[x]]--;
	res += num[a[x]] * (num[a[x]] - 1) / 2;
}

ll gcd(ll x, ll y)
{
	return y ? gcd(y, x % y) : x;
}

void solve()
{
	cin >> n >> m;
	len = sqrt(n);
	for (ll i = 1; i <= n; i++)
	{
		cin >> a[i];
		pos[i] = (i + len - 1) / len;
	}
	for (ll i = 1; i <= m; i++)
	{
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1, q + 1 + m);
	for (ll i = 1, l = 1, r = 0; i <= m; i++)
	{
		while (l > q[i].l)
			add(--l);
		while (r < q[i].r)
			add(++r);
		while (l < q[i].l)
			del(l++);
        while (r > q[i].r)
			del(r--);
		ans[q[i].id] = res;
		le[q[i].id] = q[i].r - q[i].l + 1;
	}
	for (ll i = 1; i <= m; i++)
	{
		if (!ans[i])
		{
			cout << "0/1" << '\n';
			continue;
		}
		ll x = le[i] * (le[i] - 1) / 2;
		ll g = gcd(ans[i], x);
		cout << ans[i] / g << "/" << x / g << '\n';
	}
}

signed main()
{
	IOS;
	ll t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

回滚莫队

//https://vjudge.net/contest/501795#problem/D
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const ll mod = 1e9 + 7;
const ll N = 1e5 + 5;

ll n, m, len, pos[N], a[N], num[N], num2[N], ans[N], b[N];

struct node {
	ll l, r, id;
	bool operator < (const node& a) const
	{
		if (pos[l] != pos[a.l])
			return pos[l] < pos[a.l];
		return r < a.r;
	}
}q[N];

void add(ll x, ll& res)
{
	num[x]++;
	res = max(res, num[x] * b[x]);
}

void del(ll x)
{
	num[x]--;
}

void solve()
{
	cin >> n >> m;
	len = sqrt(n);
	for (ll i = 1; i <= n; i++)
	{
		cin >> a[i];
		b[i] = a[i];
		pos[i] = (i + len - 1) / len;
	}
	sort(b + 1, b + 1 + n);
	ll cnt = unique(b + 1, b + 1 + n) - b - 1;//离散化
	for (ll i = 1; i <= n; i++)
		a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
	for (ll i = 1; i <= m; i++)
	{
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1, q + 1 + m);
	ll res = 0, l = 1, r = 0, last = 0;
	for (ll i = 1; i <= m; i++)
	{
		//左右区间都在同一个块内,长度较小直接暴力
		if (pos[q[i].l] == pos[q[i].r])
		{
			ll res2 = 0;
			for (ll j = q[i].l; j <= q[i].r; j++)
			{
				num2[a[j]]++;
				res2 = max(res2, num2[a[j]] * b[a[j]]);
			}
			ans[q[i].id] = res2;
			for (ll j = q[i].l; j <= q[i].r; j++)
				num2[a[j]]--;
			continue;
		}
		//如果当前询问块号和前一次不同，将左指针移动到当前块最右端+1，右指针移动到当前块右端
		if (last != pos[q[i].l])
		{
			ll R = min(n, pos[q[i].l] * len);
			while (r > R)
				del(a[r--]);
			while (l < R + 1)
				del(a[l++]);
			res = 0;
			last = pos[q[i].l];
		}
		while (r < q[i].r)
			add(a[++r], res);
		ll templ = l;
		ll temp_res = res;
		//答案备份
		while (templ > q[i].l)
			add(a[--templ], temp_res);
		ans[q[i].id] = temp_res;
		//回滚
		while (templ < l)
			del(a[templ++]);
	}
	for (ll i = 1; i <= m; i++)
		cout << ans[i] << '\n';
}

signed main()
{
	IOS;
	ll t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

树上莫队

int n, m, a[N];
int tot, fa[N], dep[N], sz[N], hson[N], top[N], rnk[N];
int li[N * 2], st[N], ed[N];
int pos[N * 2];
int ans[N], res, cnt[N], use[N];
vector<int> g[N];
vector<int> v;
struct Query {
	int l, r, id, lca;
	bool operator < (Query a)
	{
		if (pos[l] != pos[a.l])
			return pos[l] < pos[a.l];
		if (pos[l] % 2)
			return r < a.r;
		return r > a.r;
	}
}q[N];

void dfs1(int x, int father, int d)
{
	dep[x] = d;
	hson[x] = -1;
	sz[x] = 1;
	for (auto to : g[x])
	{
		if (to == father)
			continue;
		fa[to] = x;
		dfs1(to, x, d + 1);
		sz[x] += sz[to];
		if (hson[x] == -1 || sz[to] > sz[hson[x]])
			hson[x] = to;
	}
}

void dfs2(int x, int t)
{
	top[x] = t;
	st[x] = ++tot;
	li[tot] = x;
	rnk[tot] = x;
	if (hson[x] != -1)
		dfs2(hson[x], t);
	for (auto to : g[x])
	{
		if (to == fa[x] || to == hson[x])
			continue;
		dfs2(to, to);
	}
	ed[x] = ++tot;
	li[tot] = x;
}

int Lca(int x, int y)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] > dep[top[y]])
			x = fa[top[x]];
		else
			y = fa[top[y]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	return x;
}

void cal(int x)
{
	if (use[x] == 0)
	{
		cnt[a[x]]++;
		if (cnt[a[x]] == 1)
			res++;
	}
	else
	{
		cnt[a[x]]--;
		if (cnt[a[x]] == 0)
			res--;
	}
	use[x] ^= 1;
}

void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1, u, v; i < n; i++)
	{
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	for (int i = 1; i <= n; i++)
		v.push_back(a[i]);
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	for (int i = 1; i <= n; i++)
		a[i] = lower_bound(all(v), a[i]) - v.begin();

	dfs1(1, -1, 1);
	dfs2(1, 1);

	int len = sqrt(n) + 1;
	for (int i = 1; i <= n * 2; i++)
		pos[i] = (i - 1) / len + 1;
	for (int i = 1, x, y; i <= m; i++)
	{
		cin >> x >> y;
		q[i].id = i;
		if (st[x] > st[y])
			swap(x, y);
		q[i].lca = Lca(x, y);
		if (q[i].lca == x)//x, y在以x为根的子树中
		{
			q[i].l = st[x];
			q[i].r = st[y];
			q[i].lca = 0;
		}
		else
		{
			q[i].l = ed[x];
			q[i].r = st[y];
		}
	}
	sort(q + 1, q + 1 + m);

	for (int i = 1, l = 1, r = 0; i <= m; i++)
	{
		while (l > q[i].l)
			cal(li[--l]);
		while (r < q[i].r)
			cal(li[++r]);
		while (l < q[i].l)
			cal(li[l++]);
		while (r > q[i].r)
			cal(li[r--]);
		if (q[i].lca)
			cal(q[i].lca);
		ans[q[i].id] = res;
		if (q[i].lca)
			cal(q[i].lca);
	}

	for (int i = 1; i <= m; i++)
		cout << ans[i] << '\n';
}

树链剖分

重链剖分

int tot, fa[N], dep[N], sz[N], hson[N], top[N], dfn[N], rnk[N];
vector<int> g[N];

void dfs1(int x, int father, int d)
{
	dep[x] = d;
	hson[x] = -1;
	sz[x] = 1;
	for (auto to : g[x])
	{
		if (to == father)
			continue;
		fa[to] = x;
		dfs1(to, x, d + 1);
		sz[x] += sz[to];
		if (hson[x] == -1 || sz[to] > sz[hson[x]])
			hson[x] = to;
	}
}

void dfs2(int x, int t)
{
	top[x] = t;//所在重链的最高点t
	dfn[x] = ++tot;
	rnk[tot] = x;
	if (hson[x] == -1)
		return;
	dfs2(hson[x], t);
	for (auto to : g[x])
	{
		if (to == fa[x] || to == hson[x])
			continue;
		dfs2(to, to);
	}
}

int Qmx(int x, int y)
{
	int ans = -inf, fx = top[x], fy = top[y];
	while (fx != fy)
	{
		if (dep[fx] > dep[fy])
		{
			ans = max(ans, st.query_mx(dfn[fx], dfn[x], 1));
			x = fa[fx];
			fx = top[x];
		}
		else
		{
			ans = max(ans, st.query_mx(dfn[fy], dfn[y], 1));
			y = fa[fy];
			fy = top[y];
		}
	}
	if (dfn[x] < dfn[y])
		swap(x, y);
	ans = max(ans, st.query_mx(dfn[y], dfn[x], 1));
	return ans;
}

void Update(int x, int y, int val)
{
	int fx = top[x], fy = top[y];
	while (fx != fy)
	{
		if (dep[fx] > dep[fy])
		{
			st.update(dfn[fx], dfn[x], val, 1);
			x = fa[fx];
			fx = top[x];
		}
		else
		{
			st.update(dfn[fy], dfn[y], val, 1);
			y = fa[fy];
			fy = top[y];
		}
	}
	if (dfn[x] > dfn[y])
		swap(x, y);
	st.update(dfn[x], dfn[y], val, 1);
}

CDQ分治

离线解决三维偏序问题， 解决和点对有关的问题

原则 ：前一半更新后一半

//https://www.luogu.com.cn/problem/P3157
#include<bits/stdc++.h>
#include<unordered_map>
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
const ll mod = 998244353;
const int N = 1e5 + 5;

int n, m, rk[N];

struct node {
	int val, del;
	int ans;
}a[N];

struct BIT {
	int b[N];
	int lowbit(int x)
	{
		return x & (-x);
	}
	void add(int x, int val)
	{
		while (x < N)
		{
			b[x] += val;
			x += lowbit(x);
		}
	}
	int getsum(int x)
	{
		int ans = 0;
		while (x)
		{
			ans += b[x];
			x -= lowbit(x);
		}
		return ans;
	}
	int query(int l, int r)
	{
		return getsum(r) - getsum(l - 1);
	}
}b;

void cdq(int l, int r)
{
	if (l == r)
		return;
	int mid = (l + r) / 2;
	cdq(l, mid);
	cdq(mid + 1, r);
	int i = l;
	int j = mid + 1;
	while (i <= mid)
	{
		while (a[i].val > a[j].val && j <= r)
		{
			b.add(a[j].del, 1);
			j++;
		}
		a[i].ans += b.query(a[i].del + 1, m + 1);
		i++; 
	}
	i = l;
	j = mid + 1;
	while (i <= mid)
	{
		while (a[i].val > a[j].val && j <= r)
		{
			b.add(a[j].del, -1);
			j++;
		}
		i++;
	}

	i = mid;
	j = r;
	while (j >= mid + 1)
	{
		while (a[i].val > a[j].val && i >= l)
		{
			b.add(a[i].del, 1);
			i--;
		}
		a[j].ans += b.query(a[j].del + 1, m + 1);
		j--;
	}

	i = mid;
	j = r;
	while (j >= mid + 1)
	{
		while (a[i].val > a[j].val && i >= l)
		{
			b.add(a[i].del, -1);
			i--;
		}
		j--;
	}
	sort(a + l, a + 1 + r, [](node& a, node& b) {
		return a.val < b.val;
		});
}

void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i].val, rk[a[i].val] = i, a[i].del = m + 1;
	for (int i = 1, x; i <= m; i++)
	{
		cin >> x;
		a[rk[x]].del = i;
	}

	ll res = 0;
	for (int i = 1; i <= n; i++)
	{
		res += b.query(a[i].val + 1, n);
		b.add(a[i].val, 1);
	}
	for (int i = 1; i <= n; i++)
		b.add(a[i].val, -1);
	cdq(1, n);
	sort(a + 1, a + 1 + n, [](node& a, node& b) {
		return a.del < b.del;
		});
	for (int i = 1; i <= m; i++)
	{ 
		cout << res << '\n';
		res -= a[i].ans;
	}
}

signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

//https://codeforces.com/contest/1045/problem/G
#include<bits/stdc++.h>
#include<unordered_map>
#include<array>
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
const ll mod = 998244353;
const int N = 1e5 + 5;

int n, k;
ll ans;

struct node {
	int x, r, q, L, R;
}a[N];

struct BIT {
	int b[N];
	int lowbit(int x)
	{
		return x & (-x);
	}
	void add(int x, int val)
	{
		while (x < N)
		{
			b[x] += val;
			x += lowbit(x);
		}
	}
	int getsum(int x)
	{
		int ans = 0;
		while (x)
		{
			ans += b[x];
			x -= lowbit(x);
		}
		return ans;
	}
	int query(int l, int r)
	{
		return getsum(r) - getsum(l - 1);
	}
}b;

void cdq(int l, int r)
{
	if (l == r)
		return;
	int mid = (l + r) / 2;
	cdq(l, mid);
	cdq(mid + 1, r);
	int i = mid + 1;
	int L = l, R = l;
	while (i <= r)
	{
		while (L <= mid && a[L].q < a[i].q - k)
			b.add(a[L++].x, -1);
		while (R <= mid && a[R].q <= a[i].q + k)
			b.add(a[R++].x, 1);
		ans += b.query(a[i].L, a[i].R);
		i++;
	}
	while (L < R)
		b.add(a[L++].x, -1);
	sort(a + l, a + r + 1, [](node& a, node& b) {
		return a.q < b.q;
		});
}

int p[N];
void solve()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i].x >> a[i].r >> a[i].q;
		a[i].L = max(0, a[i].x - a[i].r);
		a[i].R = min(inf, a[i].x + a[i].r);
		p[i] = a[i].x;
	}
	sort(p + 1, p + 1 + n);
	int len = unique(p + 1, p + 1 + n) - p - 1;
	for (int i = 1; i <= n; i++)
	{
		a[i].x = lower_bound(p + 1, p + 1 + len, a[i].x) - p;
		a[i].L = lower_bound(p + 1, p + 1 + len, a[i].L) - p;
		a[i].R = upper_bound(p + 1, p + 1 + len, a[i].R) - p - 1;
	}
	sort(a + 1, a + 1 + n, [](node& a, node& b) {
		return a.r > b.r;
		});
	cdq(1, n);
	cout << ans << '\n';
}

signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

欧拉序

欧拉序1

这一种欧拉序相当于是在dfs的时候，如果某个节点入栈，就把这个节点记录下来，直到后面的操作中这个节点出栈，再记录一次这个节点

欧拉序2

这一种欧拉序相当于是在dfs的时候，如果储存节点的栈变化一次，就把栈顶的节点编号记录下来,也就是说，每当访问完一个节点的子树，则需要返回一次该节点

树上启发式合并

/*
题意 ：给出一棵 n 个节点以 1 为根的树，节点 u 的颜色为 c[u]
现在对于每个结点 u 询问 u 子树里一共出现了多少种不同的颜色。
*/
int n, a[N], c[N];
int ans[N];
vector<int> g[N];
int hson[N], L[N], R[N], sz[N], tot, rk[N];
int cnt[N], res;

void dfs(int x, int fa)
{
    hson[x] = -1;
    sz[x] = 1;
    L[x] = ++tot;
    rk[tot] = x;
    for (int &to : g[x])
    {
        if (to == fa) continue;
        dfs(to, x);
        sz[x] += sz[to];
        if (hson[x] == -1 || sz[to] > sz[hson[x]]) hson[x] = to;
    }
    R[x] = tot;
}

void add(int x)
{
    cnt[c[x]]++;
    if(cnt[c[x]] == 1) res++;
}

void del(int x)
{
    cnt[c[x]]--;
    if(cnt[c[x]] == 0) res--;
}

void dsu(int x, int fa, bool keep)
{
    for (int &to : g[x])// 计算轻儿子的答案
        if (to != fa && hson[x] != to)
            dsu(to, x, false);
    if (hson[x] != -1)// 计算重儿子答案并保留计算过程中的数据（用于继承）
        dsu(hson[x], x, true);

    for (int &to : g[x])// 把轻儿子(轻子树)的贡献加进去,这样这颗子树的贡献就全在了
    {
        if (to != fa && hson[x] != to)
        {
            //for(int i = L[to]; i <= R[to]; i++) cal();
            for (int i = L[to]; i <= R[to]; i++)
                add(rk[i]);
        }
    }

    add(x);// 将当前点的贡献加进去
	//cal(x)
    
    ans[x] = res; // 计算以 x 为根的答案

    if (!keep)//如果当前子树的是 fa 的轻儿子，则删除当前子树的贡献
    {
        for (int i = L[x]; i <= R[x]; i++)
            del(rk[i]);
    }
}

void solve()
{
    cin >> n;
    for (int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for(int i = 1; i <= n; i++) cin >> c[i];

    dfs(1, -1);
    dsu(1, -1, false);
    
    int m;
    cin >> m;
    while(m--)
    {
        int x;
        cin >> x;
        cout << ans[x] << '\n';
    }
}

点分治

// 题意:给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。
//O（nlognlogn）
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 10;

int n, m;
int dis[N], vis[N], num, root, MX, sz[N], tot;
vector<pair<int, int>> g[N];
int q[105], ans[105];

void getroot(int x, int fa)// 找重心
{
	sz[x] = 1;  
	int mx = 0;
	for (auto &now : g[x])
	{
		int to = now.first;
		if (to == fa || vis[to])
			continue;
		getroot(to, x);
		sz[x] += sz[to];
		mx = max(mx, sz[to]);
	}
	mx = max(mx, num - sz[x]);
	if (mx < MX)
	{
		MX = mx;
		root = x;
	}
}

void getdis(int x, int fa, int d)
{
	dis[++tot] = d;
	for (auto &[to, w] : g[x])
	{
		if (vis[to] || to == fa) continue;
		getdis(to, x, d + w);
	}
}

int cal(int x, int k)//O(logn)
{
	int res = 0;
	for (int l = 1; l <= tot; l++)//合并用二分保证复杂度
		res += upper_bound(dis + 1, dis + 1 + tot, k - dis[l])
		- lower_bound(dis + 1, dis + 1 + tot, k - dis[l]);
	return res;
}

int ok[105];// 记录询问是否已经存在答案了
void divide(int x)//O(nlogn)，求解以当前所求子树中，经过 x 的路径的答案
{
	tot = 0;
	getdis(x, -1, 0);// 求当前子树中每个点到 x 的距离
	sort(dis + 1, dis + 1 + tot);
	
    for (int i = 1; i <= m; i++) if(!ok[i]) ans[i] += cal(x, q[i]);
    // 计算经过 x 的路径的条数
    // 因为是通过 dis 计算出的路径数，可能两个端点都位于 x 的同一个儿子，此时路径是非法的

	vis[x] = 1;
	for (auto &[to, w] : g[x])
	{
		if (vis[to]) continue;

		tot = 0;
		getdis(to, -1, w);//以 w 为起始距离，保证路径长度相同
		sort(dis + 1, dis + 1 + tot);
		for (int i = 1; i <= m; i++) if(!ok[i]) ans[i] -= cal(x, q[i]);
        // 减去非法路径数，因为此时 dis 的端点都在同一个儿子中
	}

	for (int i = 1; i <= m; i++) if (ans[i]) ok[i] = 1; // 减去非法路径后，若仍有长度为 k 的路径存在则有答案

	for (auto &[to, w] : g[x]) //子问题
	{
		if (vis[to]) continue;
		num = sz[to];
		MX = inf;
		getroot(to, -1);
		divide(root);
	}
}

void solve()
{
	cin >> n >> m;
	for (int i = 1, u, v, w; i < n; i++)
	{
		cin >> u >> v >> w;
		g[u].push_back({ v, w });
		g[v].push_back({ u, w });
	}
	for (int i = 1; i <= m; i++) cin >> q[i];// 离线
	
    num = n, MX = inf;
	getroot(1, -1);
	divide(root);
	for (int i = 1; i <= m; i++) cout << (ans[i] ? "AYE" : "NAY") << '\n';
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;

/*
离线处理询问，询问 u, v 会在 路径上某个点作为重心时求解，不然将询问丢给子树
*/

const int N = 5e5 + 10;
int n, q;
ll c[N];
vector<int> g[N];
vector<array<int, 3>> qry[N];

int vis[N], sz[N], root, bel[N];//bel 记录处于根的那棵子树中//板子部分
ll f[N][60];
int dp[N][60];
int ans[N];

void get_sz(int x, int fa)//板子部分
{
    sz[x] = 1;
    for(auto &to : g[x])
    {
        if(to == fa || vis[to]) continue;
        get_sz(to, x);
        sz[x] += sz[to];
    }
}
int find(int x, int fa, int s)//找重心//板子部分
{
    for(auto &to : g[x])
    {
        if(to == fa || vis[to] || 2 * sz[to] <= s) continue;
        return find(to, x, s);
    }
    return x;
}

void dfs(int x, int fa)// cal，处理答案
{
    for(auto &to : g[x])
    {
        if(to == fa || vis[to]) continue;
        bel[to] = (x == root ? to : bel[x]);
        for(int i = 0; i < 60; i++)
        {
            if(dp[x][i] == -1 || !(c[x] & c[to])) dp[to][i] = -1;
            else if(f[x][i] & c[to])
            {
                dp[to][i] = dp[x][i] + 1;
                f[to][i] = f[x][i] & c[to];
            }
            else
            {
                dp[to][i] = dp[x][i] + 2;
                f[to][i] = c[x] & c[to];
            }
        }  
        dfs(to, x);
    }
}

void divide(int x)
{
    auto Q = move(qry[x]);
    get_sz(x, -1);//板子部分
    x = find(x, -1, sz[x]);// x 为重心 //板子部分

    for(int i = 0; i < 60; i++)
    {
        if(c[x] >> i & 1)
        {
            dp[x][i] = 0;
            f[x][i] = 1ll << i;
        }
        else
            dp[x][i] = -1;
    }
    
    root = x;//板子部分
    bel[x] = x;//板子部分
    dfs(x, -1);

    for(auto &[u, v, id] : Q)
    {
        if(bel[u] == bel[v]) qry[bel[u]].push_back({u, v, id});
        else
        {
            for(int i = 0; i < 60; i++)
            {
                if(dp[u][i] != -1 && dp[v][i] != -1)
                {
                    int res = dp[u][i] + dp[v][i];
                    if(ans[id] == -1 || ans[id] > res) ans[id] = res;
                }
            }
        }
    }

    vis[x] = 1;//板子部分
    for(auto &to : g[x]) if(!vis[to]) divide(to);//板子部分
}

void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> c[i];
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for(int i = 1; i <= q; i++)
    {
        int u, v;
        cin >> u >> v;
        qry[1].push_back({u, v, i});
    }

    for(int i = 1; i <= q; i++) ans[i] = -1;

    divide(1);//板子部分

    for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}