线段树

（施工中ing...）

列题

P2824 排序

solution

题目要求对一个 $1$~$n$ 进行多次区间内排序，并输出最后第 $q$ 位置上的数字

直接模拟肯定会 T ，先考虑数组为 0/1 串的情况，这时可以用线段树处理，具体地：

1. 统计区间内的 1 的数量为 $cnt$
2. 升序情况：
   • 用线段树将区间 $[r-cnt+1,r]$ 内改为 1
   • 用线段树将区间 $[l , r - cnt]$ 内改为 0
3. 降序情况：
   • 用线段树将区间 $[l,l+cnt-1]$ 内改为 1
   • 用线段树将区间 $[l+cnt,r]$ 内改为 0

对于一个 $1$~$n$ 的排列，注意到有这样子的一个性质，若最后第 $q$ 位置上的数字为 $res$，则所有的小于等于 $res$ 的数字 $x$ 都有：

将数组中大于等于 $x$ 的数标上 1 ，其余标 0，经过多次区间内排序排序后在 $q$ 位置上的数一定是 1

由性质所以答案具有二段性，所以我们可以二分第 $q$ 位置上的数，判断是否满足经上面的过程后 $q$ 位置上的数是 1 即可，判断过程中 0/1 串排序可用线段树快速处理

code

#include<bits/stdc++.h>
#define qwq ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int N = 1e5 + 20;

struct segmentTree{
	int s , t , sum , d;
}tr[N << 2];

struct ask{
	int op , l , r;
}q[N];

int n , m , a[N] , b[N] , o;

void pushup(int p){
	tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
}

void pushdown(int p){
	int s = tr[p].s , t = tr[p].t , m = (s + t) >> 1;
	if(tr[p].d == -1) return;
	
	if(tr[p].d) tr[p << 1].sum = m - s + 1 , tr[p << 1 | 1].sum = t - m;
	else tr[p << 1].sum = 0 , tr[p << 1 | 1].sum = 0;
	
	tr[p << 1].d = tr[p << 1 | 1].d = tr[p].d;
	tr[p].d = -1;
}

void build(int s , int t , int p){
	if(s == t){
		tr[p] = {s , t , b[s] , -1};
		return;
	}
	tr[p] = {s , t , 0 , -1};
	int m = (s + t) >> 1;
	build(s , m , p << 1);
	build(m + 1 , t , p << 1 | 1);
	pushup(p);
}

void modify(int l , int r , int k , int p){
	if(l > r) return;
	int s = tr[p].s , t = tr[p].t;
	
	if(l <= s && t <= r){
		if(k) tr[p].sum = t - s + 1 , tr[p].d = k;
		else tr[p].sum = 0 , tr[p].d = k;
		return;
	}
	pushdown(p);
	int m = (s + t) >> 1;
	if(l <= m) modify(l , r , k , p << 1);
	if(r > m) modify(l , r , k , p << 1 | 1);
	pushup(p);
}

int query(int l , int r , int p){
	if(l > r) return 0;
	int s = tr[p].s , t = tr[p].t;
	
	if(l <= s && t <= r){
		return tr[p].sum;
	}
	pushdown(p);
	int m = (s + t) >> 1 , res = 0;
	if(l <= m) res += query(l , r , p << 1);
	if(r > m) res += query(l , r , p << 1 | 1);
	return res;
}

bool check(int res){
	for(int i = 1 ; i <= n ; i ++){
		b[i] = (a[i] >= res ? 1 : 0);
	}
	build(1 , n , 1);
	
	for(int i = 1 ; i <= m ; i ++){
		int l = q[i].l , r = q[i].r;
		int cnt = query(l , r , 1);
		
		if(q[i].op == 0){
			modify(r - cnt + 1 , r , 1 , 1);
			modify(l , r - cnt , 0 , 1);
		}
		else{
			modify(l , l + cnt - 1 , 1 , 1);
			modify(l + cnt , r , 0 , 1);
		}
	}
	return (query(o , o , 1) == 1);
}

int main(){                     qwq
	cin >> n >> m;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	for(int i = 1 ; i <= m ; i ++){
		cin >> q[i].op >> q[i].l >> q[i].r;
	}
	cin >> o;
	
	int l = 1 , r = n;
	while(l < r){
		int mid = (l + r + 1) >> 1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l;
	return 0;
}

P3722 影魔

solution

先翻译下题面，就是在 $1$ ~ $n$ 的排列中求下列点对的数量

1. 满足 $k_i > c \& k_j > c$ $c = \max_{p=i+1}^j{k_p}$ 的点对
2. 满足 $k_i < c < k_j$ 或满足 $k_j < c < k_i$ 的点对

可以先对于每个点 $i$ 预处理出其左侧最大的数和其右侧最大的数 $l_i$ 和 $r_i$ 用单调栈处理，从两边扫一遍即可

随后注意到，对于每个 $l_i$ 和 $r_i$ 的数对：

1. $l_i$ 和 $r_i$ 产生 $p1$ 贡献
2. $l_i$ 和 $[i,r_i - 1]$ 产生 $p2$ 贡献
3. $[l_i - 1 , r_i]$ 和 $r_i$ 产生 $p2$ 贡献

所以可以依次去扫每一个位置，按照上面的方法累加贡献即可，具体地：

1. 当扫到某一个区间的左端点前时，统计区间所有数产生的贡献 $s_1$
2. 当扫到某一个区间的右端点时，统计区间所有数产生的贡献 $s_2$
3. 区间最终的答案即为 $s_2 - s_1$

可以用桶数组来记录每个 $l_i$ 和 $r_i$ 以及区间的左右端点，扫每一个位置时遍历这个位置的桶数组即可

对于 $l_i$ 和 $r_i$ 产生的贡献，用线段树维护即可，产生的贡献就是区间加，统计区间答案就是区间求和

code

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

const int N = 2e5 + 5;

struct ask{
	int a , b , id;
}q[N];

struct node{
	int id , w;
};

struct segmentTree{
	int s , t , w , b;
}tr[N << 2];

int n , m , p1 , p2;
int k[N] , l[N] , r[N] , s1[N] , s2[N];
stack<node> st;
vector<node> to1[N] , to2[N] , to3[N] , to4[N];

void pushup(int p){
	tr[p].w = tr[p << 1].w + tr[p << 1 | 1].w;
}

void pushdown(int p){
	int s = tr[p].s , t = tr[p].t , m = (s + t) >> 1;
	
	tr[p << 1].w += (m - s + 1) * tr[p].b , tr[p << 1 | 1].w += (t - m) * tr[p].b;
	tr[p << 1].b += tr[p].b , tr[p << 1 | 1].b += tr[p].b;
	tr[p].b = 0;
}

void build(int s , int t , int p){
	tr[p] = {s , t , 0 , 0};
	if(s == t){
		return;
	}
	int m = (s + t) >> 1;
	build(s , m , p << 1);
	build(m + 1 , t , p << 1 | 1);
}

void modify(int l , int r , int k , int p){
	if(l > r) return;
	int s = tr[p].s , t = tr[p].t;
	if(l <= s && t <= r){
		tr[p].w += (t - s + 1) * k , tr[p].b += k;
		return;
	}
	int m = (s + t) >> 1;
	pushdown(p);
	if(l <= m) modify(l , r , k , p << 1);
	if(r > m) modify(l , r , k , p << 1 | 1);
	pushup(p);
}

int query(int l , int r , int p){
	if(l > r) return 0;
	int s = tr[p].s , t = tr[p].t;
	if(l <= s && t <= r){
		return tr[p].w;
	}
	int m = (s + t) >> 1 , res = 0;
	pushdown(p);
	if(l <= m) res += query(l , r , p << 1);
	if(r > m) res += query(l , r , p << 1 | 1);
	return res;
}

signed main(){
	cin >> n >> m >> p1 >> p2;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> k[i];
	}
	for(int i = 1 ; i <= n ; i ++){
		while(!st.empty() && st.top().w <= k[i]) st.pop();
		if(!st.empty()) l[i] = st.top().id;
		st.push({i , k[i]});
		r[i] = n + 1;
	}
	while(!st.empty()) st.pop();
	
	for(int i = n ; i >= 1 ; i --){
		while(!st.empty() && st.top().w <= k[i]) st.pop();
		if(!st.empty()) r[i] = st.top().id;
		st.push({i , k[i]});
	}
	for(int i = 1 ; i <= m ; i ++){
		cin >> q[i].a >> q[i].b;
		q[i].id = i;
		to3[q[i].a - 1].push_back({i , q[i].b});
		to4[q[i].b].push_back({i , q[i].a});
	}
	for(int i = 1 ; i <= n ; i ++){
		to1[l[i]].push_back({i , r[i]});
		to2[r[i]].push_back({i , l[i]});
	}
	
	build(1 , n , 1);
	for(int i = 1 ; i <= n ; i ++){
		for(auto t : to1[i]){
			if(t.w - 1 != 0) modify(t.id + 1 , t.w - 1 , p2 , 1);
		}
		for(auto t : to2[i]){
			if(t.w != 0) modify(t.w , t.w , p1 , 1);
			if(t.id - 1 != 0) modify(t.w + 1 , t.id - 1 , p2 , 1);
		}
		for(auto t : to3[i]){
			s1[t.id] = query(i + 1 , t.w , 1);
		}
		for(auto t : to4[i]){
			s2[t.id] = query(t.w , i , 1) + (i - t.w) * p1;
		}
	}
	for(int i = 1 ; i <= m ; i ++){
		cout << s2[i] - s1[i] << endl;
	}
	return 0;
}