线段树的静态区间查询
- 区间里大于x的最左边的位置：
看左区间的最大值是否大于x，决定是否往左区间找
- 区间最大连续和：
维护区间左连续最大和，右连续最大和，最大连续和
- 求整个区间中大于k的数之和：
权值线段树，然后求区间和
- 区间众数 之 在排好序的数组里查询区间众数的个数：
维护区间左连续相同数的个数，区间右连续相同数的个数，区间连续相同数的个数
- 求逆序对：
从左往右扫，每次ans加上权值线段树里比这个数大的数的个数，然后往权值线段树加上这个数
- 一个二元数组，即数组里每个数有两种权值，记为权值A 和 权值B，查询n次，每次查询数组里权值A < ci 且权值B > di的数的个数(ci是递增的) ：
先把数组按权值A排序，然后从左往右扫，每次统计答案后，再把权值B加入到权值线段树里，和求逆序对的做法一样
注意这样排序做已经是很不错的做法了，如果要更优则需要用树套树这种东西做了，非常麻烦，所以碰到这种问题就老老实实写结构体排序+开一个权值线段树吧
有序区间的区间众数个数代码：
struct NODE {
int l, r, mid;
int lc, rc, mc;
}tree[MAXN*4];
void build(int pos, int l, int r) {
tree[pos].l = l; tree[pos].r = r; tree[pos].mid = l + r >> 1;
if (l == r) {
tree[pos].lc = tree[pos].rc = tree[pos].mc = 1;
return;
}
int mid = l + r >> 1;
build(pos << 1, l, mid);
build(pos << 1 | 1, mid + 1, r);
if (a[l] == a[mid + 1]) tree[pos].lc = tree[pos << 1].lc + tree[pos << 1 | 1].lc;
else tree[pos].lc = tree[pos << 1].lc;
if (a[mid] == a[r]) tree[pos].rc = tree[pos << 1 | 1].rc + tree[pos << 1].rc;
else tree[pos].rc = tree[pos << 1 | 1].rc;
tree[pos].mc = max(tree[pos << 1].mc, tree[pos << 1 | 1].mc);
if (a[mid] == a[mid + 1]) tree[pos].mc = max(tree[pos].mc, tree[pos << 1].rc + tree[pos << 1 | 1].lc);
}
int Q_l(int pos, int l, int r) {
if (tree[pos].l == l && tree[pos].r == r) return tree[pos].lc;
int mid = tree[pos].mid;
if (r <= mid) return Q_l(pos << 1, l, r);
else if (l > mid) return Q_l(pos << 1 | 1, l, r);
else {
if (a[l] == a[mid + 1]) return Q_l(pos << 1, l, mid) + Q_l(pos << 1 | 1, mid + 1, r);
else return Q_l(pos << 1, l, mid);
}
}
int Q_r(int pos, int l, int r) {
if (tree[pos].l == l && tree[pos].r == r) return tree[pos].rc;
int mid = tree[pos].mid;
if (r <= mid) return Q_r(pos << 1, l, r);
else if (l > mid) return Q_r(pos << 1 | 1, l, r);
else {
if (a[mid] == a[r]) return Q_r(pos << 1, l, mid) + Q_r(pos << 1 | 1, mid + 1, r);
else return Q_r(pos<<1|1,mid+1,r);
}
}
int Q(int pos, int l, int r) {
if (tree[pos].l == l && tree[pos].r == r) return tree[pos].mc;
int mid = tree[pos].mid;
if (r <= mid) return Q(pos << 1, l, r);
else if (l > mid) return Q(pos << 1 | 1, l, r);
else {
int res = max(Q(pos << 1, l, mid), Q(pos << 1 | 1, mid + 1, r));
if (a[mid] == a[mid + 1]) res = max(res, Q_r(pos << 1, l, mid) + Q_l(pos << 1 | 1, mid + 1, r));
return res;
}
}
线段树的区间修改和懒标记
- 扫描线模板题中维护区间里非0数的个数：
记录区间被矩形完全覆盖的矩形个数，查询时，如果区间被某个矩形完全覆盖，非0数=区间长度，否则非0数=左区间非0数+右区间非0数
因为查询都是查询[1,n]区间的非0数，所以不需要懒标记
- 以函数映射为懒标记的线段树：
和一般懒标记一样，写码时要小心，lazy_tag别忘了处理
- 宾馆住户题，找到宾馆里最靠左的有连续x个空房的房间并入住，宾馆区间[x,y]退房：
维护区间左连续空房数，右连续空房数，最大连续空房数，还有区间修改需要的懒标记
宾馆住户题代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN = 1e5 + 7;
struct NODE {
int l, r, mid, len;
int lazy, lc, rc, mc;
}tree[MAXN * 4];
void build(int pos, int l, int r) {
tree[pos].l = l; tree[pos].r = r; tree[pos].mid = l + r >> 1; tree[pos].len = r - l + 1;
tree[pos].lazy = 2;
tree[pos].lc = tree[pos].rc = tree[pos].mc = tree[pos].len;
if (l == r) return;
int mid = l + r >> 1;
build(pos << 1, l, mid);
build(pos << 1 | 1, mid + 1, r);
}
void pd(int pos) {
int lazy = tree[pos].lazy;
tree[pos << 1].lazy = tree[pos << 1 | 1].lazy = lazy;
if (lazy == 1) {
tree[pos << 1].lc = tree[pos << 1].rc = tree[pos << 1].mc = 0;
tree[pos << 1 | 1].lc = tree[pos << 1 | 1].rc = tree[pos << 1 | 1].mc = 0;
}
else {
tree[pos << 1].lc = tree[pos << 1].rc = tree[pos << 1].mc = tree[pos << 1].len;
tree[pos << 1 | 1].lc = tree[pos << 1 | 1].rc = tree[pos << 1 | 1].mc = tree[pos << 1 | 1].len;
}
tree[pos].lazy = 2;
}
void update(int pos) {
if (tree[pos << 1].lc == tree[pos<<1].len) tree[pos].lc = tree[pos << 1].len + tree[pos << 1 | 1].lc;
else tree[pos].lc = tree[pos << 1].lc;
if (tree[pos << 1 | 1].rc == tree[pos << 1 | 1].len) tree[pos].rc = tree[pos << 1 | 1].len + tree[pos << 1].rc;
else tree[pos].rc = tree[pos << 1 | 1].rc;
tree[pos].mc = max(tree[pos << 1].mc, tree[pos << 1 | 1].mc);
tree[pos].mc = max(tree[pos].mc, tree[pos << 1].rc + tree[pos << 1 | 1].lc);
}
void CHANGE(int pos, int l, int r, int k) {
if (tree[pos].l == l && tree[pos].r == r) {
tree[pos].lazy = k;
if (k) {
tree[pos].lc = tree[pos].rc = tree[pos].mc = 0;
}
else {
tree[pos].lc = tree[pos].rc = tree[pos].mc = tree[pos].len;
}
return;
}
if (tree[pos].lazy != 2) pd(pos);
int mid = tree[pos].mid;
if (r <= mid) CHANGE(pos << 1, l, r, k);
else if (l > mid) CHANGE(pos << 1 | 1, l, r, k);
else {
CHANGE(pos << 1, l, mid, k);
CHANGE(pos << 1 | 1, mid + 1, r, k);
}
update(pos);
}
int Q(int pos, int x) {
if (tree[pos].mc < x) return 0;
if (tree[pos].lazy != 2) pd(pos);
if (tree[pos << 1].mc >= x) return Q(pos << 1, x);
if (tree[pos << 1].rc + tree[pos << 1 | 1].lc >= x) return tree[pos << 1].r - tree[pos << 1].rc + 1;
else return Q(pos << 1|1, x);
}
int main()
{
int n, m, op, x, y;
cin >> n >> m;
build(1, 1, n);
while (m--) {
scanf("%d%d", &op, &x);
if (op == 2) {
scanf("%d", &y);
CHANGE(1, x, x + y - 1, 0);
}
else {
int pp = Q(1, x);
printf("%d
", pp);
if (pp) CHANGE(1, pp, pp + x - 1, 1);
}
}
return 0;
}
主席树的静态区间查询
建n个前缀权值线段树,类似前缀和,节点开MAXN*40差不多
void modify(int l, int r, int& x, int y, int pos) {
T[x = ++cnt] = T[y]; T[x].cnt++;
if (l == r) return;
int mid = l + r >> 1;
if (pos <= mid) modify(l, mid, T[x].l, T[y].l, pos);
else modify(mid + 1, r, T[x].r, T[y].r, pos);
}
查询有些东西的时候就可以把它当权值线段树用
- 区间第k大
先求区间里小于等于mid的数的个数，判断在权值线段树的左子树还是右子树查询，l == r时返回
- 区间小于等于某个数的所有数之和
权值线段树存sum，区间查询
- 区间众数 之 找区间里出现次数 > len / 2的数
查询区间即查询第len / 2 + 1大的数，再验证：查询这个数是否出现> len / 2次
关于离散化去重操作：
vector<int> v;
int getid(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; }
int main()
{
int n, m, x, y, k;
cin >> n >> m;
for (int i = 1; i <= n; i++)scanf("%d", &a[i]), v.push_back(a[i]);
sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 1; i <= n; i++) modify(1, n, root[i], root[i - 1], getid(a[i]));
//以下可以n = v.size();
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &k);
printf("%d
", v[Q_k(1, n, root[x - 1], root[y], k) - 1]);
}
return 0;
}
动态主席树
静态主席树是建了一个前缀和权值线段树
如果有修改操作的话，就要批量修改前缀和权值线段树了
所以就要用树套权值线段树之类的东西
这里用树状数组套权值线段树
查询区间第k大时，两棵前缀和权值线段树相减就变成了log棵树 - log棵树
节点要开MAXN*400或MAXN*200个
动态第k大模板：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = 2e5 + 7;
struct NODE {
int l, r, su;
}T[MAXN * 400];
int a[MAXN];
int root[MAXN];
vector<int>v;
int cnt = 0;
int n, m;
int siz;
int lowbit(int x) { return x & -x; }
int getid(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; }
void modify(int l, int r, int& x, int pos,int k) {//对这颗树进行add操作
if (!x) x = ++cnt;
T[x].su += k;
if (l == r) return;
int mid = l + r >> 1;
if (pos <= mid) modify(l, mid, T[x].l, pos, k);
else modify(mid + 1, r, T[x].r, pos, k);
}
void bit_modify(int x, int pos, int k) {//对log棵树进行add，x是树状数组的哪个位置
for (int i = x; i <= n; i += lowbit(i)) {//树状数组有n个节点
modify(1, siz, root[i], pos, k);//这个要用root[i]
}
}
NODE st1[MAXN], st2[MAXN];//存两组树
int tot1, tot2;
int Q_k(int l, int r, int k) {
if (l == r) return l;
int res = 0, mid = l + r >> 1;
for (int i = 1; i <= tot1; i++) res += T[st1[i].l].su;
for (int i = 1; i <= tot2; i++) res -= T[st2[i].l].su;
if (res >= k) {
for (int i = 1; i <= tot1; i++) st1[i] = T[st1[i].l];
for (int i = 1; i <= tot2; i++) st2[i] = T[st2[i].l];
return Q_k(l, mid, k);
}
else {
for (int i = 1; i <= tot1; i++) st1[i] = T[st1[i].r];
for (int i = 1; i <= tot2; i++) st2[i] = T[st2[i].r];
return Q_k(mid + 1, r, k - res);
}
}
int pr_Q(int x, int y, int k) {//查询的预处理
tot1 = tot2 = 0;
for (int i = y; i; i -= lowbit(i)) {
st1[++tot1] = T[root[i]];
}
for (int i = x; i; i -= lowbit(i)) {
st2[++tot2] = T[root[i]];
}
return Q_k(1, siz, k);
}
struct DT {
char op;
int x, y, k;
}dt[MAXN];//操作
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), v.push_back(a[i]);
char op;
int x, y, k;
for (int i = 1; i <= m; i++) {//存操作
cin >> op >> x >> y;
dt[i].op = op; dt[i].x = x; dt[i].y = y;
if (op == 'Q') {
cin >> k;
dt[i].k = k;
}
else {
v.push_back(y);//一起给离散化
}
}
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
siz = v.size();//权值线段树开siz个节点
for (int i = 1; i <= n; i++) bit_modify(i ,getid(a[i]), 1);
for (int i = 1; i <= m; i++) {
x = dt[i].x; y = dt[i].y;
if (dt[i].op == 'C') {
bit_modify(x, getid(a[x]), -1);
a[x] = y;
bit_modify(x ,getid(a[x]), 1);
}
else {
k = dt[i].k;
printf("%d
", v[pr_Q(x - 1, y, k) - 1]);
}
}
return 0;
}
动态逆序对：
每次删掉一个数，再问整个数组的逆序对变成多少
计算删掉数后减少的贡献：这个数前比它大的数的个数+这个数后比它小的数，也就是前缀后缀权值线段树的区间查询
删掉数后，需要改变前缀后缀权值线段树，于是需要树状数组套权值线段树
//UVA11990 ``Dynamic'' Inversion
//原题：P3157 [CQOI2011]动态逆序对
//主席树做法
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN = 2e5 + 7;
int n, m;
int a[MAXN];
int id[MAXN];
int bit[MAXN];
//树状数组
int lowbit(int x) { return x & -x; }
void ADD_BIT(int pos, int k) {
for (int i = pos; i <= n; i += lowbit(i)) bit[i] += k;
}
int Q_BIT(int pos) {
int res = 0;
for (int i = pos; i; i -= lowbit(i)) res += bit[i];
return res;
}
//动态主席树
int siz;
struct NODE {
int l, r, su;
}T_pre[MAXN * 200], T_suf[MAXN * 200];
int cnt_pre = 0, cnt_suf = 0;
int root_pre[MAXN], root_suf[MAXN];
void modify_pre(int l, int r, int& x,int pos,int k) {
if (!x) x = ++cnt_pre;
T_pre[x].su += k;
if (l == r) return;
int mid = l + r >> 1;
if (pos <= mid) modify_pre(l, mid, T_pre[x].l, pos, k);
else modify_pre(mid + 1, r, T_pre[x].r, pos, k);
}
void modify_suf(int l, int r, int& x, int pos,int k) {
if(!x) x = ++cnt_suf;
T_suf[x].su += k;
if (l == r) return;
int mid = l + r >> 1;
if (pos <= mid) modify_suf(l, mid, T_suf[x].l, pos, k);
else modify_suf(mid + 1, r, T_suf[x].r, pos, k);
}
void bit_modify_pre(int x, int pos, int k) {
for (int i = x; i <= n; i += lowbit(i)) modify_pre(1, siz, root_pre[i], pos, k);
}
void bit_modify_suf(int x, int pos, int k) {
for (int i = x; i <= n; i += lowbit(i)) modify_suf(1, siz, root_suf[i], pos, k);
}
int Q_pre(int l, int r, int x, int tl, int tr) {
if (l == tl && r == tr) return T_pre[x].su;
int mid = tl + tr >> 1;
if (r <= mid) return Q_pre(l, r, T_pre[x].l, tl, mid);
else if (l > mid) return Q_pre(l, r, T_pre[x].r, mid + 1, tr);
else return Q_pre(l, mid, T_pre[x].l, tl, mid) + Q_pre(mid + 1, r, T_pre[x].r, mid + 1, tr);
}
int Q_suf(int l, int r, int x, int tl, int tr) {
if (l == tl && r == tr) return T_suf[x].su;
int mid = tl + tr >> 1;
if (r <= mid) return Q_suf(l, r, T_suf[x].l, tl, mid);
else if (l > mid) return Q_suf(l, r, T_suf[x].r, mid + 1, tr);
else return Q_suf(l, mid, T_suf[x].l, tl, mid) + Q_suf(mid + 1, r, T_suf[x].r, mid + 1, tr);
}
int bit_Q_pre(int l,int r,int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) {
res += Q_pre(l, r, root_pre[i], 1, siz);
}
return res;
}
int bit_Q_suf(int l, int r, int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += Q_suf(l, r, root_suf[i], 1, siz);
return res;
}
int main()
{
cin >> n >> m;
long long ans = 0;
siz = n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), id[a[i]] = i;
for (int i = 1; i <= n; i++) bit_modify_pre(i, a[i], 1);
for (int i = n; i; i--) bit_modify_suf(n - i + 1, a[i], 1);
for (int i = 1; i <= n; i++) {
ans += Q_BIT(n) - Q_BIT(a[i]);
ADD_BIT(a[i], 1);
}
int x;
while (m--) {
scanf("%d", &x);
printf("%lld
", ans);
int res = 0;
if (x < n) res += bit_Q_pre(x + 1, n, id[x]);//主席树是root[x],动态主席树是x
if (x > 1) res += bit_Q_suf(1, x - 1, n - id[x] + 1);
ans -= res;
bit_modify_pre(id[x], x, -1);
bit_modify_suf(n - id[x] + 1, x, -1);
}
return 0;
}
关于P3157 [CQOI2011]动态逆序对，还可以分块做,开100个树状数组
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 2e5 + 7;
int bit[103][MAXN];
int a[MAXN], b[MAXN];
int n, m;
int id[MAXN];
int cnt = -1;
bool vis[MAXN];
int lowbit(int x) { return x & -x; }
void ADD(int cen, int pos, int k) {
for (int i = pos; i <= n; i += lowbit(i)) bit[cen][i] += k;
}
int Q(int cen, int pos) {
int res = 0;
for (int i = pos; i; i -= lowbit(i)) res += bit[cen][i];
return res;
}
void ADD_B(int pos, int k) {
for (int i = pos; i <= n; i += lowbit(i)) b[i] += k;
}
int Q_B(int pos) {
int res = 0;
for (int i = pos; i; i -= lowbit(i)) res += b[i];
return res;
}
int solve(int ct,int pp,int x) {
int res = 0;
for (int i = 0; i < ct; i++) res += Q(i, n) - Q(i, x);
for (int i = ct + 1; i <= cnt; i++) res += Q(i, x);
for (int i = 1; i < pp; i++) if (!vis[ct * 1000 + i] && a[ct * 1000 + i] > x) res++;
for (int i = pp + 1; i <= 1000 && i + ct * 1000 <= n; i++) if (!vis[ct * 1000 + i] && a[ct * 1000 + i] < x) res++;
return res;
}
int main()
{
while (cin >> n >> m) {
long long ans = 0;
cnt = -1;
memset(bit, 0, sizeof(bit));
memset(b, 0, sizeof(b));
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) {
if (i % 1000 == 1) cnt++;
scanf("%d", &a[i]);
int pp = i - cnt * 1000;
ADD(cnt, a[i], 1);
id[a[i]] = i;
ans += Q_B(n) - Q_B(a[i]);
ADD_B(a[i], 1);
}
int x;
while (m--) {
printf("%lld
", ans);
scanf("%d", &x);
int p = id[x];
int ct = (p - 1) / 1000;
int pp = p - ct * 1000;
int res = solve(ct,pp,x);
ans -= res;
ADD(ct, x, -1);
vis[p] = true;
}
}
return 0;
}